I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking (Extended Abstract).
Pankaj Kumar Agarwal, Lars Arge, T. M. Murali, Kasturi Varadarajan, Jeffrey Scott Vitter · 1998
) Pankaj K. Agarwal Lars Arge y T. M. Murali z Kasturi R. Varadarajan x Jeffrey Scott Vitter -- Center for Geometric Computing Department of Computer Science Duke University Durham, NC 27708--0129 Abstract For a polyhedral terrain \\Sigma, the contour at z-coordinate h, denoted Ch , is defined to be the intersection of the plane z = h with \\Sigma. In this paper, we study the contour-line extraction problem, where we want to preprocess \\Sigma 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 \\Sigma 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(log B N + jCh j=B) I/O operations, where jCh j denotes the size of Ch . We also pr...