Kink-free deformations of polygons

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Kink-free deformations of polygons

Full text

Pdf (701 KB)

Source

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

Saarbruchen, West Germany

Pages: 61 - 68

Year of Publication: 1989

ISBN:0-89791-318-3

Author

G. Vegter

Dept. of Computing Science, University of Groningen, P.O.Box 800, 9700AV Groningen, The Netherlands

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): 0, Downloads (12 Months): 10, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/73833.73840 What is a DOI?

ABSTRACT

We consider a discrete version of the Whitney-Graustein theorem concerning regular equivalence of closed curves. Two regular polygons P and P', i.e. polygons without overlapping adjacent edges, are called regularly equivalent if there is a continuous one-parameter family Ps, O ≥ s ≤ 1 of regular polygons with Po = P and P1 = P'. Geometrically the one-parameter family is a kink-free deformation transforming P into P'. The winding number of a polygon is a complete invariant of its regular equivalence class. We develop a linear algorithm that determines a linear number of elementary steps to deform a regular polygon into any other regular polygon with the same winding number.

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.

	D	M. Dehn: 'Transformation der Kurven auf zweiseitigen Flachen", Math. Annalen, vol. 72 (1912), 413-421.
	GKP	Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	MY	Kurt Mehlhorn , Chee-Keng Yap, Constructive Hopf's Theorem: Or How to Untangle Closed Planar Curves, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.410-423, July 11-15, 1988
	S	S. Smale: "Regular curves on Riemannian manifolds", Trans. Amer. Math. Soc., vol.87 (1958), 492-512.
	W	H. Whitney: "On regular closed curves in the plane", Compos. Math., vol. 4 (1937), 276- 284.

CITED BY 4

	Gert Vegter , Chee K. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry, p.102-111, June 07-09, 1990, Berkley, California, United States
	Haijo Schipper, Determining contractibility of curves, Proceedings of the eighth annual symposium on Computational geometry, p.358-367, June 10-12, 1992, Berlin, Germany
	Tamal K. Dey, A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection, Proceedings of the tenth annual symposium on Computational geometry, p.277-284, June 06-08, 1994, Stony Brook, New York, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada