Aarhus University Seal / Aarhus Universitets segl

Lars Arge

I/O-Efficient Algorithms for Computing Contour Lines on a Terrain

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Pankaj Kumar Agarwal, Duke University, United States
  • Lars Arge
  • Bardia Sadri, Duke University, United States
  • Thomas Mølhave, Denmark
  • Department of Computer Science

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/O efficient algorithms for the following two problems related to computing contours of M:

  1. (i) Given a sequence l1 < ... < ls of real numbers, we present an I/O-optimal algorithm that reports all contours of M at heights l1 , ... , ls 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.
  2. (ii) We can preprocess M, using O(sort(N)) I/Os, into a linear-size 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.
Original languageEnglish
Title of host publicationProceedings of the twenty-fourth annual symposium on Computational geometry
EditorsMonique Teilaud
Number of pages10
PublisherAssociation for Computing Machinery
Publication year2008
ISBN (print)978-1-60558-071-5
Publication statusPublished - 2008
EventACM Symposium on Computational Geometry - University of Maryland, United States
Duration: 9 Jun 200811 Jun 2008
Conference number: 24


ConferenceACM Symposium on Computational Geometry
LandUnited States
ByUniversity of Maryland

    Research areas

  • contours, geographical information systems, i/o-efficient algorithms, terrains

See relations at Aarhus University Citationformats

ID: 10411069