I/O-efficient algorithms for contour-line extraction and planar graph blocking (Extended Abstract)

For a polyhedral terrain, the contour at z-coordinate h, denoted Ch, is de ned to be the intersection of the plane z = h with. In this paper, we study the contour-line extraction problem, where we want to preprocess into a data structure so that given a query z-coordinate h, we can report Ch quickly. This is a central problem that arises in geographic information systems (GIS), where terrains are often stored as Triangular Irregular Networks (TINs). We present an I/O-optimal algorithm for this problem which stores a terrain with N vertices using O(N=B) blocks, where B is the size of a disk block, so that for any query h, the contour Ch can be computed using O(logB N + jCh j=B) I/O operations, where jChj denotes the size of Ch. We also present an improved algorithm for a more general problem of blocking bounded-degree planar graphs such as TINs (i.e., storing them on disk so that any graph traversal algorithm can traverse the graph in an I/O-e cient manner), and apply it to two problms that arise in GIS