I/O-efficient algorithms for contour-line extraction and planar graph blocking

Journal Article

For a polyhedral terrain Σ, the contour at z-coordinate h, denoted C , is defined to be the intersection of the plane z = h with Σ. In this paper, we study the contour-line extraction problem, where we want to preprocess Σ into a data structure so that given a query z-coordinate h, we can report C 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 Σ 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 C can be computed using O(log N+|C |/B) I/O operations, where |C | denotes the size of C . We also present an 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 problems that arise in GIS. h h h B h h h

Duke Authors

Cited Authors

  • Agarwal, PK; Arge, L; Murali, TM; Varadarajan, KR; Vitter, JS

Published Date

  • December 1, 1998

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 117 - 126

Citation Source

  • Scopus