Open AccessExternal-Memory Algorithms for Processing Line Segments in Geographic Information Systems
Author(s) -
Lars Arge,
Darren Erik Vengroff,
Jeffrey Scott Vitter
Publication year - 1996
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v3i12.19975
Subject(s) - computer science , overlay , intersection (aeronautics) , rendering (computer graphics) , line segment , algorithm , triangulation , geographic information system , point location , line (geometry) , scale (ratio) , point (geometry) , artificial intelligence , mathematics , geometry , remote sensing , programming language , physics , quantum mechanics , geology , engineering , aerospace engineering
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.