TY - GEN

T1 - Global curve simplification

AU - van de Kerkhof, Mees

AU - Kostitsyna, Irina

AU - Löffler, Maarten

AU - Mirzanezhad, Majid

AU - Wenk, Carola

PY - 2019/9

Y1 - 2019/9

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

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

KW - Curve simplification

KW - Fréchet distance

KW - Hausdorff distance

KW - Frechet distance

UR - http://www.scopus.com/inward/record.url?scp=85074836999&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2019.67

DO - 10.4230/LIPIcs.ESA.2019.67

M3 - Conference contribution

AN - SCOPUS:85074836999

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Proc. 27th Annual European Symposium on Algorithms (ESA)

A2 - Bender, Michael A.

A2 - Svensson, Ola

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 27th Annual European Symposium on Algorithms, ESA 2019

Y2 - 9 September 2019 through 11 September 2019

ER -