Math @ Duke

Publications [#235508] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Moølhave, T; Sadri, B, I/Oefflcient algorithms for computing contours on a terrain,
Proceedings of the Annual Symposium on Computational Geometry
(2008),
pp. 129138 [doi]
(last updated on 2018/05/22)
Abstract: A terrain M is the graph of a bivariate function. We assume that M is represented as a triangulated surface with N vertices. A contour (or isoline) of M is a connected component of a level set of M. Generically, each contour is a closed polygonal curve; at "critical" levels these curves may touch each other or collapse to a point. We present I/Oefficient algorithms for the following two problems related to computing contours of M: (i) Given a sequence ℓ1 < ... < ℓs of real numbers, we present an I/Ooptimal algorithm that reports all contours of M at heights ℓ1,.. . ,ℓs using O(soRT(N) + T/B) I/Os, where T is the total number edges in the output contours, B is the "block size," and SORT(N) is the number of I/Os needed to sort N elements. The algorithm uses O(N/B) disk blocks. Each contour is generated individually with its composing segments sorted in clockwise or counterclockwise order. Moreover, our algorithm generates information on how the contours are nested. (ii) We can preprocess M, using O(SORT(N)) I/Os, into a linearsize data structure so that all contours at a given height can be reported using O(logB N + T/B) I/Os, where T is the output size. Each contour is generated individually with its composing segments sorted in clockwise or counterclockwise order. Copyright 2008 ACM.


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

