Simplifying massive planar subdivisions

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

Standard

Simplifying massive planar subdivisions. / Arge, Lars; Truelsen, Jakob; Yang, Jungwoo.

2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) . ed. / Catherine C. McGeoch; Ulrich Meyer. Society for Industrial and Applied Mathematics, 2014. p. 20-30.

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

Harvard

Arge, L, Truelsen, J & Yang, J 2014, Simplifying massive planar subdivisions. in CC McGeoch & U Meyer (eds), 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) . Society for Industrial and Applied Mathematics, pp. 20-30, Portland, United States, 05/01/2014. https://doi.org/10.1137/1.9781611973198.3

APA

Arge, L., Truelsen, J., & Yang, J. (2014). Simplifying massive planar subdivisions. In C. C. McGeoch, & U. Meyer (Eds.), 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 20-30). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973198.3

CBE

Arge L, Truelsen J, Yang J. 2014. Simplifying massive planar subdivisions. McGeoch CC, Meyer U, editors. In 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) . Society for Industrial and Applied Mathematics. pp. 20-30. https://doi.org/10.1137/1.9781611973198.3

MLA

Arge, Lars, Jakob Truelsen and Jungwoo Yang "Simplifying massive planar subdivisions". and McGeoch, Catherine C. Meyer, Ulrich (editors). 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) . Society for Industrial and Applied Mathematics. 2014, 20-30. https://doi.org/10.1137/1.9781611973198.3

Vancouver

Arge L, Truelsen J, Yang J. Simplifying massive planar subdivisions. In McGeoch CC, Meyer U, editors, 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) . Society for Industrial and Applied Mathematics. 2014. p. 20-30 https://doi.org/10.1137/1.9781611973198.3

Author

Arge, Lars ; Truelsen, Jakob ; Yang, Jungwoo. / Simplifying massive planar subdivisions. 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) . editor / Catherine C. McGeoch ; Ulrich Meyer. Society for Industrial and Applied Mathematics, 2014. pp. 20-30

Bibtex

@inproceedings{d80b65a3c3724bfe9c09084eb7459608,
title = "Simplifying massive planar subdivisions",
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",
author = "Lars Arge and Jakob Truelsen and Jungwoo Yang",
note = "This paper summarizes the results obtained in the M.Sc. thesis by the first two author",
year = "2014",
doi = "10.1137/1.9781611973198.3",
language = "English",
pages = "20--30",
editor = "{ McGeoch}, {Catherine C. } and { Meyer}, {Ulrich }",
booktitle = "2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX)",
publisher = "Society for Industrial and Applied Mathematics",

}

RIS

TY - GEN

T1 - Simplifying massive planar subdivisions

AU - Arge, Lars

AU - Truelsen, Jakob

AU - Yang, Jungwoo

N1 - This paper summarizes the results obtained in the M.Sc. thesis by the first two author

PY - 2014

Y1 - 2014

N2 - 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

AB - 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

U2 - 10.1137/1.9781611973198.3

DO - 10.1137/1.9781611973198.3

M3 - Article in proceedings

SP - 20

EP - 30

BT - 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX)

A2 - McGeoch, Catherine C.

A2 - Meyer, Ulrich

PB - Society for Industrial and Applied Mathematics

ER -