Computing the Frechet distance between simple polygons

被引：39

作者：

Buchin, Kevin ^{[1
]}

Buchin, Maike ^{[1
]}

Wenk, Carola ^{[2
]}

机构：

[1] Free Univ Berlin, Inst Comp Sci, D-14195 Berlin, Germany

[2] Univ Texas San Antonio, Dept Comp Sci, San Antonio, TX 78249 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2008年 / 41卷 / 1-2期

关键词：

shape matching; Frechet distance; simple polygons;

D O I：

10.1016/j.comgeo.2007.08.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present the first polynomial-time algorithm for computing the Frechet 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 Frechet distance, and develop an algorithm for computing the Frechet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming. (c) 2008 Elsevier B.V. All rights reserved.

引用

页码：2 / 20

页数：19

共 20 条

[1] APPROXIMATE MATCHING OF POLYGONAL SHAPES [J].

ALT, H ;

BEHRENDS, B ;

BLOMER, J .

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 1995, 13 (3-4) :251-265

[2] Comparison of distance measures for planar curves [J].

Alt, H ;

Knauer, C ;

Wenk, C .

ALGORITHMICA, 2004, 38 (01) :45-58

[3] COMPUTING THE FRECHET DISTANCE BETWEEN 2 POLYGONAL CURVES [J].

ALT, H ;

GODAU, M .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1995, 5 (1-2) :75-91

[4]

ALT H, 2007, CAN WE COMPUTE SIMIL

[5]

Alt H., 2005, P 21 EUR WORKSH COMP, P45

[6]

ALT H, 1999, HDB COMPUTATIONAL GE, P121

[7]

[Anonymous], AM MATH SOC C PUBL

[8]

Buchin K., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry (SCG'06), P80, DOI 10.1145/1137856.1137870

[9]

BUCHIN K, 2005, P 15 ANN FALL WORKSH, P7

[10]

BUCHIN K, 2006, P 22 EUR WORKSH COMP, P103

← 1 2 →