Turtlegons

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Turtlegons: generating simple polygons for sequences of angles

Full text

Pdf (499 KB)

Source

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

Baltimore, Maryland, United States

Pages: 305 - 310

Year of Publication: 1985

ISBN:0-89791-163-6

Authors

Joseph Culberson	Data Structuring Group, Department of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3Gl Canada
Gregory Rawlins	Data Structuring Group, Department of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3Gl Canada

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

Additional Information:

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

ABSTRACT

In this paper we present an algorithm to create simple polygons with a particular sequence of exterior angles, given only the sequence of angles. The algorithm has worst case time complexity &Ogr;(Dn), where n is the number of angles and D is dependent on the angles. As a bonus, the algorithm proves an interesting converse of the ancient theorem that the sum of the exterior angles of a simple polygon is 2&pgr; radians.

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	[1] Fredericksen, H. and Maiorana, J.; "Necklaces of beads in k colours and k-ary DeBruijn sequences," Discrete Math. 23 (1978) pp. 207-210.
	2	[2] Honsberger, R.; "Semi-regular lattice polygons," Two Year College Math. J. 13 (1982) pp. 36-44.
	3	[3] O'Rourke, J.; Personal communication.
	4	Seymour Papert, Mindstorms: children, computers, and powerful ideas, Basic Books, Inc., New York, NY, 1980
	5	[5] Sack, J.-R.; Personal communication.
	6	Jorg-Rudiger Wolfgang Sack, Rectilinear computational geometry, 1984
	7	[7] Stewart, B. M. and Herzog, F.; "Semiregular plane polygons of integral type," Israel J. of Math. 11 (1972) pp. 31-52.

CITED BY 2

	P. D. Alevizos , J. Boissonnat , M. Yvinec, An optimal O(n log n) algorithm for contour reconstruction from rays, Proceedings of the third annual symposium on Computational geometry, p.162-170, June 08-10, 1987, Waterloo, Ontario, Canada
	Leonidas Guibas , John Hershberger, Morphing simple polygons, Proceedings of the tenth annual symposium on Computational geometry, p.267-276, June 06-08, 1994, Stony Brook, New York, United States