Logo der Fakultät Logo LG Theoretische Informatik
 

Veröffentlichung

Titel:

Fine-Grained Analysis of Problems on Curves

AutorInnen: Kevin Buchin
Maike Buchin
Wolfgang Mulzer
Maximilian Konzack
André Schulz
Kategorie: Konferenzbandbeiträ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: pdf
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.} }
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen