Quadratic-time, linear-space algorithms for generating orthogonal polygons with a given number of vertices

Quadratic-Time Linear-Space Algorithms for Generating Orthogonal Polygons with a Given Number of Vertices ⋆ Ana Paula Tom´as ∗,aand Ant´onio Leslie Bajuelos b aDCC-FC & LIACC, University of Porto, Portugal bDepartment of Mathematics & CEOC - Center for Research in Optimization and Control, University of Aveiro, Portugal Key words: Orthogonal Polygons, Generation, Decomposition, Dual Graphs, Mouths. 1. Introduction This work focus on simple polygons without holes. Therefore, we call them just polygons. Moreover, “polygon” will sometimes mean a polygon together with its interior. Pdenotes a polygon and rthe number of its reflex vertices. A polygon is orthogonal (or rectilinear) if its edges meet at right angles. O’Rourke [4] has shown that n= 2r+ 4 for every n-vertex orthogonal polygon (n-ogon, for short). Generic n-ogons may be obtained from a particular kind of n-ogons, that we called grid orthogonal polygons, as illustrated in Fig. 1. Fig. 1. Three 12-ogons mapped to the same grid 12-ogon. Definition 1 An n-ogon Pis in general position iff every horizontal and vertical line contains at most one edge of P, i.e., iff Phas no collinear edges. We call “grid n-ogon” each n-ogon in general position defined in a n 2×n 2square grid. We assume that the grid is defined by horizontal lines y= 1,...,y =n 2and vertical lines x= 1,...,x=n 2and that its northwest corner has ⋆(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] (Ana Paula Tom´as ), [email protected] (Ant´onio Leslie Bajuelos ). coordinates (1,1). Each grid n-ogon has exactly one edge in every line of the grid. 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. Hence, we restrict generation to n-ogons in general position. 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. 1.1. The paper’s contribution We propose two methods that generate grid n-ogons in polynomial time – Inflate-Cut and Inflate-Paste. The former was published in [7], where we also gave implementation details, showing that it requires linear space in nand runs in quadratic time in average. Two programs for generating random orthogonal polygons, by O’Rourke (developed for the evaluation of [5]) and by Filgueiras 1are mentioned there. The main idea of O’Rourke is to construct such a polygon via growth from a seed cell (i.e., unit square) in a board, gluing together a given number of cells that are selected randomly using some heuristics. Filgueiras’ method shares a similar idea though it glues rectangles of larger areas and allows them to overlap. Neither of these methods allows to control the final number of vertices of the polygon. A major idea in Inflate-Paste is also to glue 1personal communication, DCC-LIACC, 2003. 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry rectangles. Nevertheless, it restricts the positions where rectangles may be glued, which renders the algorithm simpler and provides control on the final number of vertices. For the latter purpose, the Inflate transformation is crucial. It is possible to implement Inflate-Paste so that it requires quadratic-time in the worst-case and linear-space. Our methods may be also adapted to generate simple orthogonal polygons with holes. Indeed, each hole is an orthogonal polygon without holes. 2. Inflate, Cut and Paste transformations Let vi= (xi, yi), for i= 1,...,n, be the vertices of a grid n-ogon P, in CCW order. Inflate takes a grid n-ogon Pand a pair of integers (p, q) with p, q ∈[0,n 2], and yields a new n-vertex orthogonal polygon ˜ Pwith vertices ˜vi= (˜xi,˜yi) given by ˜xi=xiif xi≤pand ˜xi=xi+ 1 if xi> p, and ˜yi=yiif yi≤qand ˜yi=yi+ 1 if yi> q, for i= 1,...,n. Thus, it augments the grid, creating two free lines, x=p+ 1 and y=q+ 1. Inflate-Cut: Let Cbe a unit cell in the interior of P, with center cand northwest vertex (p, q). When we apply Inflate to Pusing (p, q), cis mapped to ˜c= (p+ 1, q + 1), that is the center of inflated C. The goal of Cut is to introduce ˜cas reflex vertex of the polygon. To do that, it cuts one rectangle (defined by ˜cand a vertex ˜vmbelonging to one of the four edges shot by the horizontal and vertical rays that emanate from ˜c). We allow such a rectangle to be cut iff it contains no vertex of ˜ P except ˜vm. If no rectangle may be cut, we say that Cut fails for C. So, suppose that ˜sis the point where one of these rays first intersects the boundary of ˜ P, that ˜vm is one of the two vertices on the edge of ˜ Pthat contains ˜sand that the rectangle defined by ˜cand ˜vmmay be cut. Cut cuts this rectangle from ˜ P replacing ˜vmby ˜s, ˜c, ˜s′if this sequence is in CCW order (or ˜s′, ˜c, ˜s, otherwise), with ˜s′= ˜c+(˜vm−˜s). We may conclude that ˜s, ˜c, ˜s′is in CCW order iff ˜s belongs to the edge ˜vm−1˜vmand in CW order iff it belongs to ˜vm˜vm+1.Cut always removes a single vertex of the grid ogon and introduces three new ones. Fig. 2 illustrates this technique. Because Cut never fails if Chas an edge that is part of an edge of P,Inflate-Cut may be always applied to P. 4 Inflate Cell Cut 1 Cut 2 Cut 3 Cut 4 3 21 CC Fig. 2. The two rectangles defined by the center of C and the vertices of the leftmost vertical edge ((1,1),(1,7)) cannot be cut. There remain the four possibilities shown. Inflate-Paste: We first imagine the grid n-ogon merged in a (n 2+ 2) ×(n 2+ 2) square grid, with the top, bottom, leftmost and rightmost grid lines free. The top line is x= 0 and the leftmost one y= 0, so that (0,0) is now the northwest corner of this extended grid. Let eH(vi) represent the horizontal edge of Pto which vibelongs. Definition 2 Given a grid n-ogon Pmerged into a(n 2+ 2) ×(n 2+ 2) square grid, and a convex vertex viof P, the free staircase neighbourhood of vi, denoted by FSN(vi), is the largest staircase polygon in this grid that has vias vertex, does not intersect the interior of Pand its base edge contains eH(vi). An example is given in Fig. 3. 10 11 12 14 1 2 4 6 3 Fig. 3. A grid n-ogon merged into a (n 2+ 2) ×(n 2+ 2) square grid and the free staircase neighbourhood for each of its convex vertices, with n= 14. Now, to transform Pby Inflate-Paste we first take a convex vertex viof P, select a cell C in FSN(vi), and apply Inflate to Pusing the nortwest corner (p, q) of C. As before, the center of cell Cis mapped to ˜c= (p+ 1, q + 1), which will now be a convex vertex of the new polygon. Paste glues the rectangle defined by ˜viand ˜c to ˜ P, increasing the number of vertices by two. If eH(vi)≡vivi+1 then Paste removes ˜vi= (˜xi,˜yi) and inserts the chain (˜xi, q + 1), ˜c, (p+ 1,˜yi) in its place. If eH(vi)≡vi−1vi,Paste replaces ˜viby the sequence (p+ 1,˜yi), ˜c, (˜xi, q + 1). Fig. 4 illustrates this transformation. Clearly, Paste never fails, in contrast to Cut. March 25-26, 2004 Seville (Spain) 10 Fig. 4. The four grid 14-ogons that we may construct if we apply Inflate-Paste to the given 12-ogon, to extend the vertical edge that ends in vertex 10. 3. Inflate-Cut and Inflate-Paste Methods We showed in [7] that every grid n-ogon may be created from a unit square (i.e., the grid 4-ogon) by applying rInflate-Cut transformations. Now, we may show the same result for Inflate-Paste. At iteration k, both methods construct a grid (2k+ 4)-ogon from the grid (2(k−1) + 4)-ogon obtained in the previous iteration, for 1 ≤k≤r. The Inflate-Cut method yields a random grid n-ogon, if cells and rectangles are chosen at random. This is also true for Inflate-Paste, though now for the selections of viand of Cin FSN(vi). It is not difficult to see that both Inflate-Cut and Inflate-Paste yield grid ogons. In contrast, the proof of their completeness is not immediate, as suggested by the example given in Fig. 5. Fig. 5. The rightmost polygon is the unique grid 16-ogon that gives rise to this 18-ogon, if we apply Inflate-Cut. Before we go through the proof, we need to introduce some definitions and results. Definition 3 Given a simple orthogonal polygon Pwithout holes, let ΠH(P)be the horizontal decomposition of Pinto rectangles obtained by extending the horizontal edges incident to reflex vertices towards the interior of Puntil they hit its boundary. Each chord (i.e., edge extension) separates exactly two adjacent pieces (faces), since it makes an horizontal cut (see e.g. [9]). The dual graph of ΠH(P) captures the adjacency relation between pieces of ΠH(P). Its nodes are the pieces of ΠH(P) and its non-oriented edges connect adjacent pieces. Lemma 4 The dual graph of ΠH(P)is a tree for all simple orthogonal polygons Pwithout holes. PROOF. This result follows from the well-known Jordan Curve Theorem. Suppose the graph contains a simple cycle F0, F1,...,Fd, F0, with d≥2. Let γ= (γ0,1γ1,2. . . γd,0) be a simple closed curve in the interior of Pthat links the centroids of the faces F0, F1,...,Fd. Denote by vthe reflex vertex that defines the chord v svthat separates F0from F1. Here, svis the point where this edge’s extension intersects the boundary of P. Either vor sv would be in the interior of γ, because γneeds to cross the horizontal line supporting v svat least twice and just γ0,1crosses v sv. But the interior of γis contained in the interior of P, and there exist points in the exterior of Pin the neighbourhood of vand of sv, so that we achieve a contradiction. ✷ It is worth noting that the vertical decomposition ΠV(P) of Pwould have identical properties. We shall now prove Proposition 5 that asserts the completeness of Inflate-Paste. Proposition 5 For each grid (n+ 2)-ogon, with n≥4, there is a grid n-ogon that yields it by Inflate-Paste. PROOF. Given a grid (n+ 2)-ogon P, we use Lemma 4 to conclude that the dual graph of ΠH(P) is a tree. Each leaf of this tree corresponds to a rectangle that could have been glued by Paste to yield P. Indeed, suppose that v svis the chord that separates a leaf Ffrom the rest of P. Because grid ogons are in general position, svis not a vertex of P. It belongs to the relative interior of an edge of P. The vertex of rectangle Fthat is not adjacent to svwould be ˜cin Inflate-Paste. If we cut F, we would obtain an inflated n-ogon, that we may deflate to get a grid n-ogon that yields P. The two grid lines y=y˜cand x=x˜care free. Clearly svis the vertex we called viin the description of Inflate-Paste (more accurately, svis ˜vi) and c= (x˜c−1, y˜c−1) ∈F SN(vi). ✷ For this paper to be self-contained, we recall now a proof of the completeness of Inflate-Cut, already sketched in [7]. It was inspired by work about convexification of simple polygons [2,6,8], in particular, by a recent paper by O. Aichholzer et al. [1]. It also shares ideas of a proof of Meisters’ Two- Ears Theorem [3] by O’Rourke, though we were not aware of this when we wrote it. Fig. 6 illustrates the fundamental ideas. 20th European Workshop on Computational Geometry pocket pocket A Fig. 6. The two leftmost grids show a grid 18-ogon and its pockets. The shaded rectangle A is a leaf of the tree associated to the vertical partitioning of the largest pocket. The rightmost polygon is an inflated grid 16-ogon that yields the represented grid 18-ogon, if Cut removes rectangle A. We need some additional definitions and results. Definition 6 Apocket of a nonconvex polygon P is a maximal sequence of edges of Pdisjoint from its convex hull except at the endpoints. The lid is the line segment joining its two endpoints. Any nonconvex polygon Phas at least one pocket. Each pocket of an n-ogon, together with its lid, defines a simple polygon without holes, that is almost orthogonal except for an edge (lid). It is possible to slightly transform it to obtain an orthogonal polygon, as illustrated in Fig. 6. We shall refer to this polygon as an orthogonalized pocket. For every orthogonalized pocket Q, it is easy to see that the pocket’s lid is contained in a single rectangle of either ΠH(Q) or ΠV(Q). Let Π(Q) represent the one where the lid is contained in a single piece. Proposition 7 For each grid (n+ 2)-ogon, there is a grid n-ogon that yields it by Inflate-Cut. PROOF. Given a grid (n+ 2)-ogon P, let Qbe an orthogonalized pocket of P. Necessarily, Qis in general position. By Lemma 4 the dual graph of Π(Q) is a tree. We claim that at least one of its leaves contains or is itself a rectangle that might have been removed by Cut to yield P. Indeed, the leaves are of the two following forms. c ~ ~ v m c ~ ~ v m The shaded rectangles are the ones that might have been cut. We have also represented the points that would be ˜vmand ˜cin Inflate-Cut. Here, we must be careful about the leaf that has the pocket’s lid. Only if the tree consists of a single node (c.f. the smallest pocket in Fig. 6), may this leaf be filled. But, every non-degenerated tree has at least two leaves. Then, in this case the tree has a leaf other than the one that contains the lid. ✷ The concept of mouth [8] was crucial to reach the current formulation of Cut. Actually, Inflate- Cut is somehow doing the reverse of an algorithm given by Toussaint in [8] that computes the convex hull of a polygon globbing-up mouths to successively remove its concavities. For orthogonal polygons, we would rather define rectangular mouths. Definition 8 A reflex vertex viof an ogon Pis a rectangular mouth of Piff the interior of the rectangle defined by vi−1and vi+1 is contained in the exterior of Pand neither this rectangle nor its interior contain vertices of P, except vi−1, viand vi+1. To justify the correction of our technique, we observe that when we apply Cut to obtain a grid (n+ 2)-ogon, the vertex ˜cis always a rectangular mouth of the resulting (n+ 2)-ogon. In sum, the proof of Proposition 7 given above justifies Corollary 9, which rephrases the One-Mouth Theorem by Toussaint. Corollary 9 Each grid n-ogon has at least one rectangular mouth, for n≥6. References [1] Aichholzer, O., Cort´es, C., Demaine, E. D., Dujmovic, V., Erickson, J., Meijer, H., Overmars, M., Palop, B., Ramaswawi, S., Toussaint, G. T.: Flipturning polygons. Discrete & Comput. Geometry 28 (2002), 231–253. [2] Erd¨os, P.: Problem number 3763. American Mathematical Monthly 42 (1935) 627. [3] Meisters, G. H.: Polygons have ears. American Mathematical Monthly 82 (1975) 648-651. [4] O’Rourke, J.: An alternate proof of the rectilinear art gallery theorem. J. of Geometry 21 (1983) 118–130. [5] O’Rourke, J., Pashchenko, I., Tewari, G.: Partitioning orthogonal polygons into fat rectangles. In Proc. 13th Canadian Conference on Computational Geometry (CCCG’01) (2001) 133-136. [6] Sz.-Nagy, B.: Solution of problem 3763. American Mathematical Monthly 46 (1939) 176–177. [7] Tom´as, A. P., Bajuelos, A. L.: Generating Random Orthogonal Polygons. To appear in Post-conference Proceedings of CAEPIA-TTIA’2003, LNAI, Springer- Verlag (2004). [8] Toussaint, G. T.: Polygons are anthropomorphic. American Mathematical Monthly 122 (1991) 31–35. [9] Urrutia, J.: Art gallery and illumination problems. In J.-R. Sack and J. Urrutia, editors, Handbook on Computational Geometry. Elsevier (2000).