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 Ch, 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 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 Σ 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(logB N+|Ch|/B) I/O operations, where |Ch| denotes the size of Ch. 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.

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