Loading...
I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking
Agarwal, Pankaj K. Arge, Lars Murali, T. M. Kasturi R., Varadarajan Vitter, Jeffrey Scott
Agarwal, Pankaj K.
Arge, Lars
Murali, T. M.
Kasturi R., Varadarajan
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
For a polyhedral terrain C, the contour at z-coordinate h, denoted Ch, is defined to be the intersection of the plane z = h with C. In this paper, we study the contour-line extraction problem, where we want to preprocess C into a data structure so that given a query z-coordinate h, we can report Ch quickly. This is a central problem that arises in geographic information systems (GIS), where terrains are often stored as Triangular Irregular Networks (TINS). We present an I/O-optimal algorithm for this problem which stores a terrain C with N vertices using O(N/B) blocks, where B is the size of a disk block, so that for any query h, the contour ch can be computed using o(log, N + I&l/B) I/O operations, where l&l denotes the size of Ch.
We also present en improved algorithm for a more general problem of blocking bounded-degree planar graphs such as TINS (i.e., storing them on disk so that any graph traversal algorithm can traverse the graph in an I/O-efficient manner), and apply it to two problms that arise in GIS.
Description
Date
1998
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Files
Loading...
vitter_1998.pdf
Adobe PDF, 1.8 MB
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
P. K. Agarwal, L. Arge, T. M. Murali, K. R. Varadarajan, and J. S. Vitter. “I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking,” Proceedings of the 9th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA ’98), San Francisco, CA, January 1998, 117–126.