Approximate matching of polygonal shapes (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate matching of polygonal shapes (extended abstract)

Full text

Pdf (562 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the seventh annual symposium on Computational geometry table of contents

North Conway, New Hampshire, United States

Pages: 186 - 193

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Helmut Alt	Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W-1000 Berlin 33, Germany
Bernd Behrends	Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W-1000 Berlin 33, Germany
Johannes Blömer	Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, W-1000 Berlin 33, Germany

Sponsors

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): n/a, Downloads (12 Months): n/a, Citation Count: 20

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/109648.109669 What is a DOI?

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.

	ABGW	Helmut Alt , Johannes Blömer , Michael Godau , Hubert Wagener, Approximation of convex polygons, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.703-716, July 1990, Warwick University, England
	AKMSW	Esther M. Arkin , Klara Kedem , Joseph S. B. Mitchell , Josef Sprinzak , Michael Werman, Matching points into noise regions: combinatorial bounds and algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.42-51, January 28-30, 1991, San Francisco, California, United States
	AMWW	Helmut Alt , Kurt Mehlhorn , Hubert Wagener , Emo Welzl, Congruence, similarity and symmetries of geometric objects, Discrete & Computational Geometry, v.3 n.3, p.237-256, Jan., 1988 [doi>10.1007/BF02187910]
	ASS	P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
	At1	M. j. Atallah, "A Linear Time Algorithm for the Hausdorff-distance between Convex Polygons'', Information Processing Letters 17, 1983, pp. 207-209.
	At2	M. Atallah, "Dynamic Computational Geometry'', Prec. 24th Annual Symp. on Foundations of Computer Science, 1983, pp. 92-99 also in Comp. Math. Appl. 11, 1985, pp. 1171-1181.
	EPSS	H. Edelsbrunner, J. Path, J. T. Schwartz, M. Sharir, "On the Lower Envelope of Bivariate Functions and its Applications", Prec. 28th Annual Symp. on Foundations of Computer Science, 1987, pp. 27-37.
	F	S. Fortune, "A Sweepline- Algorithm for Voronot-Diagrams", Algorithmica 2, 1987, pp. 153- 174.
	G	Michael Godau, A natural metric for curves—computing the distance for polygonal chains and approximation algorithms, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.127-136, February 1991, Hamburg, Germany
	HK	Daniel P. Huttenlocher , Klara Kedem, Computing the minimum Hausdorff distance for point sets under translation, Proceedings of the sixth annual symposium on Computational geometry, p.340-349, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98599]
	M	G. E. Martin, Transformation Geometry, Springer-Verlag, New York, Heidelberg, Berlin, 1982.
	S	S. Schirra, "Uber die Bitkomplexit~it der c- Kongruenz", Diplomarbeit, Fachbereich Informatik, Universit~t des Saarlandes, 1988.
	Y	C.K. Yap, "An O(nlogn) Algorithm for the Voronoi Diagram of a Set of Simple Curve Segments'', Discrete Comp. Geom. 2, 1987, pp. 365- 393.

CITED BY 20

	Andrew B. Kahng, Classical floorplanning harmful?, Proceedings of the 2000 international symposium on Physical design, p.207-213, May 2000, San Diego, California, United States
	Helmut Alt , Michael Godau, Measuring the resemblance of polygonal curves, Proceedings of the eighth annual symposium on Computational geometry, p.102-109, June 10-12, 1992, Berlin, Germany
	Piotr Indyk , Suresh Venkatasubramanian, Approximate congruence in nearly linear time, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.354-360, January 09-11, 2000, San Francisco, California, United States
	Paul Goldberg , Mark Jerrum, Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers, Proceedings of the sixth annual conference on Computational learning theory, p.361-369, July 26-28, 1993, Santa Cruz, California, United States
	Nina Amenta, Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem, Proceedings of the tenth annual symposium on Computational geometry, p.340-347, June 06-08, 1994, Stony Brook, New York, United States
	Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg, On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane, Proceedings of the eighth annual symposium on Computational geometry, p.110-119, June 10-12, 1992, Berlin, Germany
	Selwyn Piramuthu, On learning to predict web traffic, Decision Support Systems, v.35 n.2, p.213-229, May 2003
	Berto van de Kraats , Marc van Kreveld , Mark Overmars, Printed circuit board simplification: simplifying subdivisions in practice, Proceedings of the eleventh annual symposium on Computational geometry, p.430-431, June 05-07, 1995, Vancouver, British Columbia, Canada
	Michael T. Goodrich , Joseph S. B. Mitchell , Mark W. Orletsky, Practical methods for approximate geometric pattern matching under rigid motions: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.103-112, June 06-08, 1994, Stony Brook, New York, United States
	Piotr Indyk , Suresh Venkatasubramanian, Approximate congruence in nearly linear time, Computational Geometry: Theory and Applications, v.24 n.2, p.115-128, February 2003
	Michael Elad , Ayellet Tal , Sigal Ar, Content based retrieval of VRML objects: an iterative and interactive approach, Proceedings of the sixth Eurographics workshop on Multimedia 2001, p.107-118, September 08-09, 2001, Manchester, UK
	Helmut Alt , Oswin Aichholzer , Günter Rote, Matching shapes with a reference point, Proceedings of the tenth annual symposium on Computational geometry, p.85-92, June 06-08, 1994, Stony Brook, New York, United States
	Alon Efrat , Alon Itai, Improvements on bottleneck matching and related problems using geometry, Proceedings of the twelfth annual symposium on Computational geometry, p.301-310, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
	Laurence Boxer , Russ Miller, Coarse grained gather and scatter operations with applications, Journal of Parallel and Distributed Computing, v.64 n.11, p.1297-1310, November 2004
	Riyaz Sikora , Selwyn Piramuthu, Efficient Genetic Algorithm Based Data Mining Using Feature Selection with Hausdorff Distance, Information Technology and Management, v.6 n.4, p.315-331, October 2005
	Arijit Bishnu , Sandip Das , Subhas C. Nandy , Bhargab B. Bhattacharya, Simple algorithms for partial point set pattern matching under rigid motion, Pattern Recognition, v.39 n.9, p.1662-1671, September, 2006
	Erwin Prassler , Jens Scholz , Alberto Elfes, Tracking Multiple Moving Objects for Real-Time Robot Navigation, Autonomous Robots, v.8 n.2, p.105-116, April 2000
	Michiel Hagedoorn , Remco C. Veltkamp, Reliable and Efficient Pattern Matching Using an Affine Invariant Metric, International Journal of Computer Vision, v.31 n.2-3, p.203-225, April 1999
	Bernardo Llanas, Efficient Computation of the Hausdorff Distance Between Polytopes by Exterior Random Covering, Computational Optimization and Applications, v.30 n.2, p.161-194, February 2005