ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 05,52 Ishigami, Yoshiyasu, University of Electro-Communications, Tokyo Covering an Orthogonal Polygon with Diagonal Rectangles A polygon is orthogonal if each edge is either vertical or horizontal. A family of rectangles R_{i}(1 ≤ i ≤ m) covers an orthogonal polygon P if and only if ∪_{i}R_{i} = P. We don’t allow neither rotation of rectangles. The problem of covering an orthogonal polygon with rectangles has practical applications and has been researched in many papers. A rectangle R is diagonal (with respect to an orthogonal polygon P) if and only if for at least one of the two diagonals of R, both endpoints of it are vertices of P. Watanabe [2] proposed the following question: “How many diagonal rectangles are needed to cover an orthogonal polygon with n vertices?”We will answer the question. Reference: [1] J. C. Culberson and R. A. Reckhow, Covering polygon is hard, Journal of Algorithms, 17, 2-44(1994). [2] Mamoru Watanabe, Rectangle coverings in orthogonal polygons, to appear (British Conference of Combinatorics,1997).