Decomposing polygonal regions into convex quadrilaterals

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Decomposing polygonal regions into convex quadrilaterals

Full text

Pdf (932 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: 97 - 106

Year of Publication: 1985

ISBN:0-89791-163-6

Author

Anna Lubiw

Department of Computer Science, University of Toronto, Toronto, 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): 15, Downloads (12 Months): 55, Citation Count: 6

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/323233.323247 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Bernard Chazelle , David Dobkin, Decomposing a polygon into its convex parts, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.38-48, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804396]
	3	[EOW] H. Edelsbrunner, J. O'Rourke, E. Welzl. Stationing guards in rectilinear art galleries, Computer Vision, Graphics, and Image Processing 27, 1984, 167-176.
	4	[F] S. Fisk, A short proof of Chvátal's watchman theorem, J. Combinatorial Theory B 24, 1978, 374.
	5	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	6	[GJPT] M. R. Garey, D. S. Johnson, F. P. Preparata and R. E. Tarjan, Triangulating a simple polygon, Information Processing Letters 7, 1978, 175- 179.
	7	[K] J. M. Keil, Decomposing Polygons into Simpler Components, Ph.D. thesis, Dept. Computer Science, U. of Toronto, 1983.
	8	[KKK] J. Kahn, M. Klawe and D. Kleitman. Traditional galleries require fewer watchmen, SIAM J. Algebraic and Discrete Methods 4, 1983, 194- 206.
	9	[L] D. Lichtenstein, Planar satisfiability and its uses, SIAM J. Computing 11, 1982, 329-343.
	10	Andrzej Lingas, The Power of Non-Rectilinear Holes, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.369-383, July 12-16, 1982
	11	[LPRS] A. Lingas, R. Y. Pinter, R. L. Rivest, A. Shamir, Minimum edge length decomposition of rectilinear polygons, unpublished manuscript.
	12	[O] J. O'Rourke, An alternate proof of the rectilinear art gallery theorem, J. Geometry 21, 1983, 118-130.
	13	[PS] W. Paul and J. Simon, Decision trees and random access machines, Logic and Algorithmic, Monograph 30, L'Enseignement Mathematique, 1980.
	14	[PLLML] L. Pagli, E. Lodi, F. Luccio, C. Mugnai, W. Lipski, On two dimensional data organization 2, Fundamenta Informaticae, Vol. 2, No. 3, 1979.
	15	[S] J.-R. Sack, An O(nlogn) algorithm for decomposing simple rectilinear polygons into convex quadrilaterals, Proc. 20th Allerton Conf., 1982, 64-74.
	16	[SH] M. I. Shamos and D. J. Hoey, Geometric intersection problems, Proc. 17th Annual IEEE Symp. on Foundations of Computer Science, 1976, 208-215.
	17	[T] G. T. Toussaint. Pattern recognition and geometric complexity, 5th Internat. Conf. on Pattern Recognition, 1980, 1324-1347.
	18	[Ta] R. E. Tarjan, Data Structures and Network Algorithms, CBMS-NSF Regional Conf. Series in Applied Math., SIAM, Philadelphia, 1983.

CITED BY 6

	John H. Reif , James A. Storer, A single-exponential upper bound for finding shortest paths in three dimensions, Journal of the ACM (JACM), v.41 n.5, p.1013-1019, Sept. 1994
	Matthias Müller-Hannemann , Karsten Weihe, Minimum strictly convex quadrangulations of convex polygons, Proceedings of the thirteenth annual symposium on Computational geometry, p.193-202, June 04-06, 1997, Nice, France
	W Chin , S Ntafos, Optimum watchman routes, Proceedings of the second annual symposium on Computational geometry, p.24-33, June 02-04, 1986, Yorktown Heights, New York, United States
	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
	Menelaos I. Karavelas , Csaba D. Tóth , Elias P. Tsigaridas, Guarding curvilinear art galleries with vertex or point guards, Computational Geometry: Theory and Applications, v.42 n.6-7, p.522-535, August, 2009
	M. Abellanas , S. Canales , G. Hernández-Peòalver, An “Art Gallery Theorem” for pyramids, Information Processing Letters, v.109 n.13, p.719-721, June, 2009