I/O-Efficient Algorithms for Computing Contour Lines on a Terrain
Bardia Sadri, Duke University
February 22, 2008, 3:30PM, Wean 7220

Abstract:
A terrain \Sigma is the graph of a bivariate function. We assume that \Sigma is represented as a triangulated surface with n vertices. A contour (or contour line) of \Sigma is a connected component of a level set of \Sigma. Generically, each contour is a closed polygonal curve; at “critical”' levels these curves may touch each other. We present I/O-efficient algorithms for the following two problems related to computing contours of \Sigma:

Given two real parameters h and d > 0, we present an I/O-optimal algorithm that report all contours of \Sigma at heights h + kd, for every positive integer k, 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 order. Moreover, our algorithm generates information on how the contours are nested.

We can preprocess \Sigma, 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 order.

This is a joint work with Lars Arge, Pankaj K. Agarwal, and Thomas Moelhave.