Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves

K.A. Buchin; J. Chun; A. Markovic; W. Meulemans; M. Löffler; Y. Okamoto; T. Shiitada

doi:10.4230/LIPIcs.SoCG.2017.64

Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves

K.A. Buchin, J. Chun, A. Markovic, W. Meulemans, M. Löffler, Y. Okamoto, T. Shiitada

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

7 Citations (Scopus)

205 Downloads (Pure)

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 curve has ply k.

Original language	English
Title of host publication	33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia
Editors	Matthew J. Katz, Boris Aronov
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	641-645
Number of pages	5
ISBN (Electronic)	9783959770385
ISBN (Print)	978-3-95977-038-5
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2017.64
Publication status	Published - 2017
Event	33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australia Duration: 4 Jul 2017 → 7 Jul 2017 Conference number: 33 http://socg2017.smp.uq.edu.au/socg.html http://socg2017.smp.uq.edu.au/index.html

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	77
ISSN (Print)	1868-8969

Conference

Conference	33rd International Symposium on Computational Geometry (SoCG 2017)
Abbreviated title	SoCG 2017
Country/Territory	Australia
City	Brisbane
Period	4/07/17 → 7/07/17
Other	The Computational Geometry Week (CG Week 2017) is the premier international forum for advances in computational geometry and its many applications. The next edition will take place in Brisbane, Australia, July 4-7, 2017. CG week combines a number of events, most notably the 33rd International Symposium on Computational Geometry (SoCG 2017), the associated multimedia exposition, workshops, and the Young Researchers Forum.
Internet address	http://socg2017.smp.uq.edu.au/socg.html http://socg2017.smp.uq.edu.au/index.html

Keywords

Fréchet distance
K-packed curves
Ply

Access to Document

10.4230/LIPIcs.SoCG.2017.64

publishers versionFinal published version, 411 KB

Cite this

Buchin, K. A., Chun, J., Markovic, A., Meulemans, W., Löffler, M., Okamoto, Y., & Shiitada, T. (2017). Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves. In M. J. Katz, & B. Aronov (Eds.), 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia (pp. 641-645). Article 64 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 77). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.64

Buchin, K.A. ; Chun, J. ; Markovic, A. et al. / Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves. 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia. editor / Matthew J. Katz ; Boris Aronov. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. pp. 641-645 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{e7d21589be6e466db95bfa319110e9c3,

title = "Folding free-space diagrams : computing the Fr{\'e}chet distance between 1-dimensional curves",

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 curve has ply k.",

keywords = "Fr{\'e}chet distance, K-packed curves, Ply",

author = "K.A. Buchin and J. Chun and A. Markovic and W. Meulemans and M. L{\"o}ffler and Y. Okamoto and T. Shiitada",

year = "2017",

doi = "10.4230/LIPIcs.SoCG.2017.64",

language = "English",

isbn = "978-3-95977-038-5",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "641--645",

editor = "Katz, {Matthew J.} and Boris Aronov",

booktitle = "33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia",

note = "33rd International Symposium on Computational Geometry (SoCG 2017), SoCG 2017 ; Conference date: 04-07-2017 Through 07-07-2017",

url = "http://socg2017.smp.uq.edu.au/socg.html, http://socg2017.smp.uq.edu.au/index.html",

}

Buchin, KA, Chun, J, Markovic, A, Meulemans, W, Löffler, M, Okamoto, Y & Shiitada, T 2017, Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves. in MJ Katz & B Aronov (eds), 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia., 64, Leibniz International Proceedings in Informatics, LIPIcs, vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, pp. 641-645, 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Queensland, Australia, 4/07/17. https://doi.org/10.4230/LIPIcs.SoCG.2017.64

Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves. / Buchin, K.A.; Chun, J.; Markovic, A. et al.
33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia. ed. / Matthew J. Katz; Boris Aronov. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. p. 641-645 64 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 77).

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

TY - GEN

T1 - Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves

AU - Buchin, K.A.

AU - Chun, J.

AU - Markovic, A.

AU - Meulemans, W.

AU - Löffler, M.

AU - Okamoto, Y.

AU - Shiitada, T.

N1 - Conference code: 33

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 curve 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 curve has ply k.

KW - Fréchet distance

KW - K-packed curves

KW - Ply

UR - http://www.scopus.com/inward/record.url?scp=85029950689&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2017.64

DO - 10.4230/LIPIcs.SoCG.2017.64

M3 - Conference contribution

SN - 978-3-95977-038-5

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 641

EP - 645

BT - 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia

A2 - Katz, Matthew J.

A2 - Aronov, Boris

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

T2 - 33rd International Symposium on Computational Geometry (SoCG 2017)

Y2 - 4 July 2017 through 7 July 2017

ER -

Buchin KA, Chun J, Markovic A, Meulemans W, Löffler M, Okamoto Y et al. Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves. In Katz MJ, Aronov B, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), 4-7 July 2017, Brisbane, Australia. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2017. p. 641-645. 64. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.SoCG.2017.64

Folding free-space diagrams : computing the Fréchet distance between 1-dimensional curves

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this