@Article{arge:jsegments,
  author = {Lars Arge and Darren Erik Vengroff and Jeffrey Scott Vitter},
  title = {External-Memory Algorithms for Processing Line Segments in
  Geographic Information Systems},
  journal = {Algorithmica},
  year = {1998},
  note = {To appear},
  earlier = {arge:segments},
  URL = {ftp://cs.duke.edu/pub/jsv/Papers/AVV97.SegmentGIS.ps.gz},
  keywords = {verify, out-of-core algorithm, computational geometry,
  pario-bib},
  abstract = {We present a set of algorithms designed to solve large-scale
  geometric problems involving collections of line segments in the plane.
  Geographical information systems (GIS) handle large amounts of spatial data,
  and at some level the data is often manipulated as collections of line
  segments. NASA's EOS project is an example of a GIS that is expected to store
  and manipulate petabytes (thousands of terabytes, or millions of gigabytes)
  of data! In the design of algorithms for this type of large-scale
  application, it is essential to consider the problem of minimizing I/O
  communication, which is the bottleneck. \par In this paper we develop
  efficient new external-memory algorithms for a number of important problems
  involving line segments in the plane, including trapezoid decomposition,
  batched planar point location, triangulation, red-blue line segment
  intersection reporting, and general line segment intersection reporting. In
  GIS systems, the first three problems are useful for rendering and modeling,
  and the latter two are frequently used for overlaying maps and extracting
  information from them. To solve these problems, we combine and modify in
  novel ways several of the previously known techniques for designing efficient
  algorithms for external memory. We also develop a powerful new technique that
  can be regarded as a practical external memory version of fractional
  cascading. Except for the batched planar point location problem, no
  algorithms specifically designed for external memory were previously known
  for these problems. Our algorithms for triangulation and line segment
  intersection partially answer previously posed open problems, while the
  batched planar point location algorithm improves on the previously known
  solution, which applied only to monotone decompositions. Our algorithm for
  the red-blue line segment intersection problem is provably optimal.},
  comment = {Special issue on cartography and geographic information systems.}
}