Math @ Duke

Publications [#235537] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; MÃ¸lhave, T; Sadri, B, I/Oefficieiit contour queries on terrains,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2011),
pp. 268284
(last updated on 2018/07/22)
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 levelset 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/Oefficient 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 277080320

