Conference proceeding
I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking
SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp.117-126
01/1998
DOI: 10.5555/314613.314691
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.
Details
- Title: Subtitle
- I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking
- Creators
- Pankaj K AgarwalLars ArgeT. M MuraliKasturi R VaradarajanJeffrey Scott Vitter
- Resource Type
- Conference proceeding
- Publication Details
- SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp.117-126
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.5555/314613.314691
- Language
- English
- Date published
- 01/1998
- Academic Unit
- Computer Science
- Record Identifier
- 9984259496102771
Metrics
2 Record Views