Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.26
URN: urn:nbn:de:0030-drops-144666
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14466/
Buchin, Kevin ; Löffler, Maarten ; Popov, Aleksandr ; Roeloffzen, Marcel
Uncertain Curve Simplification
| pdf-format: |
|
Abstract
We study the problem of polygonal curve simplification under uncertainty, where instead of a sequence of exact points, each uncertain point is represented by a region which contains the (unknown) true location of the vertex. The regions we consider are disks, line segments, convex polygons, and discrete sets of points. We are interested in finding the shortest subsequence of uncertain points such that no matter what the true location of each uncertain point is, the resulting polygonal curve is a valid simplification of the original polygonal curve under the Hausdorff or the Fréchet distance. For both these distance measures, we present polynomial-time algorithms for this problem.
BibTeX - Entry
@InProceedings{buchin_et_al:LIPIcs.MFCS.2021.26,
author = {Buchin, Kevin and L\"{o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel},
title = {{Uncertain Curve Simplification}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {26:1--26:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-201-3},
ISSN = {1868-8969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14466},
URN = {urn:nbn:de:0030-drops-144666},
doi = {10.4230/LIPIcs.MFCS.2021.26},
annote = {Keywords: Curves, Uncertainty, Simplification, Fr\'{e}chet Distance, Hausdorff Distance}
}
| Keywords: | Curves, Uncertainty, Simplification, Fréchet Distance, Hausdorff Distance | |
| Seminar: | 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 18.08.2021 |
