2026-07-22T08:26:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11188 2024-03-06T10:47:40Z ddc:004 open_access

Global Curve Simplification van de Kerkhof, Mees Kostitsyna, Irina Löffler, Maarten Mirzanezhad, Majid Wenk, Carola Curve simplification Fréchet distance Hausdorff distance Due to its many applications, curve simplification is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve P with n vertices, the goal is to find another polygonal curve P' with a smaller number of vertices such that P' is sufficiently similar to P. Quality guarantees of a simplification are usually given in a local sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work we aim to provide a systematic overview of curve simplification problems under global distance measures that bound the distance between P and P'. We consider six different curve distance measures: three variants of the Hausdorff distance and three variants of the Fréchet distance. And we study different restrictions on the choice of vertices for P'. We provide polynomial-time algorithms for some variants of the global curve simplification problem, and show NP-hardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mees van de Kerkhof and Irina Kostitsyna and Maarten Löffler and Majid Mirzanezhad and Carola Wenk 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.67 urn:nbn:de:0030-drops-111887 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.67 eng https://creativecommons.org/licenses/by/3.0/legalcode