Computing the Fréchet distance between simple polygons in polynomial time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing the Fréchet distance between simple polygons in polynomial time

Full text

Pdf (216 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twenty-second annual symposium on Computational geometry table of contents

Sedona, Arizona, USA

SESSION: Session 3 (monday, june 5th--3:20-4:20 pm) table of contents

Pages: 80 - 87

Year of Publication: 2006

ISBN:1-59593-340-9

Authors

Kevin Buchin	Freie Universität Berlin, Berlin, Germany
Maike Buchin	Freie Universität Berlin, Berlin, Germany
Carola Wenk	University of Texas, San Antonio, TX

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 60, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1137856.1137870 What is a DOI?

ABSTRACT

We present the first polynomial-time algorithm for computing the Fréchet for a non-trivial class of surfaces: simple polygons. For this, we show that it suffices to consider homeomorphisms that map an arbitrary triangulation of one polygon to the other polygon such that diagonals of the triangulation are mapped to shortest paths in the other polygon.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	H. Alt, B. Behrends, and J. Blömer. Approximate matching of polygonal shapes. Ann. Math. Artif. Intell., 13:251--266, 1995.
	2	H. Alt and M. Buchin. Semi-computability of the Fréchet distance between surfaces. In Proc. 21st European Workshop on Computational Geometry, pages 45--48, 2005.
	3	H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. Internat. J. Comput. Geom. Appl., 5:75--91, 1995.
	4	H. Alt and L. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 121--153. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 1999.
	5	Helmut Alt , Christian Knauer , Carola Wenk, Comparison of Distance Measures for Planar Curves, Algorithmica, v.38 n.1, p.45-58, October 2003 [doi>10.1007/s00453-003-1042-5]
	6	Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991
	7	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	8	M. Fréchet. Sur la distance de deux surfaces. Ann. Soc. Polonaise Math., 3:4--19, 1924.
	9	M. Godau. On the complexity of measuring the similarity between geometric objects in higher dimensions. PhD thesis, Freie Universität Berlin, Germany, 1998.
	10	L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
	11	T. Rado. Length and area. Amer. Math. Soc. Colloq. Publ. Vol. 30, New York, 1948.
	12	Remco C. Veltkamp , Michiel Hagedoorn, State of the art in shape matching, Principles of visual information retrieval, Springer-Verlag, London, 2000