Computing the Fréchet distance between folded polygons

A.F. Cook IV; A. Driemel; J. Sherette; C. Wenk

doi:10.1016/j.comgeo.2015.08.002

Computing the Fréchet distance between folded polygons

A.F. Cook IV, A. Driemel, J. Sherette, C. Wenk

Data Mining

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

9 Citaten (Scopus)

Samenvatting

Computing the Fréchet distance for surfaces is a surprisingly hard problem and the only known polynomial-time algorithm is limited to computing it between flat surfaces. We study the problem of computing the Fréchet distance for a class of non-flat surfaces called folded polygons. We present a fixed-parameter tractable algorithm for this problem. Next, we present a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fréchet distance for L_8 in polynomial time. Keywords: Fréchet distance; Surface comparison; Folded polygons

Originele taal-2	Engels
Pagina's (van-tot)	1-16
Tijdschrift	Computational Geometry
Volume	50
Nummer van het tijdschrift	dec.
DOI's	https://doi.org/10.1016/j.comgeo.2015.08.002
Status	Gepubliceerd - 2015

Toegang tot document

10.1016/j.comgeo.2015.08.002

Citeer dit

@article{b3457f42bd214c82963fa89f660c6553,

title = "Computing the Fr{\'e}chet distance between folded polygons",

abstract = "Computing the Fr{\'e}chet distance for surfaces is a surprisingly hard problem and the only known polynomial-time algorithm is limited to computing it between flat surfaces. We study the problem of computing the Fr{\'e}chet distance for a class of non-flat surfaces called folded polygons. We present a fixed-parameter tractable algorithm for this problem. Next, we present a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fr{\'e}chet distance for L_8 in polynomial time. Keywords: Fr{\'e}chet distance; Surface comparison; Folded polygons",

author = "{Cook IV}, A.F. and A. Driemel and J. Sherette and C. Wenk",

year = "2015",

doi = "10.1016/j.comgeo.2015.08.002",

language = "English",

volume = "50",

pages = "1--16",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier",

number = "dec.",

}

TY - JOUR

T1 - Computing the Fréchet distance between folded polygons

AU - Cook IV, A.F.

AU - Driemel, A.

AU - Sherette, J.

AU - Wenk, C.

PY - 2015

Y1 - 2015

N2 - Computing the Fréchet distance for surfaces is a surprisingly hard problem and the only known polynomial-time algorithm is limited to computing it between flat surfaces. We study the problem of computing the Fréchet distance for a class of non-flat surfaces called folded polygons. We present a fixed-parameter tractable algorithm for this problem. Next, we present a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fréchet distance for L_8 in polynomial time. Keywords: Fréchet distance; Surface comparison; Folded polygons

AB - Computing the Fréchet distance for surfaces is a surprisingly hard problem and the only known polynomial-time algorithm is limited to computing it between flat surfaces. We study the problem of computing the Fréchet distance for a class of non-flat surfaces called folded polygons. We present a fixed-parameter tractable algorithm for this problem. Next, we present a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fréchet distance for L_8 in polynomial time. Keywords: Fréchet distance; Surface comparison; Folded polygons

U2 - 10.1016/j.comgeo.2015.08.002

DO - 10.1016/j.comgeo.2015.08.002

M3 - Article

SN - 0925-7721

VL - 50

SP - 1

EP - 16

JO - Computational Geometry

JF - Computational Geometry

IS - dec.

ER -

Computing the Fréchet distance between folded polygons

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit