Math @ Duke

Publications [#235601] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Murali, TM; Varadarajan, KR; Vitter, JS, I/Oefficient algorithms for contourline extraction and planar graph blocking,
in Ninth Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(1998),
pp. 117126
(last updated on 2018/03/21)
Abstract: For a polyhedral terrain Σ, the contour at zcoordinate h, denoted Ch, is defined to be the intersection of the plane z = h with Σ. In this paper, we study the contourline extraction problem, where we want to preprocess Σ into a data structure so that given a query zcoordinate 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/Ooptimal 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 boundeddegree planar graphs such as TINs (i.e., storing them on disk so that any graph traversal algorithm can traverse the graph in an I/Oefficient manner), and apply it to two problems that arise in GIS.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

