I/o-efficient efficient algorithms for computing contours on a terrain

ABSTRACT

A terrain M is the graph of a bivariate function. We assume that M is represented as a triangulated surface with N vertices. A contour (or isoline) of M is a connected component of a level set of M. Generically, each contour is a closed polygonal curve; at "critical" levels these curves may touch each other or collapse to a point. We present I/O efficient algorithms for the following two problems related to computing contours of M:

1. (i) Given a sequence l₁ < ... < l_s of real numbers, we present an I/O-optimal algorithm that reports all contours of M at heights l₁ , ... , l_s 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 or counterclockwise order. Moreover, our algorithm generates information on how the contours are nested.
2. (ii) We can preprocess M, 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 or counterclockwise order.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , T. M. Murali , Kasturi R. Varadarajan , Jeffrey Scott Vitter, I/O-efficient algorithms for contour-line extraction and planar graph blocking, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.117-126, January 25-27, 1998, San Francisco, California, United States
• 2: Pankaj K. Agarwal , Lars Arge , Ke Yi, I/O-efficient batched union-find and its applications to terrain analysis, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137884]
• 3: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 4: Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 5: L. Arge, The buffer tree: A technique for designing batched external data structures, Algorithmica, 37 (2003), 1--24.
• 6: L. Arge, A. Danner, and S.-H. Teh, I/O-efficient point location using persistent B-trees, Proc. Workshop on Algorithm Engineering and Experimentation, 2003.
• 7: L. Arge, K. H. Hinrichs, J. Vahrenhold, and J. S. Vitter, Efficient bulk operations on dynamic R-trees, Algorithmica, 33 (2002), 104--128.
• 8: Lars Arge , Laura Toma , Norbert Zeh, I/O-efficient topological sorting of planar DAGs, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777427]
• 9: Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Computational Geometry: Theory and Applications, v.24 n.2, p.75-94, February 2003 [doi>10.1016/S0925-7721(02)00093-7]
• 10: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 11: Yi-Jen Chiang , Cláudio T. Silva, I/O optimal isosurface extraction (extended abstract), Proceedings of the 8th conference on Visualization '97, p.293-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 12: Andrew Danner , Thomas Mølhave , Ke Yi , Pankaj K. Agarwal , Lars Arge , Helena Mitasova, TerraStream: from elevation data to watershed hierarchies, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington [doi>10.1145/1341012.1341049]
• 13: H. Edelsbrunner, D. Letscher, and A. Zomorodian, Topological persistence and simplification, Discrete Comput. Geom., 28 (2002), pp. 511--533.
• 14: I. Fáry, On straight lines representation of planar graphs, Acta Sci. Math. Szeged, 11 (1948), 229--233.
• 15: Martin Isenburg , Yuanxin Liu , Jonathan Shewchuk , Jack Snoeyink, Streaming computation of Delaunay triangulations, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 16: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 17: M. H. Nodine, M. T. Goodrich, and J. S. Vitter, Blocking for external graph searching, Algorithmica, 16 (1996), 181--214.
• 18: C. Silva, Y. Chiang, J. El-Sana, and P. Lindstrom, Out-of-core algorithms for scientific visualization and computer graphics, Visualization'02, 2002. Course Notes for Tutorial 4.
• 19: R. A. Skelton, Cartography, History of Technology, 6 (1958), 612--614.
• 20: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 21: Marc van Kreveld , René van Oostrum , Chandrajit Bajaj , Valerio Pascucci , Dan Schikore, Contour trees and small seed sets for isosurface traversal, Proceedings of the thirteenth annual symposium on Computational geometry, p.212-220, June 04-06, 1997, Nice, France [doi>10.1145/262839.269238]
• 22: Peter J. Varman , Rakesh M. Verma, An Efficient Multiversion Access Structure, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.391-409, May 1997 [doi>10.1109/69.599929]
• 23: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
contours, geographical information systems, i/o-efficient algorithms, terrains