Covering rectilinear polygons with axis-parallel rectangles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Covering rectilinear polygons with axis-parallel rectangles

Full text

Pdf (867 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 445 - 454

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

V. S. Anil Kumar	Dept. of Computer Science and Automation, Indian Institute of Science, Bangalore 560012 India
H. Ramesh	Dept. of Computer Science and Automation, Indian Institute of Science, Bangalore 560012 India

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 88, Citation Count: 7

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/301250.301369 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	P. Berman and B. Dasgupta. Approximating Rectilinear Polygon Cover Problems. Proceedings of dth Canadian Conference on Computational Geometry, 19927 pp. 229-2;35.
	2	H. Br6nnimann, M. Goodrich. Almost Optimal Set Covers in Finite VC-Dimension. Discrete Comput. Geom., 142 19957 pp. 263-279.
	3	S. ChaJken, D.J. Kleitman, M. Saks and J. Shearer. Covering Regions by Rectangles. SIAM J. Algebraic and Discrete Methods, Vol. 2, 4, 198t, pp. 394-410.
	4	Y. Cheng , S. S. Iyengar , R. L. Kashyap, A New Method of image Compression Using Irreducible Covers of Maximal Rectangles, IEEE Transactions on Software Engineering, v.14 n.5, p.651-658, May 1988 [doi>10.1109/32.6142]
	5	Joseph C. Culberson , Robert A. Reckhow, Covering polygons is hard, Journal of Algorithms, v.17 n.1, p.2-44, July 1994 [doi>10.1006/jagm.1994.1025]
	6	D. S. Franzblau, Performance guarantees on a sweep-line heuristic for covering rectilinear polygons with rectangles, SIAM Journal on Discrete Mathematics, v.2 n.3, p.307-321, August 1989 [doi>10.1137/0402027]
	7	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]
	8	A. Hegediis. Algorithms for Covering Polygons with Rectangles. Computer Aided Geom. DeMgrq 14, {982, pp. 257-260.
	9	D.S. Johnson. Approximation Algorithms for Combinatorial Problems. Journal of Computing and Systems Sciences, 9, 1974, pp. 256-278.
	10	J M Keil, Minimally covering a horizontally convex orthogonal polygon, Proceedings of the second annual symposium on Computational geometry, p.43-51, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10520]
	11	C. Levcopoulos. On Covering Regions with Minimum Number of Rectangles. Proceedings of International Workshop on Par. Comp. and VLSI, I984.
	12	Christos Levcopoulos, A fast heuristic for covering polygons by rectangles, Fundamentals of Computation Theory, p.269-278, September 09-13, 1985
	13	Christos Levcopoulos, Improved bounds for covering general polygons with rectangles, Proc. of the seventh conference on Foundations of software technology and theoretical computer science, p.95-102, December 1987, Pune, India
	14	Christos Levcopoulos , Joachim Gudmundsson, Close Approximation of Minimum Rectangular Coverings, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, p.135-146, December 18-20, 1996
	15	C. Levcopoulos and J. Gudmundsson. Approximation Algorithms for Covering Polygons with Squares and Similar Problems. Technical Report, Lund University.
	16	L. Lovasz. On the Ratio of Optimal.Integral and Fractional Covers. Journal of Discrete Mathematics, 13, 1975, pp. 383-390.
	17	Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
	18	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
	19	W.J. Masek. Some NP-Comptete Set Covering Problems, Manuscript, MIT, 1979.

CITED BY 7

	Himanshu Gupta , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA
	Alberto O. Mendelzon , Ken Q. Pu, Concise descriptions of subsets of structured sets, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.123-133, June 09-11, 2003, San Diego, California
	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
	Himanshu Gupta , Zongheng Zhou , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.55-67, February 2006
	Sherin M. Youssef , Meer A. Hamza , Salma F. Fayed, EQOWSN: Evolutionary-based query optimization over self-organized wireless sensor networks, Expert Systems with Applications: An International Journal, v.36 n.1, p.81-92, January, 2009
	David A. Applegate , Gruia Calinescu , David S. Johnson , Howard Karloff , Katrina Ligett , Jia Wang, Compressing rectilinear pictures and minimizing access control lists, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1066-1075, January 07-09, 2007, New Orleans, Louisiana
	Mohamed K. Watfa , Sesh Commuri, An energy efficient and self-healing 3-dimensional sensor cover, International Journal of Ad Hoc and Ubiquitous Computing, v.3 n.1, p.33-47, December 2008