How many diagonal rectangles are needed to cover an orthogonal polygon?

DOI10.1007/S004540010059MaRDI QIDQ1577551zbMATH OpenOpenAlexFDO

Authors Yoshiyas Ishigami

Publication date 3 September 2001

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004540010059

zbMATH Keywords

coveringorthogonal polygonrectangle

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Review text

A polygon whose edges are horizontal and vertical is called ``orthogonal. A rectangle with a pair of opposite corners at the vertices of an orthogonal polygon is ``diagonal (in that polygon). The author finds that any orthogonal polygon with \(n\) vertices can be covered by (the union of) \(\lfloor {3\over 4}n \rfloor-2-\omega\) diagonal rectangles where \(\omega=1\) when \(n=8, 12, 16\) and \(\omega =0\) otherwise. Furthermore this result is sharp and settles a problem proposed by Mamoru Watanabe at the British Combinatorial Conference 1997.

Recommendations

• Covering Orthogonal Polygons with Non-Piercing Rectangles
• How to guard orthogonal polygons: diagonal graphs and vertex covers
• scientific article; zbMATH DE number 29609
• A note on the contractions for orthogonal polygons

Cited in

(2)

• Tilings of orthogonal polygons with similar rectangles or triangles
• Some properties of FAT and THIN grid n-ogons

This page was built for publication: How many diagonal rectangles are needed to cover an orthogonal polygon?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1577551)