^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University^{3} Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1137/1.9781611973198.3

Abstract:

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

ISBN:

9781611973198

Type:

Conference paper

Language:

English

Published in:

2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (alenex), 2014, p. 20-30

Main Research Area:

Science/technology

Publication Status:

Published

Review type:

Peer Review

Conference:

Workshop on Algorithm Engineering and ExperimentsAlgorithm Engineering and Experimentation, 2014