@InProceedings{goodrich:external,
  author = {Michael T. Goodrich and Jyh-Jong Tsay and Darren E. Vengroff and
  Jeffrey Scott Vitter},
  title = {External-Memory Computational Geometry},
  booktitle = {Proceedings of the 34th Annual Symposium on Foundations of
  Computer Science},
  year = {1993},
  month = {November},
  pages = {714--723},
  keywords = {computational geometry, parallel I/O algorithm, pario-bib},
  abstract = {In this paper, we give new techniques for designing efficient
  algorithms for computational geometry problems that are too large to be
  solved in internal memory, and we use these techniques to develop optimal and
  practical algorithms for a number of important large-scale problems in
  computational geometry. Our algorithms are optimal for a wide range of
  two-level and hierarchical multilevel memory models, including parallel
  models. The algorithms are optimal in terms of both I/O cost and internal
  computation. \par Our results are built on four fundamental techniques: {\it
  distribution sweeping}, a generic method for externalizing plane-sweep
  algorithms; {\it persistent B-trees}, for which we have both on-line and
  off-line methods; {\it batch filtering}, a general method for performing $K$
  simultaneous external-memory searches in any data structure that can be
  modeled as a planar layered dag; and {\it external marriage-before-conquest},
  an external-memory analog of the well-known technique of Kirkpatrick and
  Seidel. Using these techniques we are able to solve a very large number of
  problems in computational geometry, including batched range queries, 2-d and
  3-d convex hull construction, planar point location, range queries, finding
  all nearest neighbors for a set of planar points, rectangle
  intersection/union reporting, computing the visibility of segments from a
  point, performing ray-shooting queries in constructive solid geometry (CSG)
  models, as well as several geometric dominance problems. \par These results
  are significant because large-scale problems involving geometric data are
  ubiquitous in spatial databases, geographic information systems (GIS),
  constraint logic programming, object oriented databases, statistics, virtual
  reality systems, and graphics. This work makes a big step, both theoretically
  and in practice, towards the effective management and manipulation of
  geometric data in external memory, which is an essential component of these
  applications.}
}