Minimum partitioning simple rectilinear polygons in O(n log log n)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimum partitioning simple rectilinear polygons in O(n log log n) - time

Full text

Pdf (1.36 MB)

Source

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

Saarbruchen, West Germany

Pages: 344 - 353

Year of Publication: 1989

ISBN:0-89791-318-3

Authors

W. T. Liou	Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C.
J. J. Tan	Institute of Information Science, National Chiao Tung University, Hsinchu, Taiwan, R.O.C.
R. C. Lee	National Tsing Hua University, Hsinchu, Taiwan, and the Academia Sinica, Taipei, Taiwan, R.O.C.

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

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

	AHO74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	ASAN86	Takao Asano , Tetsuo Asano , Roy Y Pinter, Polygon triangulation: efficiency and minimality, Journal of Algorithms, v.7 n.2, p.221-231, June 1986 [doi>10.1016/0196-6774(86)90005-2]
	CHAI81	S. Chaiken, D.J. Kleitman, M. Saks, and J. Shearer, 'Covering Regions by Rectangles', SIAM Journal on Algebraic and Discrete Methods 2(1981), 394410.
	FERR84	L. Ferrari, P.V. Sankar, and J. Sklansky, 'Minimal Rectangular Partition of Digitized Blobs', Computer z:is;: Granhics. and Imaee Processlog 28(19S4),
	FRAN84	D S Franzblau , D J Kleitman, An algorithm for covering polygons with rectangles, Information and Control, v.63 n.3, p.164-189, Dec. 1986 [doi>10.1016/S0019-9958(84)80012-1]
	GABO85	H.N. Gabow, and R.E. Tarjan, 'A Linear-Time Algorithm for a Special Case of Disjoint Set Union', Journal of CornmIter and Svstem Scienoes 30(1935). 209-221.
	GLOV67	F. Glover, 'Maximum Matching in Convex Bipartite Graph', Naval l&s. LoPist. Quart. 14(L967), 313-316.
	GOUR83	K.D. Gourley, and D.M. Green, 'A Polygon-t@Rectangle Conversion Algorithm', IEEE Commuter Graohica and ADDkations 3(1983), 31-36.
	HEGE82	A. Hegediis, 'Algorithms for Covering Polygons by Rectangles', Commuter Aided Design 257-260. 14( 1982),
	HOPC73	E. Hopcroft, and R.M. Karp 'An n5/2 Algorithm for Maximum Matchings in bipartite Graph' SIAM Journal on Comouting 2( 1973), 225-231. ' -
	IMAI86	Hiroshi Imai , Takao Asano, Efficient algorithms for geometric graph search problems, SIAM Journal on Computing, v.15 n.2, p.478-494, May 1986 [doi>10.1137/0215033]
	LIPS79	W. Lispki, Jr., E. Lode, F. Luccio, C. Muganai, and L. Pagli, 'On Two Dimensional Data Organization II,' Fundamenta Informaticae 2(1979), 245-260.
	LIPS81	W. Lipski, Jr., and F.P. Preparata, 'Efficient Algorithms for Finding Maximum Matchings in Convex Bipartite Graphs and Related Problems', Acta Informatica 15(1981), 329-346.
	MEHL84	K. Mehlhorn, Data Structures and Algorithms 1: Sortine and Searching, Springer-Verlag, Berlin, 1984.
	NAHA88	S. Nahar, and S. Sah;b;;ast Algorithm for Polygon Decomposition', y- Transactions on 'Minimum Partitioning of Rectilinear Regions'~ Transaction of Information ProcesssinE %cietv oi J&p& 1963.
	OHTS82	T. Ohtsuki, "Minimum Dissection of Rectilinear Regions'. Proceedings of IEEE Symposium on Circuits and Systems. 1982, pp.1210-1213.
	OHTS83	T. Ohtsuki, M. Sato, M. Tachibana, and S. Torii, 'Minimum Partitioning of Rectilinear Regions' Transaction of Information Processing Siciety of Japan. 1963.
	PAPA82	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	TARJ88	Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]

CITED BY 4

	David G. Kirkpatrick , Maria M. Klawe , Robert E. Tarjan, Polygon triangulation in O(n log log n) time with simple data-structures, Proceedings of the sixth annual symposium on Computational geometry, p.34-43, June 07-09, 1990, Berkley, California, United States
	Mario A. Lopez , Dinesh P. Mehta, Efficient decomposition of polygons into L-shapes with application to VLSI layouts, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.3, p.371-395, July 1996
	Joseph O'Rourke , Geetika Tewari, The structure of optimal partitions of orthogonal polygons into fat rectangles, Computational Geometry: Theory and Applications, v.28 n.1, p.49-71, May 2004
	Joachim Gudmundsson , Thore Husfeldt , Christos Levcopoulos, Lower bounds for approximate polygon decomposition and minimum gap, Information Processing Letters, v.81 n.3, p.137-141, 14 February 2002