Aarhus University Seal / Aarhus Universitets segl

Lars Arge

I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Pankaj K. Agarwal, Duke University, United States
  • Lars Allan Arge
  • Ke Yi, Hong Kong University of Science and Technology, China
  • Department of Computer Science
In this article we present an I/O-efficient algorithm for the batched (off-line) version of the union-find problem. Given any sequence of N union and find operations, where each union operation joins two distinct sets, our algorithm uses O(SORT(N)) = O(&frac;NB logM/B&frac;NB) I/Os, where M is the memory size and B is the disk block size. This bound is asymptotically optimal in the worst case. If there are union operations that join a set with itself, our algorithm uses O(SORT(N) + MST(N)) I/Os, where MST(N) is the number of I/Os needed to compute the minimum spanning tree of a graph with N edges. We also describe a simple and practical O(SORT(N) log(&frac;NM))-I/O algorithm for this problem, which we have implemented.

We are interested in the union-find problem because of its applications in terrain analysis. A terrain can be abstracted as a height function defined over R2, and many problems that deal with such functions require a union-find data structure. With the emergence of modern mapping technologies, huge amount of elevation data is being generated that is too large to fit in memory, thus I/O-efficient algorithms are needed to process this data efficiently. In this article, we study two terrain-analysis problems that benefit from a union-find data structure: (i) computing topological persistence and (ii) constructing the contour tree. We give the first O(SORT(N))-I/O algorithms for these two problems, assuming that the input terrain is represented as a triangular mesh with N vertices.
Original languageEnglish
JournalA C M Transactions on Algorithms
Volume7
Issue1
Pages (from-to)Article 11
Number of pages21
ISSN1549-6325
DOIs
Publication statusPublished - 2010

See relations at Aarhus University Citationformats

ID: 22380187