Global curve simplification

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)
125 Downloads (Pure)


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.

Originele taal-2Engels
TitelProc. 27th Annual European Symposium on Algorithms (ESA)
RedacteurenMichael A. Bender, Ola Svensson, Grzegorz Herman
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's14
ISBN van elektronische versie9783959771245
StatusGepubliceerd - sep 2019
Evenement27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Duitsland
Duur: 9 sep 201911 sep 2019

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
ISSN van geprinte versie1868-8969


Congres27th Annual European Symposium on Algorithms, ESA 2019


Duik in de onderzoeksthema's van 'Global curve simplification'. Samen vormen ze een unieke vingerafdruk.

Citeer dit