On partitioning rectilinear polygons into star-shaped polygons

1. A. Aho, J. Hopcroft, and J. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.

   MATH  Google Scholar 

2. T. Asano, T. Asano, and H. Imai, Partitioning a Polygonal Region into Trapezoids,Journal of ACM, Vol. 33, No. 2, April 1986, pp. 290–312.

   Article  MathSciNet  Google Scholar 

3. D. Avis and G. T. Toussaint, An Efficient Algorithm for Decomposing a Polygon into Star-Shaped Polygons,Pattern Recognition, Vol. 13, No. 6, 1981, pp. 395–398.

   Article  MathSciNet  Google Scholar 

4. B. Chazelle and D. Dobkin, Decomposing a Polygon into its Convex Parts, inProc. 11th Annual ACM Symposium on Theory of Computing, 1979, pp. 38–48.

5. V. Chvátal, A Combinatorial Theorem in Plane Geometry,Journal of Combinatorial Theory, Series B, Vol. 18, 1975, pp. 39–41.

   Article  MATH  MathSciNet  Google Scholar 

6. S. Fisk, A Short Proof of Chvátal's Watchman Theorem,Journal of Combinatorial Theory, Series B, Vol. 24, 1978, p. 374.

   Article  MathSciNet  Google Scholar 

7. M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a Simple Polygon,Information Processing Letters, Vol. 7, No. 4, 1978, pp. 175–179.

   Article  MATH  MathSciNet  Google Scholar 

8. J. Kahn, M. Klawe, and D. Kleitman, Traditional Galleries Require Fewer Watchman,SIAM Journal on Algebraic and Discrete Methods, Vol. 4, No. 2, 1983, pp 194–206.

   Article  MATH  MathSciNet  Google Scholar 

9. J. M. Keil, Decomposing a Polygon into Simpler Components,SIAM Journal on Computing, Vol. 14, No. 4, 1985, pp. 799–817.

   Article  MATH  MathSciNet  Google Scholar 

10. J. M. Keil and J.-R. Sack. Minimum Decompositions of Polygonal Objects, inComputational Geometry, Ed. G. T. Toussaint, North-Holland, Amsterdam, 1985, pp. 197–216.

    Google Scholar 

11. D. T. Lee and F. P. Preparata, Computational Geometry—a Survey,IEEE Transactions on Computers, Vol. 33, No. 12, Dec. 1984, pp. 1072–1101.

    Article  MathSciNet  Google Scholar 

12. J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, Oxford, 1987.

    MATH  Google Scholar 

13. L. Pagli, E. Lodi, F. Luccio, C. Mugnai, and W. Lipski, On Two-Dimensional Data Organization 2,Fundamenta Informaticae, Vol. 2, No. 3, 1979.

14. J. R. Sack, AnO(n logn) Algorithm for Decomposing Simple Rectilinear Polygons into Convex Quadrilaterals, inProc. 20th Allerton Conference, 1982, pp. 64–74.

15. G. T. Toussaint, Pattern Recognition and Geometrical Complexity, inProc. Fifth International Conference on Pattern Recognition, Dec. 1980, pp. 1324–1347.

Download references