Folding Free-Space Diagrams

By folding the free-space diagram for efficient preprocessing, we show that the Fréchet distance between 1D curves can be computed in O(nklogn) time, assuming one of the curves has ply k.

keywords: Computational Geometry, Graphs Theory, Trajectories

Workshop or Poster (weakly reviewed)

Aleksandar Markovic, Jinhee Chun, Kevin Buchin, Maarten Löffler, Taichi Shiitada, Wouter Meulemans, Yoshio Okamoto
Folding Free-Space Diagrams
Proc. 32nd Symposium on Computational Geometry
(to appear), 2017

back to list