Folding Free-Space Diagrams

Kevin Buchin; Jinhee Chun; Maarten Löffler; Aleksandar Markovic; Wouter Meulemans; Yoshio Okamoto; Taichi Shiitada

Folding Free-Space Diagrams

Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, Taichi Shiitada

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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

Original language	English
Title of host publication	Proc. 32nd Symposium on Computational Geometry
Publication status	Published - 2017

Keywords

CG, GRAPH, TRAJ

Cite this

@inproceedings{4ece39bea46c4cfc848175295ec5d6d8,

title = "Folding Free-Space Diagrams",

abstract = "By folding the free-space diagram for efficient preprocessing, we show that the Fr{\'e}chet distance between 1D curves can be computed in $O(nk log n)$ time, assuming one of the curves has ply $k$.",

keywords = "CG, GRAPH, TRAJ",

author = "Kevin Buchin and Jinhee Chun and Maarten L{\"o}ffler and Aleksandar Markovic and Wouter Meulemans and Yoshio Okamoto and Taichi Shiitada",

note = "(to appear)",

year = "2017",

language = "English",

booktitle = "Proc. 32nd Symposium on Computational Geometry",

}

TY - GEN

T1 - Folding Free-Space Diagrams

AU - Buchin, Kevin

AU - Chun, Jinhee

AU - Löffler, Maarten

AU - Markovic, Aleksandar

AU - Meulemans, Wouter

AU - Okamoto, Yoshio

AU - Shiitada, Taichi

N1 - (to appear)

PY - 2017

Y1 - 2017

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

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

KW - CG, GRAPH, TRAJ

M3 - Conference contribution

BT - Proc. 32nd Symposium on Computational Geometry

ER -

Folding Free-Space Diagrams

Abstract

Keywords

Fingerprint

Cite this