Partitioning Orthogonal Polygons by Extension of All Edges Incident to Reflex Vertices: Lower and Upper Bounds on the Number of Pieces

摘要

Given an orthogonal polygon P, let |Π(P)| be the number of rectangles that result when we partition P by extending the edges incident to reflex vertices towards INT(P). In [4] we have shown that |Π(P)| ≤ 1 + r + r~2, where r is the number of reflex vertices of P. We shall now give sharper bounds both for maxp |Π(P)| and minp |Π(P)|. Moreover, we characterize the structure of orthogonal polygons in general position for which these new bounds are exact. We also present bounds on the area of grid n-ogons and characterize those having the largest and the smallest area.