I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking

P. K. Agarwal, L. Arge, T. M. Murali, K. R. Varadarajan, and J. S. Vitter. ``I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking,'' Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '98), San Francisco, CA, January 1998.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

For a polyhedral terrain, the contour at z-coordinate h is defined to be the intersection of the plane z = h with the terrain. In this paper, we study the contour-line extraction problem, where we want to preprocess the terrain into a data structure so that given a query z-coordinate h, we can report the h-contour quickly. This problem is central to 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 h-contour can be computed using $O(\log_B N + \vert C\vert/B)$ I/O operations, where |C| denotes the size of the h-contour. 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-efficient manner). We apply it to two problems that arise in GIS.