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

Math @ Duke





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

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


Publications [#235537] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Mølhave, T; Sadri, B, I/O-efficieiit contour queries on terrains, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2011), pp. 268-284
    (last updated on 2017/12/15)

    Abstract:
    A terrain M can be represented as a triangulation of the plane along with a height function associated with the vertices (and linearly interpolated within the edges and triangles) of M. We investigate the problem of answering contour queries on M: Given a height l aud a triangle of M that intersects the level set of M at height l, report the list of the edges of the connected component of this level set that intersect f, sorted in clockwise or counterclockwise order. Contour queries are different from level-set queries in that only one contour (connected component of the level set) out of all those that may exist is expected to be reported. We present an I/O-efficient data structure of linear size that answers a contour query in 0(logB N + T/B) I/Os, where N is the number of triangles in the terrain and T is the number of edges in the output contour. The data structure can be constructed using O(Sort(N)) I/Os.

 

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

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