I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking

View/ Open
Issue Date
1998Author
Agarwal, Pankaj K.
Arge, Lars
Murali, T. M.
Kasturi R., Varadarajan
Vitter, Jeffrey Scott
Publisher
Society for Industrial and Applied Mathematics
Type
Article
Article Version
Scholarly/refereed, publisher version
Published Version
http://portal.acm.org/citation.cfm?id=314691Metadata
Show full item recordAbstract
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.
Collections
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.
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.