Veröffentlichung

Titel:

Fine-Grained Analysis of Problems on Curves

AutorInnen:

Kevin Buchin
Maike Buchin
Wolfgang Mulzer
Maximilian Konzack
André Schulz

Kategorie:

Workshopbeiträge

erschienen in:

Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16), Abstract

Abstract:

We provide conditional lower bounds on two
problems on polygonal curves. First, we
generalize a recent result on the (discrete) Fr\'echet
distance to $k$ curves. Specifically, we show that,
assuming the Strong Exponential Time Hypothesis,
the Fr\'echet distance between $k$ polygonal curves in the
plane with $n$ edges cannot be computed in $O(n^{k-\eps})$
time, for any $\eps > 0$. Our second construction shows that
under the same assumption a polygonal curve with $n$
edges in dimension $\Omega(\log n)$ cannot be simplified
optimally in $O(n^{2-\eps})$ time.

Download:

Proceedings Website

BibTeX-Eintrag:

@InProceedings{hkms-dttfg-eurocg16, Title = {Fine-Grained Analysis of Problems on Curves}, Author = {MKevin Buchin, Maike Buchin, Wolfgang Mulzer, Maximilian Konzack and Andr{\'e} Schulz}, Booktitle = {Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16)}, Year = {2016}, Editor = {Gill Barequet and Evanthia Papadopoulou}, Abstract={We provide conditional lower bounds on two problems on polygonal curves. First, we generalize a recent result on the (discrete) Fr\'echet distance to $k$ curves. Specifically, we show that, assuming the Strong Exponential Time Hypothesis, the Fr\'echet distance between $k$ polygonal curves in theplane with $n$ edges cannot be computed in $O(n^{k-\eps})$ time, for any $\eps > 0$. Our second construction shows that under the same assumption a polygonal curve with $n$ edges in dimension $\Omega(\log n)$ cannot be simplified optimally in $O(n^{2-\eps})$ time.} }