License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14466/
Go to the corresponding LIPIcs Volume Portal

Buchin, Kevin ; Löffler, Maarten ; Popov, Aleksandr ; Roeloffzen, Marcel

Uncertain Curve Simplification

pdf-format:
LIPIcs-MFCS-2021-26.pdf (1.0 MB)

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
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI