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