External-Memory Algorithms for Processing Line Segments in Geographic Information Systems |
| |
Authors: | Lars Arge Darren Erik Vengroff Jeffrey Scott Vitter |
| |
Affiliation: | (1) Department of Computer Science, University of Aarhus, 8200, Aarhus N, Denmark;(2) Pelago, Inc., Seattle, WA 98118, USA;(3) Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA |
| |
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 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|