@InProceedings{arge:segments,
  author = {Lars Arge and Darren Erik Vengroff and Jeffrey Scott Vitter},
  title = {External-Memory Algorithms for Processing Line Segments in
  Geographic Information Systems},
  booktitle = {Proceedings of the Third European Symposium on Algorithms},
  year = {1995},
  month = {September},
  series = {Lecture Notes in Computer Science},
  volume = {979},
  pages = {295--310},
  publisher = {Springer-Verlag},
  address = {Corfu, Greece},
  later = {arge:jsegments},
  URL = {ftp://cs.duke.edu/pub/jsv/Papers/AVV95.SegmentGIS.ps.Z},
  keywords = {out-of-core algorithm, computational geometry, pario-bib},
  abstract = {In the design of algorithms for large-scale applications it is
  essential to consider the problem of minimizing I/O communication.
  Geographical information systems (GIS) are good examples of such large-scale
  applications as they frequently handle huge amounts of spatial data. 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.},
  comment = {Does deal with parallel disks, though not in great detail.}
}