Lars Arge, Pankaj K. Agarwal, Thomas Mølhave, and Bardia Sadri

A terrain ∑ is the graph of a bivariate function. We assume that ∑ is represented as a triangulated surface with
n vertices. A contour (or contour line) of ∑ is a connected component of a level set of ∑. 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 ∑:

Given two real parameters h and d > 0, we present an I/O-optimal algorithm that report all contours of ∑ 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 ∑, 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(log_B N + T/B) I/Os, where T is the output size.  Each contour is generated individually with its composing segments sorted in clockwise order.Symposium on

Computational Geometry (SoCG), 2008 [PDF]
SoCG presentation slides [PDF]
Longer version slides [PDF]