Global curve simplification

Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, Carola Wenk

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
96 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publicationProc. 27th Annual European Symposium on Algorithms (ESA)
EditorsMichael A. Bender, Ola Svensson, Grzegorz Herman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages14
ISBN (Electronic)9783959771245
DOIs
Publication statusPublished - Sep 2019
Event27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany
Duration: 9 Sep 201911 Sep 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume144
ISSN (Print)1868-8969

Conference

Conference27th Annual European Symposium on Algorithms, ESA 2019
Country/TerritoryGermany
CityMunich/Garching
Period9/09/1911/09/19

Keywords

  • Curve simplification
  • Fréchet distance
  • Hausdorff distance
  • Frechet distance

Fingerprint

Dive into the research topics of 'Global curve simplification'. Together they form a unique fingerprint.

Cite this