I/O-efficieiit contour queries on terrains


Journal Article

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(logBN + 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.

Duke Authors

Cited Authors

  • Agarwal, PK; Mølhave, T; Sadri, B

Published Date

  • May 12, 2011

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 268 - 284

Citation Source

  • Scopus