On Fully Characterizing Terrain Visibility Graphs by Noushin Saeedi Bidokhti B.Sc., Sharif University of Technology, 2008 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Computer Science) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) March 2012 c© Noushin Saeedi Bidokhti 2012 Abstract A terrain is an x-monotone polygonal line in the xy-plane. Two vertices of a terrain are mutually visible if and only if they are adjacent or the line segment that connects them lies above the terrain (except at its endpoints). A graph whose vertices represent terrain vertices and whose edges repre- sent mutually visible pairs of terrain vertices is called a terrain visibility graph. Understanding the graph theoretic properties of all terrain visibility graphs may help us understand the combinatorial structure of these geomet- ric objects and help to address problems related to geometric visibility. The properties that are true of all terrain visibility graphs are called necessary properties. The set of properties that, if true, imply that a graph is a terrain visibility graph is called a sufficient set. We would like to find properties that are both necessary and sufficient; that is, we would like to characterize, graph theoretically, terrain visibility graphs. Abello et al. [Discrete and Computational Geometry,14(3):331–358,1995] studied the core induced subgraphs of the visibility graphs of staircase poly- gons, which are exactly the class of terrain visibility graphs. They showed that the visibility between vertices in such structures implies some ordering requirements on the slopes of the lines that connect pairs of vertices in any realization. They approached the problem of whether certain graph prop- erties are sufficient by creating a slope order on the lines that connect all pairs of polygon vertices (in a possible realization) such that the slope order is consistent with the desired visibility graph. The main contribution of our work is to give a much simpler proof that these properties guarantee such a slope ordering. Our proof consequently gives a faster algorithm for con- structing this slope order. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Description of results . . . . . . . . . . . . . . . . . . . . . . 3 2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Restricting the class of graphs . . . . . . . . . . . . . . . . . 5 2.2 Restricting the class of polygons . . . . . . . . . . . . . . . . 5 2.3 Adding extra information . . . . . . . . . . . . . . . . . . . . 7 3 Necessary properties for terrain visibility graphs . . . . . . 14 3.1 Graph property definitions . . . . . . . . . . . . . . . . . . . 14 3.2 Necessary conditions . . . . . . . . . . . . . . . . . . . . . . . 15 4 On the sufficiency of the persistent property . . . . . . . . 17 4.1 Representation of the slope order . . . . . . . . . . . . . . . 18 4.2 Abello et al.’s approach . . . . . . . . . . . . . . . . . . . . . 20 4.3 Our main result . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.3.1 Orienting the triples . . . . . . . . . . . . . . . . . . . 21 4.3.2 The M-tableau relation digraph DM . . . . . . . . . . 26 4.3.3 The digraph DM is acyclic — proof 1 . . . . . . . . . 26 4.3.4 The digraph DM is acyclic — proof 2 . . . . . . . . . 34 5 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . 39 iii Table of Contents Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 iv List of Figures 3.1 X-property in terrain visibility graphs. . . . . . . . . . . . . 16 3.2 Bar-property in terrain visibility graphs. . . . . . . . . . . . 16 4.1 A balanced tableau and its skeleton. . . . . . . . . . . . . . . 19 4.2 The abc-hook and the half-strict abc-rectangle. . . . . . . . . 21 4.3 Possible structures of an abc-hook. . . . . . . . . . . . . . . . . 22 4.4 Possible structures of a half-strict abc-rectangle. . . . . . . . . 23 4.5 The bar-property implies M [[a..b); (c..d]] is a zero matrix. . . . 24 4.6 Orientation function αM and the implied inequality relations. 24 4.7 The triple orientations agree with the conditions in Lemma 3. 25 4.8 No cycle lies completely in the same row . . . . . . . . . . . . 27 4.9 The properties of DM . . . . . . . . . . . . . . . . . . . . . . . 29 4.10 The black path implies the existence of the red edge. . . . . . 30 4.11 The case when bm is greater than both b0 and bk. . . . . . . . 31 4.12 The cases bm = b0 and bm = bk. . . . . . . . . . . . . . . . . . 32 4.13 The contradiction if DM were cyclic. . . . . . . . . . . . . . . 33 4.14 Monotone orientation sequences. . . . . . . . . . . . . . . . . 35 4.15 Case 1: αM (bcd) = +. . . . . . . . . . . . . . . . . . . . . . . 36 4.16 Case 2.1: αM (bcd) = −, αM (acd) = −, and αM (abd) = +. . . 37 4.17 Case 2.2: αM (bcd) = − and αM (acd) = +. . . . . . . . . . . . 38 5.1 The relation between pre-CC systems, CC systems, and 3- signotopes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.2 A triple orientation of a smaller graph may not be extensible. 43 v Acknowledgements First and foremost I would like to thank my supervisor, Prof. William Evans. His inspiration and support gave me the opportunity and motivation to explore very interesting research problems. I learned a lot from our discussions on the problems. I thank him for his understanding, great advice, patience, generosity with his time, and his invaluable support during my studies. I have enjoyed working with him a lot and I am truly indebted to him for being a great mentor, both professionally and personally. I would like to extend my gratitude to my second reader, Prof. David Kirkpatrick, for his helpful comments. I thank the faculty members and my colleagues in the Beta Lab who have made my M.Sc. studies at the University of British Columbia more enjoyable. I also thank Holly Kwan and Lara Hall for always being helpful. I would also like to thank Prof. Janos Pach, Radoslav Fulek, and other people in the Discrete and Computational Geometry Group at EPFL (École Polytechnique Fédérale de Lausanne), where I did an internship last year. It has been a pleasure working with them. It helped me improve my research abilities, and made me more determined in my career. I thank Janos for his valuable advice. Many people supported me during my stay in Vancouver and helped make life more fun. Thanks to Monir Hajiaghayi, Ali Mahmoudzadeh, Par- nian Alimi, Niousha Bolanzadeh, Azin Dastpak, Amirhossein Mehrabian, Zohreh Jabbari, Pantea Jabbari, Babak Bostan, Ida Karimfazli, Behrooz Yousefzadeh, Nima Taherinejad, Mona Haraty, Syavash Nobarany, and Yas- saman Sefidgar. I would also very much like to thank my aunt Pari and my cousins Taymaz and Tara for their true kindness and invaluable support during my time in Vancouver. Finally, I owe my especial thanks to my dearest parents Sima and Mah- moud and my caring sister Shirin for their unconditional love and support. I have learned the most from them. Their inspiration, love, support, advice, and trust have made me who I am today, and I am deeply grateful to them for each day of my life, and for all their sacrifices. vi For my parents and sister vii Chapter 1 Introduction Problems related to geometric visibility have arisen from applications in graphics and motion planning in robotics. In graphics, for example, the hidden line problem for computer-drawn polyhedra is to determine which edges, or parts of edges, of a polyhedra are visible from a given vantage point. In robotics or more specifically motion planning, we would like to find the shortest path between two positions for a robot without hitting the objects around. Visibility problems include the well-known art-gallery problems: planning a path for a guard so that it can protect the entire art gallery, or determining the minimum number of the guards which together can observe the whole art gallery. It is conceivable that understanding the combinatorial structure of visi- bility is needed before addressing problems involving visibility in computa- tional geometry. A visibility graph is a fundamental combinatorial structure which has proven useful for addressing such problems. The vertices of a visibility graph correspond to geometric components such as points or line segments. There is an edge between two vertices of the graph if the com- ponents are visible to each other. There are variations in the definition of visibility depending on the underlying application. For the class of art gallery problems, the vertex visibility graph of polygons is more commonly used. Here, the geometric components are the vertices of the polygon, and two vertices are visible if and only if the line segment connecting them is in the interior or along the boundary of the polygon. Throughout this the- sis, by the term visibility graph, we mean the vertex visibility graph of the geometric object unless otherwise stated. Visibility graphs have been used to find the shortest path between two vertices of a polygon that goes through the inside of the polygon. Such a path is a subgraph of the visibility graph [46]. Thus, we may construct the visibility graph of the polygon and simply find the shortest path between two vertices in the graph. Since computing the visibility graph takes linear time [41] in the size of the graph, this is a reasonably efficient method. Ideally, we would like to fully understand the combinatorial properties of visibility in polygons. The properties that are true of all visibility graphs are 1 1.1. Problem statement called necessary properties. The set of properties that, if true, imply that a graph is a visibility graph is called a sufficient set. If a graph satisfies the sufficient graph theoretic properties, it is realizable as a visibility graph of a polygon. We would like to find properties that are both necessary and suf- ficient; that is, we would like to characterize, graph theoretically, visibility graphs. There is a close relation between characterization and recognition of a class of graphs. A recognition algorithm for a class of graphs is an al- gorithmic characterization of that class. Studying the recognition and char- acterization of visibility graphs may help us find more efficient algorithms for problems related to geometric visibility. Although there are some partial results for restricted polygons, no char- acterization of visibility graphs of simple polygons is available in general. It may be useful to separate the characterization problem into two parts: First find combinatorial conditions on point sets representing the vertices of a visibility graph that obeys certain graph theoretic properties; then decide if a point set with these combinatorial conditions is realizable. Such combi- natorial conditions may be interpreted in the language of oriented matroids. Several important and hard realizability problems of combinatorial geome- try can be reduced to the realizability problem of oriented matroids. The realizability problem for oriented matroids in general is NP-hard. However, the graph theoretic properties of polygon visibility graphs make the family of the oriented matroid representations restricted. It may be possible that the realizability problem for such oriented matroids is easier to address. 1.1 Problem statement A one-dimensional terrain is an x-monotone polygonal line in the xy-plane. The endpoints of the terrain line segments mark terrain vertices. Two ver- tices of a terrain are mutually visible if and only if they are adjacent in the terrain or the line segment that connects them lies above the terrain (except at its endpoints). The visibility graph of a terrain with n vertices is the undirected graph with vertex set [n] ≡ {1, 2, . . . , n} and edges {{a, b} | the ath and bth terrain vertices are mutually visible}. The ath vertex of the ter- rain is the vertex with the ath smallest x-coordinate. (The vertex numbers in the terrain visibility graph give the ordering of vertices along the terrain.) We want to use graph theoretic properties to fully characterize terrain visibility graphs; that is we would like to find properties that are both neces- sary and sufficient for a graph to be a terrain visibility graph. It is relatively simple to show that all terrain visibility graphs satisfy three properties de- 2 1.2. Description of results scribed in Chapter 3. It is much harder to show that all graphs with these three properties are terrain visibility graphs. In fact, though Abello, et al. [4] claimed this result, a complete proof has never been published. 1.2 Description of results We give a streamlined proof of a step towards characterizing terrain visibility graphs. Abello et al. [Discrete and Computational Geometry,14(3):331–358,1995] studied the core induced subgraphs of the visibility graphs of staircase poly- gons, which are exactly the class of terrain visibility graphs. (See the defi- nitions at the start of Section 2.2.) They showed that the visibility between vertices in such structures implies some ordering requirements on the slopes of the lines that connect pairs of vertices in any realization. They approached the problem of whether certain graph properties are sufficient by creating a slope order on the lines that connect all pairs of polygon vertices (in a possible realization) such that the slope order is consistent with the desired visibility graph. The main contribution of our work is to give a much sim- pler proof that these properties guarantee such a slope ordering. Our proof consequently gives a faster algorithm for constructing this slope order. Our approach is to establish an orientation on every triple of terrain ver- tices such that they are consistent with the desired visibility graph. For three points a < b < c, the orientation of the triple (a, b, c) determines whether b lies above or below the line through a and c. Such a triple orientation implies an ordering on the slopes of the three lines connecting these points. We de- fine our orientation such that the resulting slope ordering requirements are consistent with the desired visibility graph, and show that the requirements induced by the set of all these triple orientations are globally consistent and form a global slope order on all lines. We clarify the implications of the graph theoretic properties on the or- dering of the slopes. Moreover, we show that our orientation has specific properties that forbid certain substructures in the point set realizing it. This may help prove realizability. In Chapter 5, we interpret our orientation as defining properties on an underlying oriented matroid. 3 Chapter 2 Related work There have been extensive studies to better understand visibility graphs. The visibility may be defined among the vertices of a polygon, line segments in the plane, or various other geometric objects in two or higher dimensions. O’Rourke [49], and Ghosh and Goswami [37] give an excellent review of research on visibility graphs. Ghosh’s book [36] is also a good detailed source of information on visibility graphs. Considerable literature exists on construction of visibility graphs. For a simple polygon, there are efficient algorithms to compute the visibility graph. Asano et al. [10] and Welzl [64] have O(n2) algorithms to find the visibility graph of an n-vertex polygon. Hershberger [41] presents an O(m+ n log logn) algorithm where m is the number of edges in the visibility graph. The term O(n log log n) reflects the time to triangulate a polygon using the algorithm of Tarjan and Van Wyk [62]. Chazelle [20] gives a linear triangulation algorithm, thus Hershberger’s result becomes O(m+n) which is in fact O(m). Other visibility problems that have been studied involve the characteri- zation and recognition problems. There is no polynomial algorithm known to recognize visibility graphs (that is, to decide whether a given graph is the visibility graph of some polygon). Nor is the problem known to be NP-hard, or even in NP. Everett [29] expresses the recognition problem for visibility graphs as a sentence in the existential theory of the reals, and shows that the problem can be solved in PSPACE. Characterizing visibility graphs and finding algorithms to recognize them seem challenging. The class of visibility graphs does not lie in any of the well-known classes of graphs such as planar graphs, chordal, circle or perfect graphs [29, 35]. Everett [29] shows that there is no finite set of forbidden induced subgraphs which characterizes visibility graphs. Results on visibility graphs so far have involved restricting the class of graphs, or restricting the class of polygons, or adding extra information to the graph. 4 2.1. Restricting the class of graphs 2.1 Restricting the class of graphs ElGindy [28] shows that any maximal outerplanar graph is a visibility graph. A graph is outerplanar if it has a planar representation with all the vertices on the outer face. A maximal outerplanar graph is an outerplanar graph such that the addition of any arc results in a graph that is not outerplanar. A triangulation of a simple polygon is a maximal outerplanar graph. Thus the visibility graph of any simple polygon on n vertices is a supergraph of an n vertex maximal outerplanar graph [29]. ElGindy provides a linear time embedding algorithm to construct a uni-monotone polygon such that its visibility graph is identical to any desired maximal outerplanar graph. A monotone polygonal chain is a set of vertices in the plane, ordered along some direction, with consecutive vertices joined. A polygon is monotone if it can be broken into two monotone polygonal chains (both ordered along the same direction). A uni-monotone polygon is a monotone polygon where one chain consists of a single edge. A terrain, whose visibility properties we study in this thesis, is essentially the same as a monotone polygonal chain (the only difference is that we consider terrains to be monotone in the horizontal direction). Colley [24] extends the range of graphs that can be identified as visibility graphs. He defines a new class of graphs, tree of cliques graphs, and presents an algorithm to recognize these graphs. A tree of cliques graph is formed by replacing each face of a two-connected outerplanar graph (except for the outerface) with a clique on the same vertices. He proves that all tree of cliques graphs are visibility graphs by giving an embedding algorithm that constructs a uni-monotone polygon with the required visibility. His algo- rithm is an extension of ElGindy’s algorithm. Both ElGindy’s and Colley’s algorithms can be modified to create a uniform uni-monotone polygon (that is, a uni-monotone polygon whose vertices are uniformly spaced in the di- rection of monotonicity). Not every uniform uni-monotone polygon has a tree of cliques visibility graph. 2.2 Restricting the class of polygons A staircase polygon is a polygon consisting of alternate horizontal and verti- cal edges which is formed by a polygonal chain leading down and to the right plus the two additional edges required to complete a polygon. These poly- gons are also known as orthogonal convex fans. A convex fan is a polygon that has a convex vertex visible to all other vertices (that is, has a convex 5 2.2. Restricting the class of polygons kernel vertex). An orthogonal convex fan is a convex fan consisting of only horizontal and vertical edges. The core of a staircase polygon is formed by the reflex vertices plus the vertices adjacent to the kernel vertex. A uniform step length staircase polygon is a staircase polygon whose vertices are evenly spaced with respect to the horizontal direction. Abello and Egecioglu [2] give a polynomial time recognition algorithm, using linear programming, to recognize visibility graphs of uniform step length staircase polygons. Using this method, they show that there exist graphs that are visibility graphs of staircase polygons but realizable only if not all polygon vertices are uniformly spaced. Colley [24, 25] proves a strong relationship between the visibility graphs of uni-monotone polygons and staircase polygons, which turns up in the recognition problems. Colley defines skew transformations, which move the points in the xy-plane vertically an amount proportional to their x- coordinate, and shows that skew transformations do not affect visibility (as they do not affect the collinearity of points). He uses the result to show that recognizing the visibility graph of a staircase polygon is equivalent, under linear-time reduction, to the problem of recognizing the visibility graph of a monotone polygonal chain, where the additional information of the order of the vertices on the chain is given. The vertex ordering of the core of a staircase polygon is determined by the visibility graph of the staircase poly- gon. A crucial part of his argument is that the core induced subgraph of the visibility graph of a staircase polygon is identical to the visibility graph of a monotone polygonal chain (or equivalently a terrain visibility graph), and vice versa. Using this and the result from Abello and Egecioglu [2], Colley shows that the visibility graphs of uniform uni-monotone polygons are a strict subset of the visibility graphs of general uni-monotone polygons, if the outside face of the polygon is fixed. There have been few results that give a graph theoretic characterization of visibility graphs for restricted classes of polygons. Everett and Corneil [30] characterize the visibility graphs of 1-spiral polygons and show they are a subclass of interval graphs, and hence are perfect. A polygon is k-spiral if its boundary contains at most k concave chains. They give a linear time algo- rithm for recognizing the visibility graphs of 1-spiral polygons. Everett [29] shows that visibility graphs of 2-spiral polygons are perfect1. This is not true of k-spiral polygons for k > 2. She also shows that the visibility graph 1She shows that they are perfect if the strong perfect graph conjecture is true. The conjecture was proposed by Berge [13] in 1963 and some forty years later, it was proved by Chudnovsky et al. [23]. 6 2.3. Adding extra information of a convex polygon with a single convex hole is a circular arc graph. A circular arc graph is the intersection graph of a collection of arcs on a circle. Colley et al. [26] characterize the visibility graphs of towers. A tower is a polygon formed by two reflex chains sharing one common endpoint, plus one edge joining the other endpoints of the chains. They present a linear time algorithm to recognize visibility graphs of towers, and tie these visibility graphs to bipartite permutation graphs. There is an exponential lower bound and a doubly exponential upper bound on the grid size required to realize the visibility graphs of towers, by results from Lin and Skiena [45] and Colley et al. [26]. Visibility graphs of towers are also characterized by Choi et al. [22], where they use the term funnel instead of tower. They give a linear time algorithm to recognize the visibility graph of a funnel and to reconstruct the funnel from its visibility graph. They show that the visibility graphs of funnels are weakly triangulated and therefore perfect. Abello and Kumar [6] give a characterization of the visibility graphs of the class of 2-spiral polygons when extra information is added to the graph. We discuss this result later in the next section. 2.3 Adding extra information Many results on visibility graphs involve adding extra information to the graphs. Originally Ghosh [34] conjectured three necessary conditions for recognizing visibility graphs of simple polygons, when the Hamiltonian cycle forming the polygon boundary is specified. Everett [29] gave a counterexam- ple to this conjecture and suggested a stronger version of the third necessary condition, which Srinivasaraghavan and Mukhopadhyay [56] proved is indeed necessary. Abello et al. [9] showed that, even with the stronger version of the third condition, the necessary conditions are insufficient. Ghosh [35] iden- tified another necessary condition to circumvent the new counterexample. (Meanwhile, Abello and Kumar [7] proposed four other necessary conditions, but Ghosh [35] showed that all of them follow from his third and fourth con- ditions.) Ghosh conjectured that the four necessary conditions are sufficient. The first three conditions can be tested in polynomial time [29, 35, 37]. Al- though Vijay [63] claimed to have shown a polynomial time algorithm to test the fourth condition, whether this property can be tested in polynomial time is still open [37]. Later, Streinu [59] proved Ghosh’s conjecture [35] is false. Coullard and Lubiw [27] introduced further necessary conditions for a graph to be a visibility graph. They developed a new structural property 7 2.3. Adding extra information of visibility graphs: Each 3-connected component of a visibility graph has a vertex ordering in which every vertex is adjacent to a previous 3-clique; that is, each 3-connected component of a visibility graph has a 3-clique ordering. The weaker result that each vertex is adjacent to a previous 2-clique is a consequence of polygon triangulation. The 3-clique ordering property is not sufficient. The property can be tested in polynomial time, and is used to give an algorithm for the distance visibility graph problem, which is the problem of whether an edge-weighted graph is the visibility graph of a simple polygon with the weights as Euclidean distances [27]. They proved each 3-connected component of a visibility graph is a visibility graph, and that every 3-connected visibility graph has a 3-clique ordering. They used this to reconstruct unique polygon representations for the 3-connected components (each vertex is adjacent to at least three old fixed vertices so the position of the new vertex is fixed), and showed how to reconstruct a polygon representation for the whole graph by pasting them together. ElGindy [28] conjectured a characterization of visibility graphs of convex fans. He suggested a decomposition strategy and gave an algorithm to check whether a graph is the visibility graph of a convex fan, when the Hamiltonian cycle forming the boundary is known. However, the reconstruction appears tricky and the correctness of the algorithm is not clear. Abello et al. [3, 4] claimed to have characterized visibility graphs of stair- case polygons (or equivalently orthogonal convex fans) in a series of two papers, only one of which has appeared in the literature. The preliminary results by Abello et al.[8] are precursors to these two papers. Abello et al.[4] presented a necessary property for such visibility graphs, which was called the persistent property. They showed that the visibility between vertices in such structures implies some ordering requirements on the slopes of the lines that connect pairs of vertices in any realization. They approached the problem of whether the persistent property is sufficient, given the Hamilto- nian cycle forming the boundary, by creating a slope order on the lines that connect all pairs of polygon vertices (in a possible realization) such that the slope order is consistent with the desired visibility graph. The definition of the persistent property in the initial papers [4, 8] was stated incorrectly and could not guarantee this result. Abello [1] corrected the definition in 2004. Abello et al. [4, 8] claimed that the proposed slope order is realizable by a point set but a complete proof has not been published. We describe their work in more detail in Section 4.2. Following Ghosh’s result [34], Abello and Kumar [7] study visibility graphs of simple polygons, when the Hamiltonian cycle forming the bound- ary of the polygon is given. They define a new class of graphs called quasi- 8 2.3. Adding extra information persistent graphs, which they show is equivalent to the class of graphs sat- isfying the first two necessary conditions of Ghosh [34]. This implies that visibility graphs of simple polygons are all quasi-persistent. They also show that quasi-persistent graphs are closed under ear deletion. An ear is a vertex whose successor and predecessor vertices (with regards to the Hamiltonian cycle) are connected. Using a geometric interpretation of a polygon realizing a quasi-persistent graph, they determine vertices that block the line of sight between pairs that are not mutually visible. This gives a blocking vertex assignment. (Different polygons with the same visibility graph may have different blocking vertex assignments.) They show that a blocking vertex assignment, if determined by a polygon realization, satisfies four necessary conditions. The last three conditions are based on properties of Euclidean shortest paths (as the shortest path between a pair that is not mutually visible is determined by the blocking vertex assignment of the pairs on the path). Ghosh [35] shows all four necessary conditions of Abello and Kumar follow from his third and fourth conditions. Abello and Kumar show that ev- ery quasi-persistent graph has a blocking vertex assignment that satisfies the last three conditions, and suggest that the first condition is what restrains quasi-persistent graphs to be visibility graphs. To address the realizability problem, they introduce an oriented matroid approach: first find the com- binatorial properties on the point set corresponding to the vertices of the visibility graph (that is represented by an oriented matroid or equivalently a simplicial chirotope); then decide whether such a point set is realizable. In particular, they show how to construct a uniform rank 3 oriented ma- troid for every quasi-persistent graph satisfying the four conditions, which if affinely realizable yields a simple polygon with the desired visibility graph. Abello and Kumar [6] show that these conditions are sufficient to recon- struct a polygon from the graph when restricted to 2-spiral polygons. The characterization of visibility graphs of 2-spiral polygons relies on the exis- tence of an ear whose removal leaves a smaller graph in the same class such that any realization of the smaller graph can be extended to a realization of the initial graph. This is not true for k-spiral polygons where k ≥ 3. Thus, in the general case, a reconstruction algorithm needs to take into con- sideration that only some of the realizations of an induced subgraph may be extensible to the realization of the initial graph. This motivates under- standing the realization space of a given visibility graph. It has been shown that there are simple configurations of points with disconnected realization space [16, 40, 54]. O’Rourke and Streinu [51] introduce a new polygon visibility graph, the vertex-edge visibility graph, that represents visibility between vertices and 9 2.3. Adding extra information edges. They suggest that the additional geometric information such graphs provide may simplify the problem of characterizing them. They show that a vertex-edge visibility graph determines the convexity of vertices, the vertex visibility graph, and, for each vertex, the partial local sequence (definition below) and the shortest path tree. Moreover, they show that it contains the same information as an edge visibility graph (which shows edge-to-edge visibility in a polygon), and that an external vertex-edge visibility graph determines the convex hull vertices. The following definitions are useful to understand the following related works. The local sequence for a vertex v is the circular sequence of all other vertices as they are encountered by a rotating line through v. The partial local sequence contains only the visible vertices. The collection of all local sequences is called a cluster of stars, and forms an affine (or acyclic) uniform rank 3 oriented matroid [38, 57], whose topological representation is a generalized configuration of points [38]. Let P be a set of points in the Euclidean plane, and and let L be an arrangement of pseudolines such that every pair of points in P lie on exactly one pseudoline, and each pseudoline in L contains exactly two points of P. Then the pair (P,L) is a generalized configuration of points in general position (“in general position” indicates that no three points of P lie on the same pseudoline of L). A pseudoline is a simple curve that separates the plane. An arrangement of pseudolines is a collection of pseudolines, such that each pair of them meet in exactly one point, where they cross. The set of all local sequences of a generalized configuration of points determines the chirotope information, or equivalently the set of all triple orientations, of the point set. The orientation of a triple (i, j, k) shows whether k is to the right or to the left of the pseudoline through i to j. The same is true when pseudolines are straight-lines. The set of all triple orientations determines the order type. O’Rourke and Streinu [50] generalize the notion of straight-line visibility to visibility along pseudolines. The idea of pseudo-visibility comes from the concept of duality between pseudoline arrangements and generalized con- figurations of points. They give a complete characterization of vertex-edge (pseudo) visibility graphs of pseudo-polygons. They show every vertex-edge pseudo-visibility graph satisfies three properties recognizable in polynomial time. From these properties, they derive a number of additional combina- torial concepts (such as convexity of vertices, partial local sequences and shortest path trees), and use them to define a predicate on any triple of vertices (the predicates match the chirotope definition of Abello and Ku- mar [7]). They show the predicates satisfy Knuth’s CC system axioms [44]. CC systems are equivalent to uniform rank 3 acyclic oriented matroids [44], 10 2.3. Adding extra information which in turn are equivalent to Goodman and Pollack’s generalized config- urations of points in general position [14]. They show that the order of the corresponding generalized configuration of points induces a pseudo-polygon (as the edges do not cross) with the desired vertex-edge pseudo-visibility graph, and conclude that their properties are also sufficient. As a conse- quence of the relationship between vertex-edge visibility graphs and vertex visibility graphs, they show that the recognition problem for vertex visibil- ity graphs of pseudo-polygons is in NP (the same problem with straight-line visibility is only known to be in PSPACE). Streinu [57] concludes the work of O’Rourke and Streinu [50] by provid- ing efficient algorithms for recognizing and drawing clusters of stars, which consequently solves the pseudo-polygon drawing problem. She gives a char- acterization of clusters of stars that are realizable as generalized configu- rations of points. She gives an O(n2) time drawing algorithm that uses an O(n2) space data structure to keep the order type of the generalized configu- ration of points, from which the orientation of each triple can be retrieved in constant time. Her characterization conditions suggest that an orientation (clockwise or counterclockwise) of every triple that is consistent over a set of local sequences (that is, obeys a generalized transitivity law) is realizable as a generalized configuration of points, for some ordering of the point set. Knuth’s CC systems [44] can also be interpreted as characterizing the local sequences of generalized configurations of points. The concept of pseudo-visibility detaches the stretchability question from the combinatorial aspects of the problem. A pseudoline arrangement (or equivalently an affine rank 3 oriented matroid) is stretchable or realizable if it is isomorphic to a line arrangement. The main difficulty in fully charac- terizing vertex-edge visibility graphs of (straight-line) polygons is to decide whether a certain class of affine rank 3 oriented matroids is stretchable. It is well-known that stretchability of pseudoline arrangements, in general, is NP-hard [47, 55]. Mnëv [47] shows determining the stretchability of a pseudoline arrangement is equivalent to the existential theory of the reals (via which one can decide if a graph is a visibility graph [29]). Shor [55] proves the NP-hardness by reducing the monotone 3-SAT problem, a vari- ant of the 3-SAT problem, to the stretchability problem. Using Pappus and Desargues configurations, he constructs a pseudoline arrangement which is stretchable if and only if the given monotone 3-SAT formula is satisfiable. However, there exist various techniques to prove stretchability for particu- lar instances [15–19, 52, 53]. O’Rourke and Streinu [50] suggest that the class of acyclic uniform rank 3 oriented matroids generated by the vertex- edge pseudo-visibility graphs is a strict subclass of all acyclic uniform rank 11 2.3. Adding extra information 3 oriented matroids, so it may be possible to characterize or recognize them (with an algorithm of complexity smaller than PSPACE). Streinu [58] shows that the class of vertex-edge (straight-line) visibility graphs is properly contained in the class of vertex-edge pseudo visibility graphs. She introduces star-like pseudo-polygons and shows that a star- like vertex-edge pseudo-visibility graph may not be realizable. She gives a complete combinatorial characterization for the stretchability problem of this subclass. However, since vertex-edge pseudo-visibility graphs contain more geometric information than pseudo-visibility graphs, it is possible that a pseudo-visibility graph is associated with several (possibly exponentially many) vertex-edge pseudo-visibility graphs, some of which are stretchable and some not [59]. For instance, all star-like pseudo-visibility graphs are re- alizable [58]. Later, Streinu [59] shows an infinite family of pseudo-visibility graphs that are not realizable. She shows that any graph in this class in- duces a unique vertex-edge pseudo-visibility graph all of whose compatible pseudo-polygons are necessarily constructed on top of a generalized configu- ration of points containing a nonstretchable substructure. Since the graphs in this family satisfy the necessary conditions of O’Rourke and Streinu [50], Abello and Kumar [7], and Ghosh [35], this implies that these necessary conditions are not sufficient to characterize (straight-line) visibility graphs. Other combinatorial objects describing the structure of simple polygons (that contain more information than a visibility graph) have been studied by Everett et al. [31]. They introduce stabbing information of a simple polygon, which basically stores certain information about the intersections that each line connecting two vertices makes with the other edges of the polygon. They define three variations of the stabbing information, namely weak, strong, and labelled. They show the strong stabbing information is sufficient to recover the convex hull, the internal and external visibility graphs and to determine the reflex vertices; but is not sufficient to establish the order type of the vertex set. The labelled stabbing information is equivalent to the order type. Horizontal and vertical visibility information in orthogonal polygons (or equivalently, the orthogonal edge visibility graph) has been studied by O’Rourke [48], and Jackson and Wismath [42]. O’Rourke [48] shows that horizontal and vertical (internal) visibility information consists of two dis- joint trees. A tree is realizable if there is an orthogonal polygon that has the tree as one of the two components of its visibility graph. Two trees can mesh if they are jointly realizable by the same polygon. O’Rourke shows that every tree is realizable but not every pair of them are jointly realizable. He characterizes realizable labelled trees and the meshable labellings of tree 12 2.3. Adding extra information pairs. But the characterization in terms of the structure of (unlabelled) tree pairs remains unsolved. The simpler problem of bar visibility graphs has been characterized by Wismath [65], and independently by Tamassia and Tollis [61]. Bar visibility graphs differ from orthogonal polygon visibil- ity trees: the bars do not have to connect into a polygon, and they have two “sides”; This considerably widens the class of bar representable graphs. Later, Jackson and Wismath [42] show how to reconstruct an orthogonal polygon from both the internal and external horizontal and vertical visibil- ity information. They use the horizontal visibility information to determine the convexity of vertices. Using the convexity information and both hori- zontal and vertical visibility information, they compute two partial orders on the x and y dimensions and subsequently assign integer coordinates to the polygon vertices such that the polygon is consistent with the input. 13 Chapter 3 Necessary properties for terrain visibility graphs We first define the graph properties that we use, and then present the set of conditions satisfied by all terrain visibility graphs. 3.1 Graph property definitions We use the following notations for integer intervals: (i..j) = {x ∈ N | i < x < j}, (i..j] = {x ∈ N | i < x ≤ j}, [i..j) = {x ∈ N | i ≤ x < j}, and [i..j] = {x ∈ N | i ≤ x ≤ j}. Definition 1. A graph G = ([n], E) has the X-property if for every four vertices a < b < c < d, if {a, c} ∈ E and {b, d} ∈ E then {a, d} ∈ E. This property is called inversion complete by Abello [1]. Definition 2. A graph G = ([n], E) has the bar-property if for every edge {a, c} ∈ E where a + 1 < c, there exists a vertex b ∈ (a..c) such that {a, b} ∈ E and {b, c} ∈ E. This property is an ordered version of chordality [1, 35]: every ordered cycle of length at least four has a chord. Definition 3. A graph G = ([n], E) that has both the X-property and the bar-property and contains the Hamiltonian path 1, 2, . . . , n is called persis- tent. Abello et al. [4] initially defined persistent graphs in 1995 in a different and slightly incorrect manner so that the X-property was not guaranteed 14 3.2. Necessary conditions (incorrect in the sense that some properties that they assume from their definition are not true). Abello modified the definition in 2004 [1] to include this property (which he called inversion completeness). His subsequent def- inition gives the same class of graphs as our definition does. 3.2 Necessary conditions Now, we present necessary conditions for terrain visibility graphs and prove that terrain visibility graphs are all persistent. Colley [24] shows a strong relationship between terrain visibility graphs and visibility graphs of stair- case polygons. He proves that the core induced subgraph of the visibility graph of a staircase polygon is identical to a terrain visibility graph, and vice versa. (See pages 5–6 of Section 2.2 for more details.) Abello et al. [4] show that the core induced subgraph of the visibility graph of a staircase polygon (and as a result a terrain visibility graph), with respect to its or- dering, is persistent (for their persistent definition). Here, for completeness of results, we re-prove the necessary conditions for terrain visibility graphs by a simpler and more geometric approach. Our proof relies on two lemmas. The first is called the Order Claim in the literature [12, 21, 43], and the second is called the Midpoint Claim by King [43]. Lemma 1. Terrain visibility graphs have the X-property. Proof. Consider four vertices a < b < c < d in a terrain visibility graph G = ([n], E), such that {a, c} ∈ E and {b, d} ∈ E. Since {a, c} ∈ E, we know the terrain does not touch the half-strip above the segment ac. Denote the half-strip above the segment uv by H+(uv). Similarly, we know the terrain does not touch H+(bd). Hence the ray above b crosses the line segment ac and the ray above c crosses the line segment bd, which means the two segments ac and bd intersect in-between. Thus the line segment ad lies in the region H+(ac) ∪H+(bd). Therefore, the terrain does not penentrate H+(ad), which implies {a, d} ∈ E. See Figure 3.1. Lemma 2. Terrain visibility graphs have the bar-property. Proof. Consider a terrain visibility graph G = ([n], E). For any edge {a, c} ∈ E where a+1 < c, the terrain induced on the vertices in [a..c] together with the edge {a, c} create a simple polygon. The fact that every simple polygon admits a triangulation implies the existence of a vertex b ∈ (a..c) such that {a, b} ∈ E and {b, c} ∈ E. See Figure 3.2. 15 3.2. Necessary conditions a b c d Figure 3.1: X-property in terrain visibility graphs. a b c Figure 3.2: Bar-property in terrain visibility graphs. We know terrain visibility graphs contain the Hamiltonian path 1, 2, . . . , n. Moreover, by Lemma 1 and Lemma 2, we have terrain visibility graphs satisfy both the X-property and the bar-property. Thus we conclude the following theorem (which is equivalent to Theorem 3.5 by Abello et al. [4]). Theorem 1. Terrain visibility graphs are persistent. 16 Chapter 4 On the sufficiency of the persistent property Determining whether a graph with certain properties is the visibility graph of of a simple polygon is known as visibility graph realizability or recognition. The actual drawing of the point set whose visibility graph is the desired graph is called visibility graph reconstruction. Even though there have been extensive studies on understanding the combinatorial properties of visibility graphs, the realizability and reconstruction problems appear difficult and the results are very limited (even for special classes of simple polygons). Ideally, we would like to show that the persistent property is sufficient to imply that the graph is a terrain visibility graph, and to be able to recover a terrain from a given persistent graph; but this seems challenging. Abello et al. [4] attempted characterizing the core induced subgraphs of the visibility graphs of staircase polygons, which are exactly the class of terrain visibility graphs. They showed that the visibility information of a given vertex in such structures implies some ordering requirements on the slopes of the lines connecting this vertex to the others in any realization. They showed that there is a global order on all slopes that is consistent with all these local slope orders, for visibility graphs satisfying the persistent property. However, this does not imply that there is a point set that realizes the resulting slope order (that is, the properties are sufficient). The main contribution of our work is to give a much simpler proof that the persistent property guarantees such a global slope ordering. Our proof consequently gives a faster algorithm for constructing this global slope order. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid. Here, we first introduce the terminology that we use for the representa- tion of the slope ordering. We next describe the overall approach of Abello et al. [4] briefly. Then, we give two different much simpler proofs to show that the persistent property guarantees a global slope order. The first proof is a proof by contradiction and is based on the implications of certain slope 17 4.1. Representation of the slope order ordering requirements, which are imposed by the persistent property. The second proof uses a combinatorial result from Felsner and Weil [32]. 4.1 Representation of the slope order We use terminology similar to that used by Abello et al. [4] for the repre- sentation of the slope order of the lines connecting pairs of points. A tableau of size n is a two-dimensional array of n− 1 columns (indexed from 1 to n− 1) where the ath column contains n− a entries (indexed from a + 1 to n), and whose entries are the integers 1, 2, . . . , ( n 2 ) . For a tableau T , we refer to the entry in the ath column and bth row as T [a, b]. Note that a < b. Consider a non-degenerate point set [n]. We may represent the slope ordering of the lines connecting all pairs of the points by a tableau T of size n, such that T [i, j] is the rank of the slope of the line through i and j. (In other words, T [i, j] = s if and only if the rank of the slope of the line through i and j is s.) We know that every three points a < b < c form either a positive orientation (that is, b lies below the segment ac) or a negative orientation (that is, b lies above the segment ac). This implies that, in the tableau T representing the slope ordering, we have either T [a, b] < T [a, c] < T [b, c] or T [a, b] > T [a, c] > T [b, c]. (This establishes Lemma 3.1 of Abello et al. [4].) For three integers a < b < c, we say the triple T [a, b], T [a, c], and T [b, c] is oriented positively if and only if T [a, b] < T [a, c] < T [b, c]. Similarly, the triple is oriented negatively if and only if T [a, b] > T [a, c] > T [b, c]. The triple is balanced if either T [a, b] < T [a, c] < T [b, c], or T [a, b] > T [a, c] > T [b, c]. A balanced tableau is a tableau whose triples are all balanced. The skeleton ST of a tableau T is a two-dimensional array of the same dimensions as T where ST [a, c] = { 1 if c = a+ 1 or T [a, c] > T [a, b] for all b ∈ (a..c), 0 otherwise. Figure 4.1 shows a balanced tableau and its skeleton. An n-triangle is the strict lower triangle of an n× n zero-one matrix. A persistent n-triangle is the n-triangle of the adjacency matrix of a persistent graph. 18 4.1. Representation of the slope order 1 1 2 2 14 3 3 5 4 4 6 8 7 21 5 9 11 10 13 12 6 15 16 17 19 18 20 7 22 23 24 25 26 27 28 8 1 1 2 1 1 3 1 0 1 4 1 0 1 1 5 1 0 1 0 1 6 1 1 1 0 1 1 7 1 1 1 1 1 1 1 8 Figure 4.1: A balanced tableau and its skeleton. A skeleton ST of a balanced tableau T of size n can be interpreted as the n-triangle of an adjacency matrix for an undirected graph with vertices 1, 2, . . . , n and edges {{a, c} | ST [a, c] = 1}. This graph is the skeleton graph of the balanced tableau. Note that the skeleton graph of a balanced tableau representing the slope order of a terrain point set is identical to the terrain visibility graph. (We know ST [a, c] = 1 if and only if c = a+ 1 or the slope rank of line ac is greater than the slope ranks of all lines ab, where b ∈ (a..c). This means that ST [a, c] = 1 if and only if the terrain vertices a and c are adjacent in the terrain, or no terrain vertex in (a..c) lies above the line ac; that is, terrain vertices a and c are mutually visible. See Lemma 3.2 of Abello et al. [4].) A tableau representing the slope order of a simple configuration of points is balanced (See Lemma 3.1 of Abello et al. [4]). This and Theorem 1 imply that the skeleton graph of a balanced tableau representing a terrain is persistent. To characterize terrain visibility graphs, we would like to show that persistent graphs are visibility graphs of terrains. That is equivalent to showing that every persistent graph is the skeleton of a balanced tableau representing the slope order of a terrain point set. We have not proved that but here we show that every persistent graph is the skeleton graph of a balanced tableau representing a slope order. The slope order may or may not be realizable (as a terrain). In other words, we prove the following theorem. (The converse of that is true by Lemma 3.4 of Abello et al. [4].) Theorem 2. If M is a persistent n-triangle, then there exists a balanced tableau whose skeleton is identical to M . We will prove this theorem in Section 4.3. 19 4.2. Abello et al.’s approach 4.2 Abello et al.’s approach Abello et al. [4] prove that a graph is persistent if and only if it is the skeleton graph of a balanced tableau. They argue that a skeleton graph of a balanced tableau is persistent directly by using the definitions. Here we only describe their approach for the reverse direction (that is, every persistent graph is the skeleton graph of a balanced tableau). For a persistent graph G = (V,E), they define an edge e to be reversible if and only if the graph G = (V,E \ e) remains persistent. They use the idea of reversible edges to partially order persistent graphs so that they can generate any of them in a canonical manner. Given a persistent graph of order n, they give an algorithm that starts from a clique of the same or- der and successively removes a reversible edge until the desired persistent graph is generated. They use the basis of this algorithm to reconstruct a balanced tableau from a given persistent graph. Namely, they start from a balanced tableau whose skeleton represents a clique, and perform operations on the tableau entries so that the underlying skeleton becomes incrementally closer to the desired graph. They define flush and augmentation operations, which are compositions of Coxeter type I and type II transformations, on a balanced tableau. Each flipping of a one entry in the skeleton (that is, removing a reversible edge) is done through a sequence of flush and augmen- tation operations on the tableau and is complicated. They establish a loop invariant to show the correctness of their proposed algorithm. However, the loop invariant is not intuitive and requires a complex proof. The overall complexity of their algorithm is O(n5). 4.3 Our main result We reprove that every persistent graph is the skeleton graph of a balanced tableau but in a much simpler way. By the definition of a tableau’s skele- ton, we know that the skeleton entries (whether zero or one) imply certain inequality relations amongst the tableau entires. The following lemma sum- marizes these relations. Lemma 3. For a tableau T and an n-triangle M , ST = M if and only if 1. If M [a, c] = 1, then c = a+ 1 or T [a, c] > T [a, b] for all b ∈ (a..c), and 2. If M [a, c] = 0, then there exists b ∈ (a..c) such that T [a, b] > T [a, c]. Proof. It follows directly from the definition of the skeleton of a tableau. 20 4.3. Our main result Using the combinatorial properties of a persistent graph G, we would like to derive a balanced tableau satisfying the conditions in Lemma 3, where M is the n-triangle of the adjacency matrix of G. We show that the inequality relations required by Lemma 3 and by the balanced property give a par- tial order on the tableau entries; and as a result any tableau that realizes this partial order is balanced, with a skeleton graph identical to the given persistent graph. Our approach is to orient all tableau triples so that they are consistent with Lemma 3. Since our orientation is guaranteed to be balanced, to show the existence of such a balanced tableau, we only need to show that our orientation forms a partial order on the tableau entries. 4.3.1 Orienting the triples We infer combinatorial properties on the structure of a persistent n-triangle, and use these structural properties in determining the orientation of a tableau triple. Definition 4. Let M be an n-triangle. The collection of the entries M [a; [b..c]] ∪ M [[a..b]; c], where a < b < c, is called the abc-hook, and is denoted by hookM (abc). The corner of hookM (abc) is M [a, c]. The column-arm of hookM (abc) is M [a; [b..c]], and the row-arm of hookM (abc) is M [[a..b]; c]. The half-strict abc-rectangle is the submatrix M [[a..b); (b..c]], and is de- noted by rectM (abc). (Figure 4.2 illustrates the abc-hook and the half-strict abc-rectangle.) a b b c rectM (abc) Figure 4.2: The abc-hook (bold outline) and the half-strict abc-rectangle (shaded). 21 4.3. Our main result Note that for every a < b < c < d we have rectM (abc) is contained in rectM (abd) and rectM (bcd) is contained in rectM (acd). We refer to this property as rectangle containment. The following lemma identifies the structure of the abc-hook in a persis- tent n-triangle M . Lemma 4. If M is a persistent n-triangle then each hookM (abc) is of one of the following forms (See Figure 4.3): • The corner is one, or • Either the row-arm or the column-arm consists of all zeros, or • M [a, b] = M [b, c] = 1 and all other entries in hookM (abc) are zeros. 1 0 . . . 0 0 0 ... 0 0 0 ... 0 1 . . . 0 1 Figure 4.3: Possible structures of an abc-hook in a persistent n-triangle. Proof. Suppose to the contrary that there exists an abc-hook that does not have any of the above properties. Thus, we have 1. M [a, c] = 0; 2. there exists i ∈ (a..b] such that M [i, c] = 1; and 3. there exists j ∈ [b..c) such that M [a, j] = 1; such that either i 6= b or j 6= b. But this contradicts M having the X- property on the four points a < i < j < c, which is impossible. 22 4.3. Our main result It is easy to deduce the possible structures of a half-strict abc-rectangle in a persistent n-triangle, from Lemma 4 and the X-property. Figure 4.4 illustrates these possible structures with regards to the associated abc-hook. As shown in the picture, in the four cases above each half-strict abc-rectangle contains a one entry whereas in the four cases below each half-strict abc- rectangle consists of all zero entries. 1 0 1 ? . . . 0 0 0 ... 0 0 1 ? 0 ... 0 0 . . . 0 0 ∃1 0 ... 0 1 . . . 0 1 all 0 0 ... 0 1 . . . 0 0 all 0 0 ... 0 0 . . . 0 1 all 0 0 ... 0 0 . . . 0 0 all 0 Figure 4.4: Possible structures of a half-strict abc-rectangle and its abc-hook in a persistent n-triangle. From the bar-property we conclude the following lemma. Lemma 5. Let M be a persistent n-triangle. For every a < b < c < d in [n], if both rectM (abc) and rectM (bcd) consist of all zero entries then M [[a..b); (c..d]] is a zero matrix. Proof. The k-upper triangle of a matrix is the collection of the entries above the kth diagonal. Suppose to the contrary that M [[a..b); (c..d]] contains a one entry. Let M [a′, c′] be a one entry lying at the kth diagonal in the submatrix M [[a..b); (c..d]] such that the k-upper triangle of the submatrix contains only zero entries. It is easy to see that such an entry exists. We have M [a′, c′] = 1 with a′ < b < c < c′. Since M is persistent, by the bar-property we know there exists b′ ∈ (a′..c′) such that M [a′, b′] = 1 and M [b′, c′] = 1. Since the k-upper triangle in the submatrix M [[a..b); (c..d]] consists of zero entries, we infer b ≤ b′ ≤ c. From knowing that rectM (bcd) consists of all zero entries, we conclude b′ = c. So M [a′, b′] = 1 implies that there is a one entry in M [[a..b); c]. Hence rectM (abc) contains a one entry, which is a contradiction. See Figure 4.5. Let M be a persistent n-triangle. We would like to find a balanced tableau whose skeleton is identical to M (if possible). Given M , we define the orientation function αM from the 3-element subsets of [n] to {+,−} as follows: 23 4.3. Our main result a b c d a b c d 1 a’ c’ (a) We have M [a′, c′] = 1. The bar-property implies that there exists b′ ∈ (a′..c′) such that M [a′, b′] = 1 and M [b′, c′] = 1. Since the grey region consists of zero entries, we conclude b ≤ b′ ≤ c. a b c d a b c d 1 1 1 a’ c’ (b) We have M [b′, c′] = 1. Since rectM (bcd) consists of zero entries, we conclude b′ = c. But this is a contradiction. Figure 4.5: The bar-property implies M [[a..b); (c..d]] is a zero matrix if both rectM (abc) and rectM (bcd) consist of all zero entries, for a persistent M . For every a < b < c in [n], let αM (abc) = { + if rectM (abc) contains a one entry, − if rectM (abc) consists of all zero entries. A tableau T agrees with orientation function αM if for all a < b < c, T [a, b] < T [a, c] < T [b, c] if αM (abc) = +, and T [a, b] > T [a, c] > T [b, c] if αM (abc) = −. Figure 4.6 illustrates the orientation function αM and the inequality rela- tions required in a tableau that agrees with αM . ∃1 + all 0 - Figure 4.6: Orientation function αM and the implied inequality relations. Suppose there exists a tableau T that agrees with αM . The following lemma shows that our orientation captures both the balanced property and the properties required to satisfy ST = M . 24 4.3. Our main result Lemma 6. Let M be a persistent n-triangle. If there is a tableau T whose entries agree with orientation function αM , then 1. T is balanced, and 2. ST = M . Proof. We have each tableau triple oriented either positively or negatively, and hence all triples are balanced. Therefore T is a balanced tableau. As illustrated in Figure 4.7, it is easy to observe that having each tableau triple oriented by αM suffices to have: 1. if M [a, c] = 1, then c = a+ 1 or T [a, c] > T [a, b] for all b ∈ (a..c), and 2. if M [a, c] = 0, then there exists b ∈ (a..c) such that T [a, b] > T [a, c]. (A particular b is b ∈ (a..c) such that M [a, b] = 1 and M [a, x] = 0 for all x ∈ (b..c). Notice that such b always exists because M [i, i+ 1] = 1 for all i ∈ [1..n), by the persistent property.) Thus the triple orientations induce the conditions in Lemma 3, which implies ST = M . 1 ? ? 0 1 ? . . . 0 0 0 ... 0 0 1 ? 0 ... 0 0 . . . 0 0 ∃1 + 0 ... 0 1 . . . 0 1 all 0 0 ... 0 1 . . . 0 0 all 0 0 ... 0 0 . . . 0 1 all 0 0 ... 0 0 . . . 0 0 all 0 - Figure 4.7: The triple orientations agree with the conditions in Lemma 3. Possible triple orientations and their implied inequality relations over a tableau that agrees with the orientation are illustrated with regards to the associated half-strict rectangles. If a tableau T agrees with αM then the entries of T have to obey a set of inequalities (as shown in Figure 4.7). From the above lemma, we conclude that if the set of all these inequalities (which are derived from αM ) gives a partial order on the tableau entries, then any tableau realizing this partial order would be a balanced tableau with skeleton M . In the following, we prove that our orientation gives a partial order. 25 4.3. Our main result 4.3.2 The M-tableau relation digraph DM We introduce a directed graph to represent the required inequality relations between the tableau entries so that the tableau agrees with αM . We show that the resulting digraph is acyclic if M is persistent, which concludes the proof of Theorem 2. The notation ([n] k ) represents the k-element subsets of [n]. Definition 5. Let M be a persistent n-triangle. The M-tableau relation digraph is a directed graph DM = (VM , EM ) such that • VM = {vab | a < b and {a, b} ∈ ( [n] 2 )} (that is, the vertices are the 2-element subsets of [n]—the vertex vab represents the tableau entry in the ath column and the bth row), and • EM = {(vab, vac) and (vac, vbc) | αM (abc) = −} ∪ {(vbc, vac) and (vac, vab) | αM (abc) = +} (that is, the edges represent the inequality relations between the tableau entries that are imposed by the orienta- tion function αM ). In the remaining, we give two different proofs to show that DM is acyclic. Both proofs result from the use of rectangle containment and Lemma 5. The first one is a direct proof by contradiction, in which we show how certain sets of edges imply the existence of other edges in the digraph (which subsequently gives a contradiction in the case of a cycle). The second one relates our work to a combinatorial result from Felsner and Weil [32]. 4.3.3 The digraph DM is acyclic — proof 1 We embed the digraph DM on the n-triangle M such that each vertex vxy is placed at the position of the entry M [x, y] and each edge is a straight line segment. The bth row of the graph is the subgraph induced on the vertices {vxb | x ∈ [1..b)} (that is, the vertices at row b). The ath column of the graph is the subgraph induced on the vertices {vay | y ∈ (a..n]} (that is, the vertices at column a). The following lemma shows that each row or column of the graph is acyclic. Lemma 7. Let DM be an M -tableau relation digraph where M is a persis- tent n-triangle. Each row or column of DM is acyclic. Proof. For an edge e that has both its endpoints in the same row or column, we define e-rectM (e) as follows: For every a < b < c, let e-rectM ((vab, vac)) = 26 4.3. Our main result e-rectM ((vac, vab)) = e-rectM ((vac, vbc)) = e-rectM ((vbc, vac)) = rectM (abc). We say e-rectM (e) is the half-strict rectangle associated with the edge e. Suppose there is a cycle that has all its vertices in the same row. Let eout be the out-going cycle edge incident on the rightmost point of the cycle. From the direction of eout we know e-rectM (eout) contains a one entry. It is easy to see that e-rectM (eout) is covered by the union of all half-strict rectangles associated with cycle edges in the opposite direction relative to eout. These half-strict rectangles contain only zero entries. This contradicts e-rectM (eout) having a one entry. See Figure 4.8. A similar contradiction arises if a cycle occurs in a column (we consider the in-going cycle edge incident on the topmost point in this case). eout Figure 4.8: No cycle lies completely in the same row. Otherwise e-rectM (eout) is contained in the union of the half-strict rectangles associated with edges in the opposite direction relative to eout, which is impossible. Corollary 1 (Transitivity on a row or a column). Let DM = (VM , EM ) be an M -tableau relation digraph where M is a persistent n-triangle. We have: • if (va1b, va2b) and (va2b, va3b) are in EM , then (va1b, va3b) is in EM , and • if (vab1 , vab2) and (vab2 , vab3) are in EM , then (vab1 , vab3) is in EM . Proof. We know that for every a < b < c in [n], we have a directed edge between the pairs {vac, vbc} and {vab, vac} in EM . Thus the corollary is a direct consequence of Lemma 7. The following two lemmas provide the clues to prove that DM is acyclic. 27 4.3. Our main result Lemma 8. Let DM = (VM , EM ) be the M -tableau relation digraph defined on a persistent n-triangle M . For every a < b < c < d in [n] the digraph DM satisfies the four properties below (see Figure 4.9): Property 1: if (vbd, vbc) ∈ EM , then (vad, vac) ∈ EM . Property 2: if (vac, vad) ∈ EM , then (vbc, vbd) ∈ EM . Property 3: if (vad, vac) ∈ EM and (vac, vbc) ∈ EM , then (vbd, vbc) ∈ EM . Property 4: if (vac, vbc) ∈ EM and (vbc, vbd) ∈ EM , then (vac, vad) ∈ EM . Proof. We prove each property as follows: Property 1. If (vbd, vbc) ∈ EM then αM (bcd) = + (by Definition 5). Thus rectM (bcd) contains a one entry. Since rectM (bcd) is contained in rectM (acd), we know rectM (acd) contains a one entry. Therefore αM (acd) = +, which implies (vad, vac) ∈ EM . Property 2. If (vac, vad) ∈ EM then αM (acd) = −. Thus rectM (acd) consists of zero entries. Since rectM (bcd) is contained in rectM (acd), we know rectM (bcd) consists of all zero entries. Hence αM (bcd) = −, which implies (vbc, vbd) ∈ EM . Property 3. If (vad, vac) ∈ EM and (vac, vbc) ∈ EM , then αM (acd) = + and αM (abc) = −. Suppose to the contrary that (vbd, vbc) is not in EM . This implies that αM (bcd) = −. From αM (bcd) = − and αM (acd) = +, we conclude M [[a..b); (c..d]] contains a one entry. Thus we have both rectM (abc) and rectM (bcd) consist of all zero entries whereas M [[a..b); (c..d]] contains a one entry, which is a contradiction to Lemma 5. Property 4. If (vac, vbc) ∈ EM and (vbc, vbd) ∈ EM , then αM (abc) = − and αM (bcd) = −. Thus both rectM (abc) and rectM (bcd) consist of all zero entries. From Lemma 5, we conclude M [[a..b); (c..d]] is a zero matrix. This implies rectM (acd) consists of zero entries. Therefore αM (acd) = − and we have (vac, vad) in EM . 28 4.3. Our main result a b c d a b c d (a) Since rectM (bcd) is con- tained in rectM (acd), we de- duce that if (vbd, vbc) is in EM then (vad, vac) (in red) is in EM . a b c d a b c d (b) Since rectM (bcd) is con- tained in rectM (acd), we de- duce that if (vac, vad) is in EM then (vbc, vbd) (in red) is in EM . a b c d a b c d (c) The red region contains a one entry; otherwise it con- tradicts Lemma 5. This im- plies (vbd, vbc) (in red) is in EM . a b c d a b c d (d) The grey regions consist of all zero entries. Thus Lemma 5 implies (vac, vad) (in red) is in EM . Figure 4.9: The properties of DM . The black edges imply the existence of the red edges. 29 4.3. Our main result Lemma 9. Let DM = (VM , EM ) be an M -tableau relation digraph where M is a persistent n-triangle. Let P be a path va0b0 , va1b1 , . . . , vakbk in DM such that the vertex-induced subgraph of DM on the vertex set {va0b0 , . . . , vakbk} is acyclic. Assume that bm is the greatest element in {b0, b1, . . . , bk}. If bk < b0 then (vakbm , vakbk) is in EM . If b0 < bk then (va0b0 , va0bm) is in EM . (See Figure 4.10.) bm b0 bk a0 ak bm b0 bk ak a0 bm b0 bk a0 = ak (a) If bk < b0, then (vakbm , vakbk ) (in red) is in EM . bm bk b0 ak a0 bm bk b0 a0 ak bm bk b0 a0 = ak (b) If b0 < bk, then (va0b0 , va0bm) (in red) is in EM . Figure 4.10: The black path va0b0 , va1b1 , . . . , vakbk implies the existence of the red edge. Proof. First observe that, for every i such that 0 ≤ i < k, either ai = ai+1 or bi = bi+1. We proceed by induction on the number of edges in P . For succinctness, we occasionally use vi for vaibi . Clearly the statement holds when the length of P equals one. We show that if the statement holds for all paths of length less than k, then the statement holds for all paths of length k. Suppose that bm is greater than both b0 and bk. If bk < b0, let P1 be the path from vm to vk. If b0 < bk, let P1 be the path from v0 to vm. We know P1 is a path of length less than k whose vertex-induced subgraph in DM is acyclic. Thus, by the induction hypothesis, we have P1 implies the existence of the desired edge in EM . See Figure 4.11. 30 4.3. Our main result bm b0 bk ak a0 bm bk b0 a0 ak Figure 4.11: The case when bm is greater than both b0 and bk. The black solid path is P . The black thick path is P1. From the induction hypothesis, we conclude that P1 implies the existence of the red edge. Now suppose that bm = b0. Let P1 be the path from v0 to vk−1. Note that bk−1 ≤ b0. If bk−1 = b0, then the edge (vk−1, vk) is already the desired edge. This is because if bk−1 = b0 then we have bk−1 > bk (by the conditions of the lemma, bk is not b0), and hence ak−1 = ak. Thus (vk−1, vk) = (vakbm , vakbk). So we assume bk−1 < b0. By the induction hypothesis on P1, we infer that (vak−1b0 , vak−1bk−1) is in EM . By Corollary 1 and Lemma 8 (properties 1 and 3), it is easy to observe that this and (vk−1, vk) ∈ EM imply that (vakb0 , vakbk) is in EM . See Figure 4.12(a). Finally assume that bm = bk. The argument is similar to the previous case. Let P1 be the path from v1 to vk. Note that b1 ≤ bk. If b1 = bk then the edge (v0, v1) is already the desired edge. This is because b1 = bk implies b1 > b0 (because bk is not b0 by the conditions of the lemma), and hence a1 = a0. Thus (v0, v1) = (va0b0 , va0bk). So we assume b1 < bk. By the induction hypothesis on P1, we infer that (va1b1 , va1bk) is in EM . By Corollary 1 and Lemma 8 (properties 2 and 4), it is easy to observe that this and (v0, v1) ∈ EM imply that (va0b0 , va0bk) is in EM . See Figure 4.12(b). This concludes the proof. 31 4.3. Our main result bm = b0 bk = bk−1 a0akak−1 bm = b0 bk = bk−1 a0akak−1 bm = b0 bk−1 bk a0ak ak−1 bm = b0 bk bk−1 a0ak ak−1 (a) The case when bm = b0 and bk−1 6= b0. We have ak < ak−1, bk = bk−1 or ak > ak−1, bk = bk−1 or ak = ak−1, bk > bk−1 or ak = ak−1, bk < bk−1 < b0. In the first and second subcases, we use the properties 1 and 3 in Lemma 8, respectively. In the third and fourth subcases we use Corollary 1. bm = bk b0 = b1 aka0 a1 bm = bk b0 = b1 aka0a1 bm = bk b1 b0 aka0 a1 bm = bk b0 b1 aka0 a1 (b) The case when bm = bk and b1 6= bk. We have a0 < a1, b0 = b1 or a0 > a1, b0 = b1 or a0 = a1, b0 > b1 or a0 = a1, b0 < b1 < bk. In the first and second subcases, we use the properties 4 and 2 in Lemma 8, respectively. In the third and fourth subcases we use Corollary 1. Note that the third subcase is impossible since we know the solid blue edge contradicts the existence of the dotted blue edge. Figure 4.12: The cases bm = b0 and bm = bk. The black thick path is P1. The path P is composed of P1 and the blue solid edge. From P1, by the induction hypothesis, we conclude the existence of the dotted blue edge. The blue solid and dotted edges imply the existence of the red edge. 32 4.3. Our main result Lemma 10. Let DM = (VM , EM ) be an M -tableau relation digraph where M is a persistent n-triangle. The digraph DM is acyclic. Proof. Suppose to the contrary that DM is cyclic. Again, for succinctness, we occasionally use vi for vaibi . Let C = va0b0 , va1b1 , . . . , vak−1bk−1 , va0b0 be a shortest cycle in DM . Observe that, for every i such that 0 ≤ i ≤ k − 1, either ai = ai+1 mod k or bi = bi+1 mod k. From Corollary 1, we know that C is composed of edges that alter- nate horizontal and vertical alignment. Assume that (v0, v1) is a top- most edge in C (we have b0 = b1 and no element in {b0, b1, . . . , bk−1} is smaller that b0). Let (vm, vm+1) be a bottommost edge in C (so we have bm = bm+1 and no element in {b0, b1, . . . , bk−1} is greater that bm). By Lemma 7, we know that bm > b0. Now, let P1 = v1, v2, . . . , vm and P2 = vm+1, vm+2, . . . , vk−1, v0. Both P1 and P2 are of length at least one (because (v0, v1) and (vm, vm+1) are in different rows, by Lemma 7). Since the length of the paths P1 and P2 are less than the length of C, we know that their vertex-induced subgraphs in DM are acyclic. Thus, by Lemma 9, we conclude (va1b1 , va1bm) and (va0bm+1 , va0b0) are in EM . Therefore, we have the three edges (va0bm+1 , v0), (v0, v1) and (v1, va1bm) in EM , which contra- dicts Lemma 8. See Figure 4.13. bm = bm+1 b0 = b1 am+1 a1 am a0 Figure 4.13: The contradiction if DM were cyclic. The path P1 (in blue) implies the blue dotted edge. The path P2 (in red) implies the red dotted edge. But the green path is a contradiction. Theorem 2 follows directly from this lemma. The lemma shows that our orientation forms a partial order on the tableau entries. By Lemma 6, we guarantee that if a tableau agrees with our orientation, then it is balanced 33 4.3. Our main result and has the desired skeleton. As a result, any tableau that realizes this partial order would be a balanced tableau with the desired skeleton. 4.3.4 The digraph DM is acyclic — proof 2 Here, we use a result from Felsner and Weil [32] to prove that DM is acyclic. We first describe their terminology and their related result. Definition 6. Let − ≺ +. For an integer r such that 1 ≤ r ≤ n an r- signotope on [n] is a function α from the r-element subsets of [n] to {−,+} such that for every (r + 1)-element subset P of [n] and all i, j, and k such that 1 ≤ i < j < k ≤ r + 1 either α(P bic)  α(P bjc)  α(P bkc) or α(P bic)  α(P bjc)  α(P bkc), where P bxc denotes the set P minus the xth largest element of P . We refer to this property as monotonicity. Felsner and Weil associate an r-signotope α on [n] with a directed graph whose vertices are the (r − 1)-element subsets of [n], and whose edges are →α ≡ {P bic →α P bjc | P ∈ ( [n] r ) , 1 ≤ i < j ≤ r, α(P ) = +} ∪ {P bjc →α P bic | P ∈ ( [n] r ) , 1 ≤ i < j ≤ r, α(P ) = −}. They prove the following lemma. Lemma 11 (Felsner and Weil [32]). For an r-signotope α on [n] the graph with vertices ( [n] r−1 ) and edges →α is acyclic. We show that our orientation function αM is a 3-signotope and hence the associated directed graph, which is identical to the transpose of DM (consisting of the edges of DM with their directions reversed), is acyclic. This implies DM is acyclic. Felsner and Weil give an abstract combinatorial proof that the graphs associated with signotopes are acyclic in general. Lemma 10 may be viewed as an alternative and perhaps more intuitive proof for the acyclicity of such graphs when restricted to 3-signotopes. While the substantial ideas of both proofs are the same, our proof explains in more detail the manner in which sets of edges imply the existence of other edges. In the case of a cycle, this results in a contradiction. We restate Definition 6 for the case r = 3. (See pages 14–15 of Felsner and Weil [32].) 34 4.3. Our main result Definition 7. A 3-signotope on [n] is a function α : ( [n] 3 ) → {−,+} such that for every 4-element subset {a, b, c, d} of [n] with a < b < c < d, the orientation sequence (α(abc), α(abd), α(acd), α(bcd)) is monotone (that is, it has at most one change of sign). In other words, it is one of the eight columns of the table in Figure 4.14. α(abc) + − − − + + + − α(abd) + + − − + + − − α(acd) + + + − + − − − α(bcd) + + + + − − − − Figure 4.14: Monotone orientation sequences. We use this definition in proving the following lemma. Lemma 12. Let M be a persistent n-triangle. The orientation function αM : ( [n] 3 )→ {−,+} where αM (abc) = { + if rectM (abc) contains a one entry − otherwise, is a 3-signotope. Moreover, for every 4-tuple, the resulting orientation se- quence excludes (−,−,−,+) and (+,−,−,−). Proof. We need to show that for any 4-element subset P = {a, b, c, d} of [n] the orientation sequence (αM (abc), αM (abd), αM (acd), αM (bcd)), where a < b < c < d, is monotone. Let P bxc denote the set P minus the xth largest element of P . We say αM (P bic) is at position i of the orientation sequence. We know either αM (bcd) = + or αM (bcd) = −. Consider the following cases. Case 1. αM (bcd) = +: Since αM (bcd) = +, we know there is a one entry in rectM (bcd). As a result rectM (acd) contains a one entry, which implies αM (acd) = +. Thus, we may get a non-monotone orientation sequence only if αM (abd) = − and αM (abc) = +. Assume αM (abd) = −. Hence rectM (abd) consists of all zero entries and so does rectM (abc). Therefore we have αM (abc) = −, which concludes this case. See Figure 4.15. Case 2. αM (bcd) = −: Suppose we have a non-monotone orientation sequence. Thus the sequence contains at least one + sign. We show that the rightmost + sign in the 35 4.3. Our main result a b c d a b c d (a) From αM (bcd) = +, we know rectM (bcd) (in green) contains a one entry. a b c d a b c d (b) Since rectM (bcd) (in green) is contained in rectM (acd) (in blue), we know αM (bcd) = + im- plies αM (acd) = +. a b c d a b c d (c) From αM (abd) = −, we know rectM (abd) (in red) consists of all zero entries. a b c d a b c d (d) Since rectM (abc) (in yellow) is contained in rectM (abd) (in red), we know αM (abd) = − im- plies αM (abc) = −. Figure 4.15: Case 1: αM (bcd) = +. orientation sequence propagates all the way to the left, which implies that the sequence is monotone. Note that if αM (abd) = − then αM (abc) = −. This is because from rectM (abd) containing only zero entries, we conclude that rectM (abc) consists of all zero entries. Therefore, the rightmost + sign is either at position 2 or at position 3. We consider each case below. Case 2.1. αM (abd) = + and αM (acd) = −: We have rectM (abd) contains a one entry whereas rectM (acd) consists of all zero entries. This implies that rectM (abc) contains a one entry. Thus αM (abc) = +, which concludes this case. See Figure 4.16. 36 4.3. Our main result a b c d a b c d (a) From αM (abd) = + and αM (acd) = −, we know rectM (abd) (in red) contains a one entry whereas rectM (acd) (in blue) consists of all zero entries. a b c d a b c d (b) We conclude rectM (abc) (in yellow) contains a one entry, and hence αM (abc) = +. Figure 4.16: Case 2.1: αM (bcd) = −, αM (acd) = −, and αM (abd) = +. Case 2.2. αM (acd) = +: We know rectM (acd) contains a one entry but rectM (bcd) consists of all zero entries. This implies that there is a one entry in the submatrixM [[a..b); (c..d]]. Since M [[a..b); (c..d]] contains a one entry and rectM (bcd) consists of zero entries, by Lemma 5, we conclude that rectM (abc) contains a one entry. We know rectM (abd) covers rectM (abc) and hence it contains a one entry. Thus αM (abc) = + and αM (abd) = +, which conclude this case. See Figure 4.17. Therefore, αM gives a monotone orientation sequence for each 4-tuple, and hence is a 3-signotope. Moreover, by the argument above, it is easy to see that it never gives the monotone sequence (−,−,−,+) or (+,−,−,−), and thus it is a restricted subclass of 3-signotopes. This lemma together with Lemma 11 imply Lemma 10, which conse- quently concludes the proof of Theorem 2. A 3-signotope is realizable as an ordered generalized configuration of points (by Theorem 7 of Felsner and Weil [32] and the concept of duality between pseudoline arrangements and generalized configurations of points). However, not all 3-signotopes are realizable as ordered point sets. Our ori- entation is a strict subclass of 3-signotopes. It excludes the monotone orien- tation sequences (−,−,−,+) and (+,−,−,−), which puts more constraints on the point set realizing it (that is, it forbids certain substructures in the realization). This may help prove realizability of this subclass. 37 4.3. Our main result a b c d a b c d (a) From αM (acd) = + and αM (bcd) = −, we know rectM (acd) (in blue) contains a one entry whereas rectM (bcd) (in green) consists of all zero en- tries. Since rectM (bcd) (in green) is contained in rectM (acd) (in blue), we conclude M [[a..b); (c..d]] (dashed outline) contains a one entry. a b c d a b c d (b) The bar-property implies that if M [[a..b); (c..d]] (in grey) contains a one entry and rectM (bcd) (in green) consists of all zero entries, then rectM (abc) (in yellow) con- tains a one entry. a b c d a b c d (c) Since rectM (abc) (in yellow) is contained in rectM (abd) (in red), we know αM (abc) = + implies αM (abd) = +. Figure 4.17: Case 2.2: αM (bcd) = − and αM (acd) = +. 38 Chapter 5 Concluding remarks Our approach may be interpreted in the context of oriented matroids. The same context has been used by Abello and Kumar [5] and later by O’Rourke and Streinu [50] in addressing visibility graphs of pseudo simple polygons. Both these results require more geometric information than the mere vertex visibility graphs in order to establish the triple orientations. In fact, they use additional combinatorial concepts to impute unique blocking vertices (articulation points in the terminology of O’Rourke and Streinu) to pairs of vertices that are not mutually visible, and consequently to determine a unique shortest path between two distinct vertices. The orientation of a triple is then based on whether all three vertices lie on the same shortest path or not. In our work, we restrict ourselves to terrain visibility graphs. We determine a triple orientation based on whether the associated half- strict rectangle contains a one entry or not. Our orientation simplifies the orientation defined by Abello and Kumar [7] and O’Rourke and Streinu [50], since it is established solely from the vertex visibility graph. For terrains, a shortest ordered path in the visibility graph determines the Euclidean shortest path in any realization of the graph. The term shortest path, in what follows, refers to the shortest ordered path in the visibility graph. It is easy to see that, for a < b < c, if the half-strict abc-rectangle contains a one entry, then b is not on any shortest path containing both a and c. This is because a one entry in the half-strict abc-rectangle indicates the existence of an edge {u, v} that passes over b (where a ≤ u < b < v ≤ c). Let {u, v} be the longest such edge. If b lies on a shortest path from a to c then {u, v} is not {a, c}. Also, the shortest path must cross {u, v}, but then the X-property contradicts {u, v} being the longest such edge. Similarly, if the half-strict abc-rectangle does not contain a one entry, then all shortest paths containing a and c, contain b as well. This implies that our orientation happens to be the same as the orientation defined in the previous results. However, we use specific graph theoretic properties of terrain visibility graphs, and consequently we show more about the structure of the underlying oriented matroid, which may help to prove realizability. Since oriented matroids are closely related to Knuth’s axioms [44] on 39 Chapter 5. Concluding remarks three-point orientation predicates, we give a succinct description of these axioms and the relevant results here. Later we use Knuth’s terminology, which may help us better distinguish between the results from Abello and Kumar [7], O’Rourke and Streinu [50], and our work. The following axioms hold for counterclockwise relations between sets of up to five points in the Euclidean plane. (The primitive predicate pqr states that the circle through points (p, q, r) is traversed counterclockwise when we encounter the points in cyclic order p, q, r, p.): Axiom 1 (cyclic symmetry) pqr =⇒ qrp. Axiom 2 (antisymmetry) pqr =⇒ ¬prq. Axiom 3 (nondegeneracy) pqr ∨ prq. Axiom 4 (interiority) tqr ∧ ptr ∧ pqt =⇒ pqr. Axiom 5 (transitivity) tsp ∧ tsq ∧ tsr ∧ tpq ∧ tqr =⇒ tpr. The ternary relations that satisfy Axioms 1−5 are called CC systems (short for “counterclockwise systems”). The ternary relations that satisfy Axioms 1 − 3 and Axiom 5 are pre-CC systems. Uniform oriented matroids cor- respond to Axiom 5. Axiom 4 is equivalent to a special class of uniform oriented matroids, called acyclic. In fact, Axiom 5 captures almost all the important properties of Axiom 4, and thus pre-CC systems are not much different from full CC systems. More precisely, a set of triples is a pre-CC system if and only if it can be obtained from a CC system by negating a subset of its points where negating a point complements the value of all triples that contain that point. Abello and Kumar [7] show that their orientation forms a simplicial chi- rotope of rank 3, which equivalently represents a uniform rank 3 oriented matroid. It has been shown that simplicial rank 3 chirotopes are equiva- lent to Knuth’s pre-CC systems [11, 44]. Abello and Kumar show that if the resulting chirotope is realizable then their necessary conditions would characterize visibility graphs of simple polygons (when the additional infor- mation of the blocking vertex assignment is given). However, since some pre-CC systems that satisfy their conditions are not realizable (that is, they do not arise from actual points in the plane), such conditions fail to charac- terize visibility graphs of straight-line simple polygons. O’Rourke and Streinu [50] show that their orientation forms a CC sys- tem. CC systems are equivalent to uniform acyclic rank 3 oriented ma- troids (or identically affine rank 3 simplicial chirotopes). Uniform acyclic 40 Chapter 5. Concluding remarks rank 3 oriented matroids are in turn equivalent to arrangements of pseu- dolines, by the Folkman-Lawrence representability theorem [33]. Shor [55] and Mnëv [47] show that not all arrangements of pseudolines are stretch- able. In fact, Goodman and Pollack [39] show that almost all CC systems on n points are unrealizable, in the limit as n→∞. Even though O’Rourke and Streinu [50] suggest that their orientation forms a strict subclass of all CC systems, Streinu [58, 59] proves that their characterization (of a variant of pseudo visibility graphs containing more information than vertex pseudo visibility graphs) allows graphs that are not visibility graphs of straight-line polygons. We study terrain visibility graphs, which induce stronger conditions. Namely, we know that terrain visibility graphs satisfy the X-property in addition to the properties of simple pseudo-polygon visibility graphs. Using the specific graph properties of terrain visibility graphs, we prove stronger results: our orientation is a strict subclass of 3-signotopes. By case analysis, it is easy to see that every 3-signotope is a CC system (and consequently a pre-CC system). However, we may have CC systems that are not 3- signotopes. For instance, let f be a cyclic symmetric and antisymmetric ternary relation on the set {a, b, c, d, e} such that f(abc) = −, f(abd) = +, f(abe) = −, f(acd) = −, f(ace) = −, f(ade) = +, f(bcd) = −, f(bce) = −, f(bde) = +, and f(cde) = +, where a < b < c < d < e. Then f satisfies all the five axioms of CC systems, but does not satisfy the monotonicity property on the 4-tuples (a, b, c, d) and (a, b, d, e), and hence is not a 3- signotope. Figure 5.1 illustrates the relation between pre-CC systems, CC systems, and 3-signotopes. pre-CC systems CC Systems 3-signotopes Figure 5.1: The relation between pre-CC systems, CC systems, and 3- signotopes. 41 Chapter 5. Concluding remarks Knuth’s CC systems may be interpreted as characterizing the local se- quences of generalized configurations of points. Likewise, Streinu [57] gives the necessary and sufficient properties of local sequences that arise from generalized configurations of points (where the resulting allowable sequence2 may not include the identity permutation). These properties suggest that an orientation (clockwise or counterclockwise) of every triple that obeys a “generalized transitivity” law, is realizable as a generalized configuration of points for some ordering of the point set (or equivalently, it forms a uniform rank 3 acyclic oriented matroid). In this work, we study ordered graphs (that is, a graph with a total order over its vertices). We orient all triples such that they are balanced, and prove that our orientation obeys the transitivity law; and hence forms a partial order on the slope order requirements3. Fel- sner and Weil [32] show that the transitivity of the balanced orientations in an ordered set is identical to the monotonicity of all the 4-tuples (or in other words, to the orientation function being a 3-signotope). This suggests that our first proof for the acyclicity of the M-tableau relation digraph implies that our orientation function is a 3-signotope. We prove this fact directly in the second proof. Abello et al. [4] show that persistent graphs, if representing visibility, guarantee a slope order on the lines connecting all pairs of terrain vertices (in a possible realization) that is consistent with the desired visibility graph, through an algorithmic approach of time complexity O(n5). In our work, not only do we prove this (by showing the acyclicity of the M-tableau relation digraph), but we also establish an orientation for all triples which gives a certain 3-signotope. Our proof techniques are much simpler, and clarify the implications of the X-property and the bar-property on the ordering of the slopes. Lastly, we may orient all triples in O(n3) time, which consequently gives an O(n3) time algorithm for constructing a slope ordering. The al- gorithm is as follows: (Remember that the orientation of a triple may be equivalently determined based on whether all three vertices lie on the same 2 Suppose P is the set of numbered points {p1, . . . , pn} in the Euclidean plane. Let L be a directed line not orthogonal to any line determined by two members of P, and project P orthogonally onto L. The projected points define a permutation of the indices 1, . . . , n. If L rotates counterclockwise, the permutation changes whenever L passes through a direction perpendicular to a line connecting two points of P. (When L has turned through an angle pi the resulting permutation of the indices will be the reverse of the initial permutation.) Such a periodic sequence of permutations is called an allowable sequence. 3The concept of the slope order may also be generalized to pseudolines. If a pseudoline arrangement is intersected with a vertical line such that all vertices of the arrangement lie to its right, then the order in which the pseudolines cross the vertical line (decreasing by the y-coordinates of the crossings) is the (increasing) slope order of the pseudolines [60]. 42 Chapter 5. Concluding remarks shortest ordered path in the visibility graph or not.) First, we initialize all triple orientations negatively. Given a persistent graph G = ([n], E), for ev- ery vertex i, we run BFS on the induced subgraph of G containing vertices [i..n] such that the neighbours of vertices are visited in order. This way we obtain the ordered shortest path trees from the visibility graph. At the same time that we execute the BFS procedures, we positively orient the triples that occur on the same path in the BFS trees. Therefore we determine our triple orientation (that is, the function αM ) in O(n 3) time in total. From the triple orientation αM , we construct the digraph DM (by Definition 5). The digraph has O(n2) vertices and O(n3) edges (which represent the in- equality relations imposed by the orientation). We do a topological sort on the digraph in O(n3) time. As a result, we give an O(n3) time algorithm for constructing a slope ordering. Finally, we would like to mention that the partial order resulting from our orientation may not encode all possible slope orderings. This is because we orient all triples, which may put more constraints on the tableau entries than are required in order to guarantee a balanced tableau with the desired skeleton. In general, a triple orientation of the point set realizing an induced subgraph may not be extensible to a triple orientation of the point set real- izing the entire graph. For instance, in Figure 5.2, the induced subgraph on the vertex set {1, 2, 3, 4} admits either orientation for the points 1, 3, 4 for a realization. But the triple needs to be oriented positively in any realization of the entire graph. It is easy to see that the additional constraints that our 2 3 4 5 1 2 3 4 1 0 1 0 1 1 1 1 0 1 Figure 5.2: A triple orientation of a smaller graph may not be extensible to a triple orientation of a larger one: the smaller tableau admits either orien- tation for the points 1, 3, 4 while the points need to be oriented positively in the larger tableau. orientation defines make the triple orientation of smaller subgraphs extensi- ble to the triple orientation of the entire graph. This suggests that, using our orientation, it may be possible to reconstruct the terrain by incrementally 43 Chapter 5. Concluding remarks realizing the point set. In addition, our orientation forbids certain substruc- tures in any realization (as it excludes (−,−,−,+) and (+,−,−,−) from the possible orientation sequences on the 4-tuples). This puts more con- straints on the point set realizing it, which may help to prove realizability and perhaps to reconstruct the terrain. 44 Bibliography [1] J. Abello. The majority rule and combinatorial geometry (via the sym- metric group). Annales Du Lamsade, 3:1–13, October 2004. [2] J. Abello and Ö. Egecioglu. Visibility graphs of staircase polygons with uniform step length. International Journal of Computational Geometry and Applications, 3(1):27–37, 1993. [3] J. Abello, Ö. Egecioglu, and K. Kumar. Visibility graphs of staircase polygons and the weak Bruhat order II: From maximal chains to poly- gons. preprint. [4] J. Abello, Ö. Egecioglu, and K. Kumar. Visibility graphs of stair- case polygons and the weak Bruhat order I: From visibility graphs to maximal chains. Discrete and Computational Geometry, 14(3):331–358, 1995. [5] J. Abello and K. Kumar. Visibility graphs and oriented matroids (ex- tended abstract). In R. Tamassia and I. Tollis, editors, Graph Draw- ing, volume 894 of Lecture Notes in Computer Science, pages 147–158. Springer Berlin / Heidelberg, 1995. [6] J. Abello and K. Kumar. Visibility graphs of 2-spiral polygons (ex- tended abstract). In Proceedings of the Second Latin American Sympo- sium on Theoretical Informatics, LATIN ’95, pages 1–15, London, UK, 1995. Springer-Verlag. [7] J. Abello and K. Kumar. Visibility graphs and oriented matroids. Dis- crete and Computational Geometry, 28:449–465, 2002. 10.1007/s00454- 002-2881-6. [8] J. Abello, K. Kumar, and Ö. Egecioglu. A combinatorial view of vis- ibility graphs of simple polygons. In Proceedings of the Fifth Inter- national Conference on Computing and Information, ICCI ’93, pages 87–92, Washington, DC, USA, 1993. IEEE Computer Society. 45 Bibliography [9] J. Abello, H. Lin, and S. Pisupati. On visibility graphs of simple poly- gons. Congressus Numerantium, 90:119–128, 1992. [10] T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai. Visibility of disjoint polygons. Algorithmica, 1:49–63, January 1986. [11] P. Baier. NP-completeness of partial chirotope extendibil- ity. ArXiv Mathematics e-prints, math/0504430, April 2005. arXiv:math/0504430v1 [math.CO]. [12] B. Ben-Moshe, M. Katz, and J. Mitchell. A constant-factor approxi- mation algorithm for optimal terrain guarding. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’05, pages 515–524, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. [13] C. Berge. Some classes of perfect graphs. In Six Papers in Graph Theory, pages 1–21, Indian Statistical Institute, Calcutta, 1963. [14] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler. Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993. [15] J. Bokowski, J. Richter, and B. Sturmfels. Nonrealizability proofs in computational geometry. Discrete and Computational Geometry, 5:333– 350, 1990. 10.1007/BF02187794. [16] J. Bokowski and B. Sturmfels. On the coordinatization of oriented matroids. Discrete and Computational Geometry, 1:293–306, 1986. 10.1007/BF02187702. [17] J. Bokowski and B. Sturmfels. Algebraic criteria for geometric realiz- ability. In Computational Synthetic Geometry, volume 1355 of Lecture Notes in Mathematics, pages 61–86. Springer Berlin / Heidelberg, 1989. 10.1007/BFb0089257. [18] J. Bokowski and B. Sturmfels. Computational synthetic geometry. Springer-Verlag, Berlin and New York, 1989. [19] J. Bokowski and B. Sturmfels. An infinite family of minor-minimal non- realizable 3-chirotopes. Mathematische Zeitschrift, 200:583–589, 1989. 10.1007/BF01160956. 46 Bibliography [20] B. Chazelle. Triangulating a simple polygon in linear time. Discrete and Computational Geometry, 6:485–524, 1991. [21] D. Z. Chen, V. Estivill-Castro, and J. Urrutia. Optimal guarding of polygons and monotone chains. In Proceedings of the Seventh Canadian Conference on Computational Geometry, pages 133–138, 1995. [22] Seung-Hak Choi, Sung Yong Shin, and Kyung-Yong Chwa. Character- izing and recognizing the visibility graph of a funnel-shaped polygon. Algorithmica, 14:27–51, 1995. [23] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of Mathematics, 164(1):51–229, 2006. [24] P. Colley. Visibility graphs of uni-monotone polygons. Master’s thesis, Department of Computer Science, University of Waterloo, Waterloo, Canada, 1991. [25] P. Colley. Recognizing visibility graphs of unimonotone polygons. In Proceedings of the Fourth Canadian Conference on Computational Ge- ometry, pages 29–34, 1992. [26] P. Colley, A. Lubiw, and J. Spinrad. Visibility graphs of towers. Com- putational Geometry: Theory and Applications, 7:161–172, February 1997. [27] C. Coullard and A. Lubiw. Distance visibility graphs. In Proceedings of the seventh annual symposium on Computational geometry, SCG ’91, pages 289–296, New York, NY, USA, 1991. ACM. [28] H. ElGindy. Hierarchical decomposition of polygons with applications. PhD thesis, School of Computer Science, McGill University, Montreal, Canada, 1985. [29] H. Everett. Visibility graph recognition. PhD thesis, Department of Computer Science, University of Toronto, Toronto, Canada, 1990. [30] H Everett and D.G Corneil. Recognizing visibility graphs of spiral polygons. Journal of Algorithms, 11(1):1 – 26, 1990. [31] H. Everett, F. Hurtado, and M. Noy. Stabbing information of a simple polygon. In Proceedings of the Eight Canadian Conference on Compu- tational Geometry, pages 74–79, 1996. 47 Bibliography [32] S. Felsner and H. Weil. Sweeps, arrangements and signotopes. Discrete Applied Mathematics, 109:67–94, 2001. [33] J. Folkman and J. Lawrence. Oriented matroids. Journal of Combina- torial Theory, Series B, 25(2):199 – 236, 1978. [34] S. K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. In R. Karlsson and A. Lingas, editors, SWAT 88, vol- ume 318 of Lecture Notes in Computer Science, pages 96–104. Springer Berlin / Heidelberg, 1988. [35] S. K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. Discrete and Computational Geometry, 17(2):143– 162, 1997. [36] S. K. Ghosh. Visibility Algorithms in the Plane. Cambridge University Press, New York, NY, USA, 2007. [37] S. K. Ghosh and P. P. Goswami. Unsolved problems in visibility graphs of points, segments and polygons. CoRR, abs/1012.5187, 2010. [38] J. E. Goodman and R. Pollack. Semispaces of configurations, cell com- plexes of arrangements. Journal of Combinatorial Theory, Series A, 37(3):257 – 293, 1984. [39] J. E. Goodman and R. Pollack. Upper bounds for configurations and polytopes in Rd. Discrete and Computational Geometry, 1:219–227, 1986. 10.1007/BF02187696. [40] J. E. Goodman and R. Pollack. Allowable sequences and order types in discrete and computational geometry. In J. Pach, editor, New Trends in Discrete and Computational Geometry, volume 10 of Algorithms and Combinatorics, pages 103–134. Springer-Verlag, Berlin, 1993. [41] J. Hershberger. Finding the visibility graph of a simple polygon in time proportional to its size. In Proceedings of the third annual symposium on Computational geometry, SCG ’87, pages 11–20, New York, NY, USA, 1987. ACM. [42] L. Jackson and S. K. Wismath. Orthogonal polygon reconstruction from stabbing information. Computational Geometry: Theory and Ap- plications, 23:69–83, July 2002. 48 Bibliography [43] J. A. King. Approximation algorithms for guarding 1.5 dimensional terrains. Master’s thesis, Department of Computer Science, The Uni- versity of British Columbia, Vancouver, Canada, 2005. [44] D. E. Knuth. Axioms and hulls, volume 606 of Lecture Notes in Com- puter Science. Springer-Verlag, Berlin, 1992. [45] Y. Lin and S. Skiena. Complexity aspects of visibility graphs. Interna- tional Journal of Computational Geometry and Applications, 5(3):289– 312, 1995. [46] T. Lozano-Pérez and M. A. Wesley. An algorithm for planning collision- free paths among polyhedral obstacles. Commun. ACM, 22:560–570, October 1979. [47] N. E. Mnëv. The universality theorem on the oriented matroid strat- ification of the space of real matrices. In J. E. Goodman, R. Pollack, and W. Steiger, editors, Discrete and Computational Geometry: Papers from the DIMACS Special Year, volume 6 of DIMACS series in Dis- crete Mathematics and Theoretical Computer Science, pages 237–243. AMS/ACM, 1991. [48] J. O’Rourke. Art gallery theorems and algorithms, chapter 7. Oxford University Press, Inc., New York, NY, USA, 1987. [49] J. O’Rourke. Computational geometry column 18. SIGACT News, 24:20–25, January 1993. [50] J. O’Rourke and I. Streinu. Vertex-edge pseudo-visibility graphs: char- acterization and recognition. In Proceedings of the thirteenth annual symposium on Computational geometry, SCG ’97, pages 119–128, New York, NY, USA, 1997. ACM. [51] J. O’Rourke and I. Streinu. The vertex-edge visibility graph of a poly- gon. Computational Geometry: Theory and Applications, 10:105–120, May 1998. [52] J. Richter-Gebert. On the realizability problem of combinatorial geome- tries decision methods. PhD thesis, Technische Hochschule Darmstadt, 1992. [53] J. Richter-Gebert. Euclideaness and final polynomials in oriented ma- troid theory. Combinatorica, 13:259–268, 1993. 10.1007/BF01202352. 49 Bibliography [54] J. Richter-Gebert and G. M. Ziegler. Oriented matroids. In J. E. Good- man and J. O’rourke, editors, Handbook of Discrete and Computational Geometry, chapter 6, pages 129–151. CRC Press, Boca Raton, second edition, 2004. [55] P. W. Shor. Stretchability of pseudolines is NP-hard. In P. Gritzmann and B. Sturmfels, editors, Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of DIMACS series in Discrete Mathematics and Theoretical Computer Science, pages 531–554. AMS press, 1991. [56] G. Srinivasaraghavan and A. Mukhopadhyay. A new necessary condi- tion for the vertex visibility graphs of simple polygons. Discrete and Computational Geometry, 12:65–82, 1994. 10.1007/BF02574366. [57] I. Streinu. Clusters of stars. In Proceedings of the thirteenth annual symposium on Computational geometry, SCG ’97, pages 439–441, New York, NY, USA, 1997. ACM. [58] I. Streinu. Stretchability of star-like pseudo-visibility graphs. In Pro- ceedings of the fifteenth annual symposium on Computational geometry, SCG ’99, pages 274–280, New York, NY, USA, 1999. ACM. [59] I. Streinu. Non-stretchable pseudo-visibility graphs. Computational Geometry: Theory and Applications, 31:195–206, June 2005. [60] I. Streinu, K. Bezdek, J. Pach, T. Dey, J. Chen, D. Kravets, N. Am- ato, and W. R. Franklin. Discrete and computational geometry. In K. H. Rosen, J. G. Michaels, J. L. Gross J. W. Grossman, and D. R. Shier, editors, Handbook of Discrete and Combinatorial Mathematics, chapter 13. CRC Press, 1999. [61] R. Tamassia and I. Tollis. A unified approach to visibility representa- tions of planar graphs. Discrete and Computational Geometry, 1:321– 341, 1986. 10.1007/BF02187705. [62] R. E. Tarjan and C. J. Van Wyk. An O(n log logn)-time algorithm for triangulating a simple polygon. SIAM Journal on Computing, 17:143– 178, February 1988. [63] N. Vijay. On testing the necessary conditions for visibility graphs of simple polygons. Research report, 1998. 50 Bibliography [64] E. Welzl. Constructing the visibility graph for n-line segments in O(n2) time. Information Processing Letters, 20(4):167 – 171, 1985. [65] S. K. Wismath. Characterizing bar line-of-sight graphs. In Proceedings of the first annual symposium on Computational geometry, SCG ’85, pages 147–152, New York, NY, USA, 1985. ACM. 51