Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces

PartitioningOrthogonalPolygonsbyExtensionofAllEdgesIncident to Reflex Vertices: lower and upper bounds on the number of pieces ⋆ Ant´onio Leslie Bajuelos a, Ana Paula Tom´as ∗,band F´abio Marques c aDepartment of Mathematics & CEOC - Center for Research in Optimization and Control, University of Aveiro, Portugal bDCC-FC & LIACC, University of Porto, Portugal cSchool of Technology and Management, University of Aveiro, Portugal Abstract Given an orthogonal polygon P, let |Π(P)|be the number of rectangles that result when we partition Pby extending the edges incident to reflex vertices towards INT(P). In [4] we showed that |Π(P)| ≤ 1 + r+r2, where ris 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. Key words: Orthogonal Polygons, Decomposition, Rectilinear Cut, Square Grid. 1. Introduction We shall call simple polygon Pa region of a plane enclosed by a finite collection of straight line segments forming a simple cycle. This paper deals only with simple polygons, so that we call them just polygons, in the sequel. We will denote the interior of the polygon Pby INT(P) and the boundary by BND(P). The boundary shall be considered part of the polygon, that is P= INT(P)∪BND(P). A vertex is called convex if the interior angle between its two incident edges is at most π; otherwise it is called reflex (or concave). We use rto represent the number of reflex vertices of P. A polygon is called orthogonal (or rectilinear) iff its edges meet at right angles. O’Rourke [2] has shown that n= 2r+ 4 for every n-vertex orthogonal polygon (n-ogon, for short). ⋆(Extended abstract) Partially funded by LIACC through Programa de Financiamento Plurianual, Funda¸c˜ao para a Ciˆencia e Tecnologia (FCT) and Programa POSI, and by CEOC (Univ. of Aveiro) through Programa POCTI, FCT, co-financed by EC fund FEDER. ∗Corresponding author Email addresses: [email protected] (Ant´onio Leslie Bajuelos ), [email protected] (Ana Paula Tom´as ), [email protected] (F´abio Marques ). Definition 1 A rectilinear cut of an n-ogon Pis obtained by extending each edge incident to a reflex vertex of Ptowards INT(P)until it hits BND(P). We denote this partition by Π(P)and the number of its elements (pieces) by |Π(P)|. Each piece is a rectangle, so that we call it r-piece. Generic n-ogons may be obtained from a particular kind of n-ogons – the so-called grid orthogonal polygons [3], as illustrated in Fig. 1 (The reader may skip Definition 2 and Lemmas 3 and 4 if he/she has already read [3].) Fig. 1. Three 12-ogons mapped to the same grid 12-ogon. Definition 2 An n-ogon Pis in general position iff Phas no collinear edges. We call “grid n-ogon” each n-ogon in general position defined in a n 2×n 2 square grid. Lemma 3 follows immediately from this definition. Lemma 3 Each grid n-ogon has exactly one edge in every line of the grid. 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry Each n-ogon not in general position may be mapped to an n-ogon in general position by ǫ-perturbations, for a sufficiently small constant ǫ > 0. Consequently, we shall first address n-ogons in general position. Lemma 4 Each n-ogon in general position is mapped to a unique grid n-ogon through top-to- bottom and left-to-right sweeping. And, reciprocally, given a grid n-ogon we may create an n-ogon that is an instance of its class by randomly spacing the grid lines in such a way that their relative order is kept. The number of classes may be further reduced if we group grid n-ogons that are symmetrically equivalent. In this way, the grid n-ogons in Fig. 2 represent the same class. Fig. 2. Eight grid n-ogons that are symmetrically equivalent. From left to right, we see images by clockwise rotations of 90◦, 180◦and 270◦, by flips wrt horizontal and vertical axes and flips wrt positive and negative diagonals. Definition 5 Given an n-ogon Pin general position, GRID(P)denotes any grid n-ogon in the class that contains the grid n-ogon to which Pis mapped by the sweep procedure described in Lemma 4 The following result is a trivial consequence of the definition of GRID(P). Lemma 6 For all n-ogons Pin general position, |Π(P)|=|Π(GRID(P))|. 2. Lower and Upper bounds on |Π(P)| In [4] we showed that Π(P) has at most 1+r+r2 pieces. Later we noted that this upper bound is not sufficiently tightened. Actually, for small values of r, namely r= 3,4,5,6,7, we experimentally found that the difference between 1 + r+r2and max |Π(P)|was 1, 2, 4, 6 and 9, respectively. Definition 7 A grid n-ogon Qis called FAT iff |Π(Q)| ≥ |Π(P)|, for all grid n-ogons P. Similarly, a grid n-ogon Qis called THIN iff |Π(Q)| ≤ |Π(P)|, for all grid n-ogons P. The experimental results supported our conjecture that there was a single FAT n-ogon (except for symmetries of the grid) and that it had the form illustrated in Fig. 3. Fig. 3. The unique FAT n-ogons (symmetries excluded), for n= 4,6,8,10,12. Clearly, each piece r-piece is defined by four vertices. Each vertex is either in INT(P) (internal vertex) or is in BND(P) (boundary vertex). Similar definitions hold for edges. An edge eof r-piece R is called an internal edge if e∩INT(P)6=∅, and it is called boundary edge otherwise. Lemma 8 The total number |Vi|of internal vertices in Π(P), when the grid n-ogon Pis as illustrated in Fig. 3 is given by (1) |Vi|=     3r2−2r 4,for reven (3r+ 1)(r−1) 4,for rodd (1) where ris the number of reflex vertices of P. PROOF. In case ris even, |Vi|= 2 r 2 X k=1 (r−k) and in case ris odd |Vi|= (r−r+ 1 2) + 2 r−1 2 X k=1 (r−k) ✷ Proposition 9 Every n-vertex orthogonal polygon Psuch that the number of internal vertices of Π(P)is given by (1) has at most a single reflex vertex in each horizontal and vertical line. PROOF. We shall suppose first that Pis a grid n-ogon. Then, let vL1= (xL1, yL1) and vR1= (xR1, yR1) be leftmost and rightmost reflex vertices of P, respectively. The horizontal chord with origin at vL1can intersect at most xR1−xL1vertical chords, since we shall not count the intersection with the vertical chord defined by vL1. The same may be said about the the horizontal chord with origin at vR1. There are exactly rvertical and r horizontal chords, and thus xR1−xL1≤r−1. If there were cvertical edges such that both extreme points are reflex vertices then xR1−xL1≤r−1−c. March 25-26, 2004 Seville (Spain) This would imply that the number of internal vertices of Π(P) would be strictly smaller than the value defined by (1). Indeed, we could proceed to consider the second leftmost vertex (for x > xL1), say vL2, then the second rightmost vertex (with x < xR1) and so forth. The horizontal chord that vL2defines either intersects only the vertical chord defined by vL1or it does not intersect it at all. So, it intersects at most r−2−cvertical chords. In sum, cshould be null, and by symmetry, we would conclude that there is exactly a reflex vertex in each vertical grid line (for x > 1 and x < n 2=r+ 2). Now, if Pis not a grid n-ogon but is in general position, then Π(P) has the same combinatorial structure as Π(GRID(P)), so that we do not have to prove anything more. If Pis not in general position, then let we render it in general position by a sufficiently small ǫ-perturbation, so that the partition of this latter polygon would not have less internal vertices than Π(P). ✷ Corollary 10 For all grid n-ogons P, the number of internal vertices of Π(P)is less than or equal to the value established by (1). PROOF. It results from the proof of Proposition 9. ✷ Theorem 11 Let Pbe a grid n-ogon, r=n−4 2the number of its reflex vertices. If Pis FAT then |Π(P)|=     3r2+ 6r+ 4 4,for reven 3(r+ 1)2 4,for rodd and if Pis THIN then |Π(P)|= 2r+ 1. PROOF. Suppose that Pis a grid n-ogon. Let V,Eand Fbe the sets of all vertices, edges and faces of Π(P), respectively. Let us denote by Viand Vbthe sets of all internal and boundary vertices of the pieces of Π(P). Similarly, Eiand Ebrepresent the sets of all internal and boundary edges of such pieces. Then, V=Vi∪Vband E=Ei∪Eb. Being Pin general position, each chord we draw to form Π(P) hits BND(P) in the interior of an edge and no two chords hit BND(P) in the same point. Hence, using O’Rourke’s formula [2] we obtain |Eb|=|Vb|= (2r+ 4) + 2r= 4r+ 4. It is easily seen that to obtain a FAT n-ogon we must maximize the number of internal vertices. By Corollary 10, max P|Vi|=     3r2−2r 4,for reven (3r+ 1)(r−1) 4,for rodd and, therefore, maxP|V|= maxP(|Vi|+|Vb|) is given by max P|V|=     3r2+ 14r+ 16 4,for reven 3r2+ 14r+ 15 4,for rodd From Graph Theory [1] we know that the sum of the degrees of vertices in a graph is twice the number of its edges, that is, Pv∈Vδ(v) = 2|E|. Using the definitions of grid n-ogon and of Π(P), we may partition Vas V=Vc∪Vr∪(Vb\(Vc∪Vr)) ∪Vi Vrand Vcrepresenting the sets of reflex and of convex vertices of P, respectively. Moreover, we may conclude that δ(v) = 4 for all v∈Vr∪Vi, δ(v) = 3 for all v∈Vb\(Vc∪Vr) and δ(v) = 2 for all v∈Vc. Hence, 2|E|=X v∈Vr∪Vi δ(v) + X v∈Vc δ(v) + X v∈Vb\(Vc∪Vr) δ(v) = 4|Vi|+ 4|Vr|+ 2|Vc|+ 3(|Vb| − |Vr| − |Vc|) = 4|Vi|+ 12r+ 8 and, consequently, |E|= 2|Vi|+ 6r+ 4. Similarly, to obtain THIN n-ogons we must minimize the number of internal vertices of the arrangement. For all n, there are grid n-ogons such that |Vi|= 0. Thus, for THIN n-ogons |V|= 4r+ 4. Finally, to conclude the proof, we have to deduce the expression of the upper and lower bound of the number of faces of Π(P), that is of |Π(P)|. Using Euler’s formula |F|= 1 + |E| − |V|, and the expressions deduced above, we have maxP|F|= 1 + 2(maxP|Vi|) + 6r+ 4 −maxP|V|. That is, maxP|F|= maxP|Vi|+ 6r+ 5, so that max P|F|=     3r2+ 6r+ 4 4,for reven 3(r+ 1)2 4,for rodd and 20th European Workshop on Computational Geometry min P|F|= 1 + 2(min P|Vi|) + 6r+ 4 −min P|V| = 1 + 6r+ 4 −4r−4 = 2r+ 1 The existence of FAT grid n-ogons and THIN grid n-ogons for all n(such that nis even and n≥4) follows from Lemma 8 and the construction indicated in Fig. 5, respectively. ✷ Figs. 4 and 5 show some THIN n-ogons. Fig. 4. Some grid n-gons with |Vi|= 0. Fig. 5. Constructing the grid ogons of the smallest area, for r= 0,1,2,3,4,. . . . The area is 2r+ 1. Based on the proof of Proposition 9, we may prove the uniqueness of FATs and fully characterize them. Proposition 12 There is a single FAT n-ogon (except for symmetries of the grid) and its form is illustrated in Fig. 3. PROOF. We saw that FAT n-ogons must have a single reflex vertex in each vertical grid-line, for x > 1 and x < n 2. Also, the horizontal chords with origins at the reflex vertices that have x= 2 and x=n 2−1 = r+1, determine 2(r−1) internal points (by intersections with vertical chords). To achieve this value, they must be positioned as illustrated below on the left. 1 2 r+1 r+2 1 2 r+1 r+2r 3 Moreover, the reflex vertices on the vertical gridlines x= 3 and x=radd 2(r−2) internal points. To achieve that, we may conclude by some simple case reasoning, that vL2must be below vL1and vR2 must be above vR1, as shown above on the right. And, so forth. . . ✷ The area A(P) of a grid n-ogon Pis the number of grid cells in its interior. FATs are not the grid n-ogons that have the largest area, except for small values of n, as we may see in Fig 6. Fig. 6. On the left we see the FAT grid 14-ogon. It has area 27, whereas the grid 14-ogon on the right has area 28, which is the maximum. Proposition 13 Let Pbe any grid n-ogon with n≥8and rreflex vertices (r=n−4 2, for all P). Then 2r+ 1 ≤A(P)≤r2+ 3 and there exist grid n-ogons having area 2r+ 1 (indeed, a single one except for symmetries) and grid n-ogons having area r2+ 3. PROOF. Our proof is strongly based on the Inflate-Paste method for generating grid ogons, that will be presented also at this workshop [3]. ✷ References [1] Bondy, J., Murty, U.: Graph Theory with Applications. Elseiver Science, New York, (1976). [2] O’Rourke, J.: An alternate proof of the rectilinear art gallery theorem. J. of Geometry 21 (1983) 118–130. [3] Tom´as, A. P., Bajuelos, A. L.: Quadratic-time linearspace algorithms for generating orthogonal polygons with a given number of vertices. (Extended abstract) In Proceedings European Workshop on Computational Geometry (2004). (This book) [4] Tom´as, A. P., Bajuelos, A. L., Marques, F.: Approximation algorithms to minimum vertex cover problems on polygons and terrains. In P.M.A Sloot et al. (Eds): Proc. of ICCS 2003, LNCS 2657, Springer- Verlag (2003) 869-878.