Aarhus University Seal

On the Scalability of Computing Triplet and Quartet Distances

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

We present the first I/O- and practically-efficient algorithm for simplifying a planar subdivision, such that no point is moved more than a given distance εxy and such that neighbor relations between faces (homotopy) are preserved. Under some practically realistic assumptions, our algorithm uses (SORT(N)) I/Os, where N is the size of the decomposition and SORT(N) is the number of I/Os need to sort in the standard external-memory model of computation. Previously, such an algorithm was only known for the special case of contour map simplification.

Our algorithm is simple enough to be of practical interest. In fact, although more general, it is significantly simpler than the previous contour map simplification algorithm. We have implemented our algorithm and present results of experimenting with it on massive real-life data. The experiments confirm that the algorithm is efficient in practice. For example, for the contour map simplification problem it is significantly faster than the previous algorithm, while obtaining approximately the same simplification factor.

Read More: http://epubs.siam.org/doi/abs/10.1137/1.9781611973198.3
Original languageEnglish
Title of host publication2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX)
EditorsCatherine C. McGeoch, Ulrich Meyer
Number of pages11
PublisherSociety for Industrial and Applied Mathematics
Publication year2014
ISBN (Electronic)978-1-61197-319-8
Publication statusPublished - 2014
EventWorkshop on Algorithm Engineering and Experiments - Portland, United States
Duration: 5 Jan 20145 Jan 2014
Conference number: 16


WorkshopWorkshop on Algorithm Engineering and Experiments
LandUnited States

See relations at Aarhus University Citationformats

ID: 81804620