Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235601] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Arge, L; Murali, TM; Varadarajan, KR; Vitter, JS, I/O-efficient algorithms for contour-line extraction and planar graph blocking, in Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1998), pp. 117-126
    (last updated on 2017/12/17)

    Abstract:
    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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320