Computing the Fréchet distance between simple polygons

K. Buchin; M. Buchin; C. Wenk

doi:10.1016/j.comgeo.2007.08.003

Computing the Fréchet distance between simple polygons

K. Buchin, M. Buchin, C. Wenk

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

33 Citaten (Scopus)

Samenvatting

We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves, which may lie in different planes. For this, we show that we can restrict the set of maps realizing the Fréchet distance, and develop an algorithm for computing the Fréchet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming.

Originele taal-2	Engels
Pagina's (van-tot)	2-20
Tijdschrift	Computational Geometry
Volume	41
Nummer van het tijdschrift	1-2
DOI's	https://doi.org/10.1016/j.comgeo.2007.08.003
Status	Gepubliceerd - 2008

Toegang tot document

10.1016/j.comgeo.2007.08.003

Vingerafdruk Duik in de onderzoeksthema's van 'Computing the Fréchet distance between simple polygons'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

@article{7955db24f92f496dbc11f55aab815c10,

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

abstract = "We present the first polynomial-time algorithm for computing the Fr{\'e}chet distance for a non-trivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves, which may lie in different planes. For this, we show that we can restrict the set of maps realizing the Fr{\'e}chet distance, and develop an algorithm for computing the Fr{\'e}chet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming.",

author = "K. Buchin and M. Buchin and C. Wenk",

year = "2008",

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

language = "English",

volume = "41",

pages = "2--20",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier",

number = "1-2",

}

TY - JOUR

T1 - Computing the Fréchet distance between simple polygons

AU - Buchin, K.

AU - Buchin, M.

AU - Wenk, C.

PY - 2008

Y1 - 2008

N2 - We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves, which may lie in different planes. For this, we show that we can restrict the set of maps realizing the Fréchet distance, and develop an algorithm for computing the Fréchet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming.

AB - We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves, which may lie in different planes. For this, we show that we can restrict the set of maps realizing the Fréchet distance, and develop an algorithm for computing the Fréchet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming.

U2 - 10.1016/j.comgeo.2007.08.003

DO - 10.1016/j.comgeo.2007.08.003

M3 - Article

VL - 41

SP - 2

EP - 20

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 1-2

ER -