Minimally covering a horizontally convex orthogonal polygon

ABSTRACT

In this paper we present &Ogr;(n2) time algorithms for the problems of covering a horizontally convex orthogonal polygon with the minimum number of orthogonal convex polygons and with the minimum number of orthogonal star-shaped polygons.

REFERENCES

• Agg 84: Alok Aggarwal, The art gallery theorem: its variations, applications and algorithmic aspects, 1984
• ACYB 80: N. Ahuya, R.T. Chien, R. Yen and N, Birdwelt, Interference detection and collision avoidance among three dimensional objects, Proc. First Annual National Conference on Artificial Intelligence, Stanford, California, 1980, 44-48.
• CD 79: 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]
• Cha 80: Bernard Marie Chazelle, Computational geometry and convexity, 1980
• EOW 83: H. Edelsbrunner, J. O'Rourke and E. Welzi, Stationing Guards in Rectilinear Art Galleries, Technical Report EE- 83/02 John Hopkins University, 1983.
• FK 84: Deborah S. Franzblau , Daniel J. Kleitman, An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.167-174, December 1984 [doi>10.1145/800057.808678]
• Gre 82: D. Greene, The Decomposition of Polygons into Convex Parts, Manuscript, Xerox PARC, 1982.
• Hon 76: R. Honsberger, Mathematical Gems il, Mathematical Association of America, 1976, 104-110.
• KKK 83: J. Kahn, M. Klawe and D. Kleitman, Traditional galleries require fewer watchman, SIAM J. of Algebraic and Discrete Methods, 4, 2(1983), 194-206.
• Kei 83: J.M. Keil, Decomposing Polygons into Simpler Components, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1983.
• Kei 85: J.M. Keil, Decomposing a Polygon into Simpler Components, SIAM Journal on Computing, 14,4 (1985), 799-817.
• KS 85: J.M. Keil and J.-R. Sack, Minimum decompostions of polygonal objects, in Computational Geometry, Ed. G.T. Toussaint, No-h Holland, 1985.
• Lin 82: 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
• LLLMP 79: W. Lipski, E. Lodi, F. Luccio, C. Mugnai and L. Pagli, On two dimensional data organization 11, Fundamenta Informaticae, 2 (1979), 245-260.
• MW 84: H. Mannila and D. Wood, A simple proof of the rectilinear art gallery theorem, Technical Report C-1984-16, Dept. of Computer Science, University of Helsinki, Finland, 1984.
• Mas 79: W.J. Masek, Some NP-complete set covering problems, unpublished manuscript, August 1979.
• MF 82: D.Y. Montuno and A. Fournier, Detecting Intersections Among Star Polygons, Tech. Rept. CSRG-146, University of Toronto, Toronto, Canada, Sept. 1982.
• OSTT 83: T. Ohtsuki, M. Sato, M. Tachibana and S. Torii, Minimum partitioning of rectilinear regions, Trans. of Information Processing Society of Japan.
• OR 83: J. O'Rourke, An alternate proof of the rectilinear art gallery theorem, Technical Report EE-83-3, John Hopkins University, Baltimore, MD, March 1983.
• OS 83: J. O'Rourke and K.J. Supowit, Some NP-Hard Polygon Decomposition Problems, IEEE Trans. on Information Theory, Vol. 1T-29, 2, (1983), 181-190.
• Sac 82: J.-R. Sack, An O(nlogn) algorithm for decomposing simple rectilinear polygons into convex quadrilaterals, Proc. 20th Allerton Conference on Communication, Control and Computing, Monticello, IL, 1982, 64-74.
• Sac 84: Jorg-Rudiger Wolfgang Sack, Rectilinear computational geometry, 1984
• SvL 80: A.A. Schoone and J. van Leeuwan, Triangulating a starshaped polygon, Tech. Rept. RUV-CS-80-3, University of Utrecht, April 1980.

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Theory, Verification