Convex Decomposition of Simple Polygons

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Convex Decomposition of Simple Polygons

Full text

Pdf (844 KB)

Source

ACM Transactions on Graphics (TOG) archive
Volume 3 , Issue 4 (October 1984) table of contents

Pages: 244 - 265

Year of Publication: 1984

ISSN:0730-0301

Authors

S. B. Tor	Computer-Aided Engineering Group, School of Engineering and Science, Polytechnic of Central London, 115 New Cavendish Street, London W1M 8JS, England
A. E. Middleditch	Computer-Aided Engineering Group, School of Engineering and Science, Polytechnic of Central London, 115 New Cavendish Street, London W1M 8JS, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 100, Citation Count: 8

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/357346.357348 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.

	1	AKL, S. G., AND TOUSSAINT, G.T. A fast convex hull algorithm. Inf. Prec. Left. 7 (1978), 219- 222.
	2	ANDREW, A.M. Another efficient algorithm for convex hull in 2-dimensions. Inf. Prec. Lett. 9 (1979), 216-219.
	3	BVKAT, A. Convex hull of a finite set of points in two dimensions, lnf Proc. Lett. 7(1978),296- 298.
	4	CItAZELLE, B.M. Computational geometry and convexity. Tech. CMU-CS-80-150, Carnegie- Mellon Univ., Pittsburgh, Pa., 1980.
	5	William F. Eddy, A New Convex Hull Algorithm for Planar Sets, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.398-403, Dec. 1977 [doi>10.1145/355759.355766]
	6	GRAHAM, R.L. An efficient algorithm for determining the convex hull of a planar set. Inf. Proc. Letl. I (1972), 132-133.
	7	GRAr~AM, R. L., AND YAO, F.F. Finding the convex hull of a simple polygon. J. Algorithms. To be published.
	8	GREEN, P. J., AND SILVERMAN, B. W. Constructing the convex hull of a set of points in the plane. Comput. J. 22, 3 (1979}, 262-266.
	9	JARVIS, R.A. On the identification of the convex hull of a finite set of points in the plane. Inf. Proc. Lett. 2 (1973), 18-21.
	10	LEE, D.T. On finding the convex hull of a simple polygon. Int. J. Comput. In{. Set 12, 2 (1983), 87-98.
	11	MCCALLUM, D., AND AVIS, D. A linear time algorithm for finding the convex hull of a simple polygon. In{. Proc. Lett. 9 (1979), 201-205.
	12	F. P. Preparata, An optimal real-time algorithm for planar convex hulls, Communications of the ACM, v.22 n.7, p.402-405, July 1979 [doi>10.1145/359131.359132]
	13	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	14	Michael Ian Shamos, Computational geometry., 1978
	15	SKLANSK~, J. Measuring concavity on a rectangular mosaic. IEEE Trans. Comput. C-21. (1972), 1355-1364.
	16	{WOOnWAP, K, J.R., AND WALLIS, A.F. Graphical input to a Boolean solid modeller. In CAD 82, Brighton, U.K., 1982, p. 681-688.
	17	Andrew Chi-Chih Yao, A Lower Bound to Finding Convex Hulls, Journal of the ACM (JACM), v.28 n.4, p.780-787, Oct. 1981 [doi>10.1145/322276.322289]

CITED BY 8

	David Dobkin , Leonidas Guibas , John Hershberger , Jack Snoeyink, An efficient algorithm for finding the CSG representation of a simple polygon, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.31-40, Aug. 1988
	Ari Rappoport, The n-dimensional extended convex differences tree (ECDT) for representing polyhedra, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.139-147, June 05-07, 1991, Austin, Texas, United States
	Henry Fuchs , John Poulton , John Eyles , Trey Greer , Jack Goldfeather , David Ellsworth , Steve Molnar , Greg Turk , Brice Tebbs , Laura Israel, Pixel-planes 5: a heterogeneous multiprocessor graphics system using processor-enhanced memories, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.79-88, July 1989
	Richard J. Howarth, Spatial Models for Wide-Area Visual Surveillance: Computational Approaches and Spatial Building-Blocks, Artificial Intelligence Review, v.23 n.2, p.97-155, April 2005
	Ari Rappoport , Steven Spitz, Interactive Boolean operations for conceptual design of 3-D solids, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.269-278, August 1997
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989
	Ken Q. Pu , Alberto O. Mendelzon, Concise descriptions of subsets of structured sets, ACM Transactions on Database Systems (TODS), v.30 n.1, p.211-248, March 2005
	Jyh-Ming Lien , Nancy M. Amato, Approximate convex decomposition of polygons, Computational Geometry: Theory and Applications, v.35 n.1, p.100-123, August 2006