Graph-Theore t ic and Geomet r ic A l g o r i t h m s Assoc ia ted w i t h M o m e n t - B a s e d Po lygon Recons t ruc t ion by Stephane Durocher B .Sc . (Computer Science with Mathemat ics Major ) Universi ty of Toronto, 1997 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Maste r of Science in T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Department of Computer Science) we accept this thesis as conforming to the required standard The UnrV^rsi ty of B r i t i s h C o l u m b i a August 1999 © Stephane Durocher, 1999 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, 1 agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Co/y\ pcjVgJV" Sx^ e./\if>^ The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Abstract 0 The problem of reconstructing an unknown polygonal shape P, viewed as a region in the complex plane, from a finite number of its complex moments is motivated by a number of mathematical , computat ional , and application-oriented considerations. Complex moment information can be derived from such diverse physical processes as tomographic (line integral) measurement, exterior gravitat ional , or magnetic field measurement, or thermal radiation measurement, associated wi th an otherwise un-specified object [ G M V 9 9 , M V K W 9 5 , SB86]. Mi lanfar et al. [ M V K W 9 5 ] , building on earlier work of Davis [Dav64, Dav77], show how a finite number of complex mo-ments of P can be effectively used to reconstruct the vertices of P. If sufficient addit ional information (for example, convexity or rectilinearity) about P is known, P itself can be reconstructed. Very recently, Golub et al. [ G M V 9 9 ] address some of the formidable numerical difficulties associated with this reconstruction. In ad-di t ion, they demonstrate that part ia l information concerning a polygon's edges can also be derived from a finite number of its complex moments, raising the possibility of a more complete and general reconstruction scheme. In general, note that even simply-connected polygonal regions are not uniquely specified by even infinitely many of their complex moments [SB86], thereby precluding a completely general reconstruction scheme. Given vertex positions for the set V of vertices of P in the Cartesian plane and partial information (expressed in terms of geometric constraints) about the edges bounding P, we examine the problem of constructing polygonal regions con-ii sistent wi th this information. Al though in practice, the vertex positions and edge constraints may contain error in their specifications (due either to error originating in the data or introduced in the numerical computations) it is of interest to study the reconstruction problem with error-free moment information. A s we shall see, this translates to a constrained directed 2-factor problem in a directed graph G defined on the vertex set V. A s observed in [ G M V 9 9 ] , the potential edges incident on a vertex are subject to very specific local restrictions. These restrictions have the following simple geo-metric interpretation. Each vertex has two independent axes assigned to it: a blue and a red axis. Each axis specifies two in-directions and two out-directions such that in-directions and out-directions are orthogonal. A n edge joining vertex u to vertex v belongs to the edge set of G if and only if its direction agrees with one of the axes specified at each of u and v. We wil l colour the head and ta i l of each such edge with the colour of its associated axis. A solution to the polygon reconstruction problem is a spanning subgraph H of the resulting directed and edge-bicoloured graph in which every vertex has both in-degree and out-degree one and both red-degree and blue-degree one. Thus, we are looking for a directed 2-factor of G that satisfies some local colour constraints. This thesis addresses graph-theoretic and geometric concerns arising from moment-based polygon reconstruction. We show NP-hardness of various restrictions to the 2-factor problem. We investigate properties of moment sets whose graphs contain non-unique solutions. We develop algorithms to solve the problem of polygon recon-struction given both perfect and imperfect input moment data. Final ly , we examine the success of reconstruction on various classes of graphs. 111 Contents Abstract ii Contents iv List of Figures v i i Acknowledgements x i Dedication xi i 1 Introduction 1 1.1 Problem and Mot iva t ion 1 1.2 Previous Work 1 1.3 Thesis Organizat ion 4 2 Prob lem Definition 6 2.1 Definition of Terms 6 2.1.1 General Graph Theory 6 2.1.2 Classical Complexi ty 8 2.1.3 G r a p h Theoretic and Complexi ty Problems 9 2.1.4 Polygon Reconstruction Problem 11 2.2 Models Used and Problem Overview 12 iv 3 Restricted 2-Factors 18 3.1 2-Factors 19 3.2 Restr ic t ing the 2-Factor Problem 21 3.3 Edge-Bicoloured Directed 2-Factor 22 3.3.1 Problem Instance and Question 22 3.3.2 E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R is N P - h a r d 23 3.3.3 Bounded-Degree Edge-Bicoloured Directed 2-Factor 26 3.3.4 Degree Four versus Degree F ive 29 3.4 Non-Crossing 2-Factor 30 3.4.1 Problem Instance and Question 30 3.4.2 N O N - C R O S S I N G 2 - F A C T O R is N P - h a r d 31 3.5 Summary 37 4 Uniqueness of Moment Sets 38 4.1 Commitment Propagat ion 38 4.2 Non-Unique Solutions 40 4.3 Summary 47 5 Reconstruction Algor i thm 48 5.1 Reconstruction Process Overview 48 5.2 B u i l d G r a p h : Bui ld ing the Initial Graph 50 5.3 EdgeE l im: Simplifying the Graph 52 5.4 C o m m i t : Colour Constraint Propagat ion 55 5.5 TreeSearch: Recursive Search Trees 62 5.6 FragmentSearch: F ind ing Fragments of Solutions 67 5.7 MomentDiff : Component Reconstruction by Difference of Moments . 70 5.8 Summary 73 6 F r o m Models to Real Data 74 6.1 Vary ing Cont ro l of the Input D a t a 74 v 6.2 Examin ing the Behaviour of Various Graphs • • • 75 6.3 Deal ing wi th Numerica l E r ro r in the Reconstruction 78 6.4 Summary 80 7 Further Research 81 7.1 Variable Internal Density 82 7.2 Cert i fying Solutions 83 7.3 Iterative Reconstruction 84 7.4 Improving Er ro r Tolerance using Differences of Moments 85 7.5 A d d i t i o n a l Complexi ty Issues 86 7.6 Summary 86 8 Conclusion 87 Bibliography 90 Append ix A Glossary of Terms 92 A . l General Graph Theory 92 A . 2 Classical Complexi ty 94 A . 3 Graph Theoretic and Complex i ty Problems 95 A . 4 Polygon Reconstruction Problem 97 A . 5 Reconstruction Algor i thm Modules 99 VI List of Figures 1.1 Even with as few as four non-convex points, given only vertex po-sitions without additional information, three different polygons may be reconstructed 3 1.2 Given the same four vertex positions along with possible edge direc-tions at every vertex, only a single solution remains possible 3 2.1 local blue and red axes for potential edges at a vertex 13 2.2 axes for potential edges 13 2.3 axes for actual edges 14 2.4 an ini t ia l graph G2 and a solution subgraph H2 15 2.5 odd-length cycle edge colouring 15 2.6 an ini t ia l graph G3 and a solution subgraph H3 16 3.1 a graph G and three subgraphs which are 2-factors of G 19 3.2 We replace vertices with one of the components in which 3-cycles and 2-cycles are disallowed, respectively 20 3.3 u ^ u ' and u " 20 3.4 mapping a 2-factor problem to a matching problem 21 3.5 reversing out-edge colours at a vertex 23 3.6 example of 3 - D I M E N S I O N A L M A T C H I N G instance and solution . . 23 3.7 single point component 24 vii 3.8 We represent a triple, (xi,yi,Zi), by this component 24 3.9 In an edge-bicoloured directed 2-factor, the triple component may be in one of two states 25 3.10 example of 3-dimensional matching within G" transformation . . . . 26 3.11 bounded-degree component for a vertex Xi, j / j , or Zk 27 3.12 edge-bicoloured directed 2-factor on bounded-degree component . . . 28 3.13 modified bounded-degree component 28 3.14 three cases when removing an additional edge 29 3.15 following either edge A or edge B 31 3.16 X O R component 31 3.17 two states of X O R component in a non-crossing 2-factor 32 3.18 crossover component 32 3.19 four states of crossover component in a non-crossing 2-factor . . . . 33 3.20 3-dimensional matching instance and solution in biparti te graph . . 33 3.21 stretching G '. 33 3.22 eliminate crossovers using crossover component 34 3.23 add mirror image and connect vertices 34 3.24 connecting triples from T to T' 35 3.25 two states of component in non-crossing 2-factor 35 3.26 full reduction from biparti te S and T to G 36 3.27 reduction components wi th directions added 36 4.1 A vertex may be in one of two colour states 38 4.2 propagation of vertex states 39 4.3 ambiguous solutions wi th in the octagon graph 42 4.4 two vertex states within different solutions 42 4.5 ambiguous solutions wi th in the six-point star 42 4.6 the Strakhov-Brodsky graph [SB86] 43 4.7 ambiguous solutions wi th in the St rakhov-Brodsky graph 44 vi i i 4.8 ambiguous solutions within the modified St rakhov-Brodsky graph [SB86] 44 4.9 general pattern within common-edge solutions 45 4.10 extended St rakhov-Brodsky graph 45 4.11 four instances of the extended Strakhov-Brodsky graph 46 4.12 multiple connected instances of ambiguous graphs 46 5.1 pipelined reconstruction modules 49 5.2 determining whether vertex v is compatible with vertex u 51 5.3 a parallelogram and its associated input position and axis data . . . 51 5.4 checking for possible edges between vertices 52 5.5 applying e d g e E l i m to reduce edge density to constant degree . . . . 53 5.6 edge elimination heuristic 53 5.7 two different edge eliminations which produce equivalent results . . . 54 5.8 axes at a vertex from the graph G2 55 5.9 local elimination rules 56 5.10 new commitment rule 57 5.11 original polygon and input data after applying commit 58 5.12 graphs G\ and G2 produced by b u i l d G r a p h and edgeE l im , respectively 59 5.13 constraint propagation 59 5.14 Constraint propagation continues on to produce a solution graph G3. 60 5.15 complex rectilinear polygon reconstructed by commit 61 5.16 set of 9 boxes reconstructed by commit 62 5.17 ambiguous input graph G\ and two subgraphs, G'2 and G2 63 5.18 recursive search tree descent . • 64 5.19 solution Hi and maximal ly reduced subgraph G3 65 5.20 two subgraphs of G'3: G'3 and G'3' '. 65 5.21 two solutions H2 and H3 66 ix 5.22 b u i l d G r a p h and e d g e E l i m results for two-connected Strakhov-Brodsky extension 67 5.23 two invalid vertices 68 5.24 9-edge fragment found in 12tvertex polygon 69 5.25 sum of subcomponent moments: mp = mpi + mp2 71 5.26 reconstruction by component decomposition 72 6.1 position and angle reconstructions for two graphs G\ and G2 • • • • 76 6.2 a northeast translation of polygon P by +(1,1) 77 6.3 top right corner of a regular 48-sided polygon 77 6.4 varying the number of sample points: n = 8, 12, and 16 78 6.5 varying the number of sample points: n = 16, 24, 32, and 64 79 7.1 two shapes wi th multiple densities 82 7.2 differentiating between partial solutions 83 7.3 identifying accurate and inaccurate vertices 84 7.4 error in differences of moments 85 x Acknowledgements I am indebted to several individuals for their extensive contributions in time, ideas, suggestions, and encouragement over the last few years. Professor Fai th F i ch started me on the road to graduate research in computer sci-ence at the Universi ty of Toronto. A s a professor, she sparked my interest in theory and, as a supervisor, she introduced me to the world of research. Professor Nicholas Pippenger welcomed me to the Universi ty of Br i t i sh Co lumbia and init iated our research on parallel game trees and opt imal routing policies. Professor J i m Varah is responsible for introducing the problem of polygon reconstruction from moments. His continued interest, enthusiasm, and involvement, as well as his patient explana-tions of the numerical mechanics of reconstruction were crucial in the development of this research. He kindly agreed to be a second reader for this thesis. M a r t i n Robi l lard and Michae l M c A l l i s t e r generously acted as proofreaders, both providing very helpful reviews. The big thanks go out to Professor D a v i d Ki rkpa t r i ck . He provided essential guid-ance and motivat ion, shared his innumerable ideas, and gave up endless hours of his time, day after day and month after month, allowing this thesis and all our work on polygon reconstruction to come into being. His role as a supervisor, a role model to graduate students, and an all-around great guy and friend is very much appreciated. I consider myself very lucky to have had the opportuni ty to work closely wi th such a great individual . S T E P H A N E D U R O C H E R The University of British Columbia August 1999 xi a mes chers parents, Yves et Christ iane Duroch' X l l Chapter 1 Introduction 1.1 P r o b l e m and M o t i v a t i o n The problem of reconstructing an unknown polygonal shape, P, viewed as a region in the Cartesian plane, from a finite number of its complex moments is motivated by a several mathematical , computat ional , and application-oriented considerations. Moment information derived from such diverse physical processes as tomographic (line integral) measurements, exterior gravitat ional , or magnetic field measurements, or thermal radiation measurements often provides the input data in reconstructing a two-dimensional object. In each case, these measurements represent available in-formation associated wi th an otherwise unspecified object. Th is complex moment data potentially provides enough information to allow the complete or partial re-construction of the original polygon, P [Dav64, Dav77, SB86, M V K W 9 5 , G M V 9 9 ] . 1.2 Previous W o r k For years, mathematicians and physicists have studied the relationship between shape and moment [ST43]. The moments of a region are the integrals of the powers of the independent variables over that region. The kth harmonic moment of a 1 2-dimensional polygon P is given by [ G M V 9 9 ] : (1.1) In early work, Davis showed that given only its complex moments up to the third order, the positions of all vertices of a triangle within the Cartesian plane can be successfully reconstructed [Dav64]. Thus, any three-vertex polygon can be recon-structed from its complex moments. Davis later proved a generalization of an earlier result by M o t z k i n and Schoenberg, a quadrature formula that provides the essential mathematical basis to polygon reconstruction from moments [Dav77, G M V 9 9 ] : T h e o r e m 1.1 (Davis, 1964) Let z\,.. .,zn designate the vertices of a polygon P in the Cartesian plane. Then we can find constants a\,..., an depending upon zi,.. .,zn but independent of f, such that for all f analytic in the closure of P: This formula allowed Milanfar et al. [ M V K W 9 5 ] to generalize Dav is ' result and show how a finite number of complex moments of P can be used effectively to reconstruct the vertices of P. Using their method, given complex moments for a polygon P within the Cartesian plane, one may reconstruct the positions of the vertices of P. Given sufficient additional information about the interconnection of vertices within P, such as convexity, one may reconstruct P itself. For n vertices, there are n(n — l ) / 2 possible edges. Thus, without additional information about the edge set of P, vertex position alone may be insufficient for complete reconstruction (see example in figure 1.1). Very recently, Golub et al. [GMV99] address some of the formidable numer-ical difficulties associated with this reconstruction. In addit ion, they demonstrate that partial information concerning a polygon's edges can also be derived from a (1.2) 2 Figure 1.1: Even with as few as four non-convex points, given only vertex positions without additional information, three different polygons may be reconstructed. finite number of its complex moments, raising the possibility of a more complete and general reconstruction scheme. This further development not only allows the repro-duction of original vertex positions, but also provides edge orientation constraints between vertices of P (see example in figure 1.2). A Figure 1.2: Given the same four vertex positions along with possible edge directions at every vertex, only a single solution remains possible. Specifically, given vertex positions for the set V of vertices of P in the Carte-sian plane, for every v € V, we may derive two angles, <f>\ and fa, each allowing in-edges at angles fa mod 7r and fa mod n, and out-edges at angles fa mod 7r + ^ and fa mod TT + f [ G M V 9 9 ] . Th is smaller set of potential edges greatly restricts the choice of edges in reconstructing P. In so doing, this additional extracted in-formation constrains the edge reconstruction problem, allowing reconstruction of non-convex shapes from moments. In general, even simply-connected polygonal regions are not uniquely speci-fied by even infinitely many of their complex moments [SB86], thereby precluding a completely general reconstruction scheme. Since there exist distinct two-dimensional 3 polygons whose moment signatures are identical (see Chapter 4) reconstruction from moments is l imited, independent of any reconstruction approach. In cases involving ambiguity, differentiating between possible reconstructed solutions requires addi-tional information, aside from the input complex moments. Having applied this ini t ia l phase of the solution, the reconstruction problem remains far from being solved. The numerical methods provide positions for vertices of P and partial information about potential bounding edges of P, expressed in terms of geometric constraints. We examine the problem of constructing polygonal regions consistent wi th this information. For many non-convex polygons, this latter phase of the reconstruction process becomes quite convoluted. The problem involves in -terconnecting reconstructed vertices with a superset of potential edges and applying constraint propagation along neighbouring vertices in search of a polygonal subset of edges. Al though , in practice, the vertex positions and edge constraints may contain error in their specifications, due either to error originating in the moment data or error introduced in the numerical computations, it is of interest to study the recon-struction problem wi th error-free moment information. A s we shall see, wi th in a graph-theoretic setting, this formulation translates directly into a restricted directed 2-factor problem on a directed graph G defined on the vertex set V. We examine the problem of reconstructing polygonal regions, or 2-factors, consistent wi th the derived partial information about vertex positioning and edge orientation. 1.3 Thesis Organiza t ion The organization of the material in this thesis is as follows. Chapter 1 introduces the polygon reconstruction problem, gives motivation for its examination, and presents a brief discussion of related research. Chapter 2 provides general background and definitions from graph theory, complexity, and polygon reconstruction. Chapter 3 discusses the 2-factor problem along with proofs that restrictions to the 2-factor 4 problem specific to our polygon reconstruction setting are N P - h a r d . Chapter 4 deals with properties of various graphs with respect to solutions to the reconstruction problem and discusses the uniqueness of solutions within specific graphs. Chapter 5 explains the various modules of the reconstruction algori thm. Chapter 6 examines the behaviour of the algorithm on various classes of graphs and challenges faced by the algori thm. Chapter 7 presents a list of potential future research areas which remain open wi thin the domain of polygon reconstruction from moments. Final ly , Chapter 8 summarizes the formal discussion of the polygon reconstruction problem. 5 Chapter 2 Problem Definition Before beginning our examination of the problem, we define terms that arise in general graph theory, related complexity theory, common problems found in graph-theoretic and classical complexity, and terms that arise in our discussion of polygon reconstruction. Final ly , we formally define the problem of reconstructing the poly-gon P from its complex moments. 2.1 Def in i t ion of Terms 2.1.1 Genera l Graph Theory The following terms 1 arise in many general graph theory problems. A graph, G = (V,E), is a collection of vertices, V, and edges, E. A vertex, v € V, is a single point or node in G. A n edge, e G E, represents a relationship between two vertices in G. We say edge uv G E if and only if there exist vertices u, v G V such that u and v are related under some relation R C V x V. Graphical ly, we represent e by drawing a s traight 2 line from u to v. If the edge relation is asym-JSee the glossary in Appendix A for a complete list of definitions. 2 W i t h i n our domain, all edges are assumed to be straight lines. 6 metric, then G is a directed graph or digraph, uv and vu are distinct possible edges between vertices v and u. Given graphs G = (V, E) and H = ( V , E'), i f is a subgraph of G if and only if i f is a graph, V C V, and E' C E. If V = V then i i is a spanning subgraph of G. A n edge coming from a vertex u into vertex v is called an in-edge locally at v. Conversely, an edge going from vertex v out to a vertex u is described as an out-edge locally at v. We represent vertex adjacency through a boolean adjacency matrix, M, where MUiV = true if and only if there exists an edge from vertex u to vertex v. The degree of a vertex v is the total number of edges incident upon v. Similarly, the in-degree of v is the number of in-edges at v and the out-degree of v is the num-ber of out-edges at v. The degree of a graph, G, is defined as the maximum degree amongst all vertices v E V. If we are given a pre-determined fixed positioning for the vertices of a graph G, then we say that G is an embedded graph. A n y fixed positioning of the vertices of G is described as an embedding of G. If there exists a two-dimensional embed-ding of graph G in the plane in which none of the edges of G cross, then we say G is planar. Such an embedding is a non-crossing embedding. A l l of the edges in a rectilinear embedding lie along a single orthogonal north-south, east-west axis. A graph G is simply-connected if for any two vertices u, v £ V we can find some sequence of vertices {v\,.. .,Vk} C V such that v\ = u, Vk = v, and for all 1 < i < k — 1, V{Vi+i £ E or £ E. A connected component G" C G is a maximal simply-connected subgraph of G. There cannot exist vertices v G V - V and u G V such that uv £ E or vu £ E. A cycle is a sequence of neighbouring vertices, { u i , . . . , U j t } C V, such that £ E for all 1 < i < k - 1 and v^vi £ £\ A fc-cycle is a cycle of length k. 7 A vertex v is an interior vertex within an embedded graph G, if there exists a cycle C C G such that v £ C and C encloses v wi th in i t . Conversely, v is an exte-rior vertex, if there does not exist such a cycle C. A graph G = (V, E) is bipartite if there exists a part i t ion of its vertices, V = V 1 U V 2 , such that, V\ 7^ 0 , V2 7^ (J), V i D V ^ = Q), and every edge viv2 € E has one endpoint in each part i t ion, vi £ V\ and v2 £ V2 or v% € V2 and v2 € V\. 2.1.2 Classical C o m p l e x i t y A s is often the case with the presentation of algorithms in theoretical computer sci-ence, the classes of problems P and N P find themselves present within our domain. Garey and Johnson [GJ79, page 27] formally define the class P as follows: P = { L : there is a polynomial time deterministic Turing machine program M for which L = Lm} Informally, the class P unites all problems that have deterministic polynomial-time algorithmic solutions. Tha t is, their solutions can be found deterministically in time proportional to some polynomial function in terms of the input size of the problem. Similarly, Garey and Johnson [GJ79, page 31] formally define the class N P as follows: N P = { L : there is a polynomial time nondeterministic Turing machine program M for which L = Lm} Informally, the class N P unites all problems that have nondeterministic polynomial-t ime algorithmic solutions. B y these definitions, P C N P . Thus, we 8 require a distinction between those problems that have known polynomial-t ime de-terministic solutions and those that do not. To compare the difficulty of two decision problems, we use a reduction function, R, which allows us to transform one problem to another. Papadimi t r iou writes: Tha t is, we shall be prepared to say that problem A is at least as hard as problem B if B reduces to A . Recall what "reduces" means. We say that B reduces to A if there is a transformation R which, for every input x of B , produces an equivalent input R{x) of A . Here by "equivalent" we mean that the answer to R(x) considered as an input for A , "yes" or "no," is a correct answer to x, considered as an input of B . In other words, to solve B on input x we just have to compute R{x) and solve A on i t . [Pap94, page 159] If we can show a polynomial-t ime reduction / from some problem q to a problem p, such that, V . T , x G q <=> f(x) G p, then we say p is at least as hard as q. We define a special class of problems, the class of N P - h a r d problems. If q is N P - h a r d and q is reducible to p in polynomial time, then p is also N P - h a r d . Th is special class of N P problems have the property that, for any N P - h a r d problem q other than S A T (Section 2.1.3) there is another N P - h a r d problem p, such that, p is reducible to q in polynomial time. Thus, problem q is "at least as complex" as problem p. Therefore, NP-hardness is a lower bound of complexity in a hierarchy of problems for which no deterministic polynomial-t ime algorithmic solution is known. 2.1.3 G r a p h Theoret ic and Complex i ty Problems The following problems have been studied extensively in classical graph theory and complexity. These problems wil l be relevant in our examination of complexity issues with respect to the polygon reconstruction from moments problem. A s we wil l see in Chapter 3, our reconstruction problem is very closely related to the problem of finding an n-factor wi thin a graph. Lovasz and P lummer write, 9 "a spanning subgraph regular of degree n is called an rc-factor." [LP86, page xxx] N - F A C T O R 3 is solvable in polynomial time [LP86, GJ79] . A 2-factor is an n-factor of degree 2. A directed 2-factor of G is a spanning subgraph H C G for which every vertex v £ V has exactly one in-edge and one out-edge. The problem of finding an unconstrained 2-factor in a general graph G is polynomial-t ime solvable [LP86, GJ79] . Closely related to the 2-factor is the Hamiltonian cycle. Lovasz and P lummer define, "a cycle which includes every point of a graph G is called a Hami l ton cycle of G . " [ L P 8 6 , page xxx] The problem H A M I L T O N I A N C I R C U I T is N P - h a r d [GJ79]. A matching is an n-factor of degree 1. Every vertex is met by exactly one edge. The problem of finding a matching in a general graph G is polynomial-t ime solvable [GJ79]. W i t h i n our reductions, we wil l refer to 3-dimensional matching. Garey and Johnson explain 3-dimensional matching as follows: The 3 - D I M E N S I O N A L M A T C H I N G problem is a generalization of the classical "marriage problem": Given n unmarried men and n unmarried women, along with a list of all male-female pairs who would be wil l ing to marry one another, is it possible to arrange n marriages so that polygamy is avoided and everyone receives an acceptable spouse? Analogously, in the 3 - D I M E N S I O N A L M A T C H I N G problem, the sets W, X, and Y cor-respond to three different sexes, and each triple in M corresponds to a 3-way marriage that would be acceptable to all three participants. T ra -ditionalists wi l l be pleased to note that, whereas 3 D M is NP -complete , the ordinary marriage problem can be solved in polynomial t ime. [GJ79, page 50] Another family of problems that wil l be of interest is S A T . Papadimi t r iou defines, " S A T I S F I A B I L I T Y (or S A T , for short) then is the following problem: Given a Boolean expression <j> in conjunctive normal form, is it satisfiable?"[Pap94, page 77] S A T I S F I A B I L I T Y is the best-known and, historically, the first NP -comple te problem [GJ79]. Garey and Johnson write, "the 3 - S A T I S F I A B I L I T Y problem 3 Formal descriptions of problems in complexity theory are traditionally given an identifier composed of a few brief descriptive words written in capital letters. 10 is just a restricted version of S A T I S F I A B I L I T Y in which all instances have exactly three literals per clause." [GJ79, page 48] 3 -SAT is also NP -comple te . 2 - S A T re-stricts instances to two literals per clause. Th i s tighter restriction on the problem makes 2 - S A T solvable in polynomial time [GJ79]. 2.1.4 P o l y g o n R e c o n s t r u c t i o n P r o b l e m The following definitions are specific to our discussion of moment-based polygon reconstruction. Given a graph G — (V,E), at every vertex v E V, we assign a single colour to each edge. We say G is an edge-bicoloured graph. This colouring is local; the colour at the head and tai l of an edge may differ. W i t h i n our domain, a vertex may only have two different colours of edges; we refer to these locally as red and blue. 4 If every v G V contains no more than two red in-edges, two red out-edges, two blue in-edges, and two blue out-edges, then G is a bounded-degree edge-bicoloured graph. Furthermore, if edges of similar colour and direction align along an axis (see figure 2.1) then G is a moment-derived edge-bicoloured graph. The angular constraints on potential edges, 4>\ and (j>2, impose an orthogonality between edges of similar colour. Thus, under a geometric interpretation of these constraints, edges of similar colour at a given vertex to belong to a common frame-work or axis. Each vertex has two such local axes with edges within an axis lying orthogonal to each other. We refer to a global framework whenever frameworks of common colour across all vertices in the graph lie within the same orthogonal axis. The red-degree of a vertex v is the total number of red edges incident upon 4We sometimes refer to global colouring in a graph, in which case, head and tail colours match for all edges e £ E. For presentation of graphs, we sometimes make use of a global colouring of edges. While locally, there are only two colours, globally, a graph may have more than two different colours. 11 v. Similarly, the blue-degree of v is the total number of blue edges at v. If a graph G has global colouring, then we may refer to the red-degree or blue-degree of G. If a vertex v has at least one in-edge of a given colour and one out-edge of a different colour, then we say v is valid. If v does not have any in-edges, does not have any out-edges or only has edges of one colour, then we say v is invalid. W h e n a vertex v has in-degree one, out-degree one, red-degree one, and blue-degree one, then we say v is happy. Otherwise, we say v is unhappy. If H = ( V , E') is a spanning subgraph of G wi th the property that every v £ V is happy, then i f is a solution subgraph of G. We describe the state of H as global happiness. Under the edge constraints of the reconstruction, a vertex v that is part of a solution may be in one of two vertex states: red-in, blue-out ( R I B O ) or blue-in, red-out ( B I R O ) . This state directly corresponds to edge commitments. A n edge e exists in one of three edge states: undecided, committed, or dropped. Whenever an edge is selected as being part of a part ial solution, we say that we commit to that edge. We refer to this decision as an edge commitment. A fragment is any sequence of vertices vi,...,V{ such that v^Vk+i £ E, for all I < k < i — I and and every vertex V2, • • •, t>i-i is happy. A fragment constitutes a part of a possible solution. Several graphs embody more than one possible solution. A n y such non-unique solution is an ambiguous solution. 2.2 M o d e l s Used and P r o b l e m Overview The basis of all models we study wil l be that of an embedded graph in the Cartesian plane in which vertices are subject to very specific local restrictions; given vertex positions for the set V of vertices of P in the Cartesian plane, for every v £ V, we may derive two angles, <\>\ and (f>2, each allowing in-edges at angles <j>\ mod ix 12 and 4>2 mod TT, and out-edges at angles <j>i mod k + | and 02 mod 7r + | [ G M V 9 9 ] . These restrictions have the following simple geometric interpretation. Each vertex has two independent axes assigned to it: a blue and a red axis. Each axis specifies two in-directions and two out-directions such that in-directions and out-directions within the axis are orthogonal (see Figure 2.1). W i t h i n a solution, the reconstructed vertex positions form a set of vertices, V", for a graph G = (V, E). A n edge e from vertex u to vertex v belongs to the edge set of G if and only if its direction agrees with one of the axes specified at each of u and v. We wil l colour the head and tai l of e wi th the colour of its associated axis. For example, say we have a graph G\ wi th four vertices, v\,..., v4, and each vertex Figure 2.1: local blue and red axes for potential edges at a vertex Figure 2.2: axes for potential edges 13 has red and blue axes given as in figure 2.2. The axes and their dotted extensions represent allowable edge directions. Whenever the out-direction from vertex u aligns wi th the in-direction at another vertex v., we have an edge uv. Figure 2.3 displays the actual edge set E\ that corresponds to this particular graph. Figure 2.3: axes for actual edges A solution to the polygon reconstruction problem is a spanning subgraph H of the directed and edge-bicoloured graph G in which every vertex has both in-degree and out-degree one and both red-degree and blue-degree one. Thus we are looking for a directed 2-factor of G that satisfies some local colour constraints, namely, global happiness. A t every vertex v £ V", a solution requires commitment to a single in-edge having some colour and a single out-edge of the opposite colour. Obviously, com-mitment at the head of an edge implies commitment at the ta i l and vice-versa. For example, figure 2.4 displays a graph G2 = ( V 2 , E2) for which we wish to find a globally-happy directed 2-factor. Every vertex v £ V2 is valid. Several v, however, are unhappy. H2 = (V 2 ' , E'2) is a spanning subgraph of G2. Every v £ V2 is both valid and happy. Furthermore, H2 represents a 2-factor of G2 for which every 1 1 Figure 2.4: an ini t ia l graph G% and a solution subgraph H2 vertex has both in-degree and out-degree one and both red-degree and blue-degree one. Thus, i f 2 is a solution subgraph of G'2 for the polygon reconstruction problem. In this example, the edge set E2 has two global frameworks: red and blue. Whenever an odd-length cycle finds itself wi thin a solution, then two colours are no longer sufficient for a representation of the graph with a global colouring. Since all vertices in a solution must be happy, at some point in any odd-length cycle, there must be an edge whose vertices do not agree on a global two-colouring (see figure 2.5a). Recolouring leaves the problem unchanged; we are searching for a globally-happy two factor within an edge-bicoloured graph. To facilitate the in-terpretation and presentation of such graphs, we introduce a new colour to allow global colouring, (see figure 2.5b). A A Figure 2.5: odd-length cycle edge colouring 15 Figure 2.6 displays a second example, a more involved graph, G3 = (V3l i J 3 ) , and a solution subgraph, H3. Unlike the previous graphs, in this case, edge set colouring can be made global only through the use of a third colour. Thus, G3 has three global frameworks. Note that locally, however, every vertex v £ V3 has exactly two colours of edges. A g a i n , J f 3 is a globally-happy directed 2-factor of G3. Figure 2.6: an ini t ia l graph G'3 and a solution subgraph H3 We divide the problem of moment-based polygon reconstruction into three distinct phases: 1. Given complex moment data as input, the first step of the reconstruction provides approximations to the Cartesian coordinates of the vertices and the angles for two axes of potential in-edges and out-edges at each vertex. 2. Vertex positioning and potential edge information is mapped to an embedded edge-coloured directed graph G. 3. We look for a spanning subgraph H C G that is a globally-happy 2-factor. 16 In our research, we examine the two latter steps with a focus on the last challeng the problem of finding a globally-happy 2-factor. 17 Chapter 3 Restricted 2-Factors The third phase in the problem of reconstructing a polygon from its complex mo-ments involves searching for a spanning subgraph H C G which is a globally-happy 2-factor. Thus, we are searching for a 2-factor with specific properties: a restricted 2-factor. In this chapter, we examine properties of various relevant restrictions to the general 2-factor problem. In Section 3.1, we examine the problem of finding a gen-eral 2-factor. In Section 3.2, we define three restrictions to the 2-factor problem. In Sections 3.3 and 3.4, we show NP-ha rdness for various restricted 2-factor problems, including, E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R , B O U N D E D - D E G R E E D I R E C T E D 2 - F A C T O R , and N O N - C R O S S I N G 2 - F A C T O R . Final ly , Section 3.5 summarizes our discussion of restricted 2-factors. The unconstrained directed 2-factor problem is polynomial-t ime solvable [GJ79, LP86] . The problem of finding a globally-happy 2-factor in polygon reconstruction from moments involves the imposit ion of specific restrictions on the unconstrained 2-factor problem. We identify these addit ional properties by four specific restrictions to the input graph and output 2-factor: 1. We may constrain edge choice by requiring global happiness in the resulting 2-factor. 18 2. We may require that edges of the 2-factor be non-crossing. 3. We may require that each local blue axis and red axis of the vertices of the input graph be orthogonal. 4. We may l imit in-degree and out-degree to two edges per colour at every vertex. In this chapter, we examine these four constraints in isolation to determine their effect on the difficulty of the problem. We discuss the relationship between our colour-constrained 2-factor problem and the unconstrained 2-factor problem. We show NP-hardness for specific 2-factor restrictions which embody essential aspects of the globally-happy 2-factor problem. 3.1 2-Factors The undirected 2-factor problem involves taking an undirected graph, G = (V,E), and finding a spanning subgraph, H = (V',E'), such that every vertex v G V has degree 2 (see figure 3.1). The directed 2-factor problem is similar to the undirected t Figure 3.1: a graph G and three subgraphs which are 2-factors of G problem but with the addit ional requirement that every vertex v G V' in the 2-factor must have in-degree 1 and out-degree 1. The colour constraints on edges may be restated as a cycle-restricted 2-factor prob-lem by replacing each vertex by a simple component. Figure 3.2 displays two com-19 red in red out red in red out blue in blue out blue in blue out Figure 3.2: We replace vertices with one of the components in which 3-cycles and 2-cycles are disallowed, respectively. ponents that embed colour constraints into the graph if 3-cycles are disallowed with use of the first component and if 2-cycles are disallowed wi th use of the second component. B y replacing all vertices with either of these components, the problem may be restated as a fc-cycle-restricted 2-factor problem, where k is either 2 or 3. W i t h o u t these restrictions, a closed fc-cycle within the component would allow two edges of similar colour to be included in a 2-factor. Given any directed graph, G = (V,E), an unconstrained 2-factor may be solved by mapping to a matching problem [LP86]. To do so, we make two copies of every vertex v 6 V. One instance retains all in-edges and the other retains all out-edges (see figure 3.3). A l l in-edge vertices, v', are placed into a part i t ion V and all out-edge vertices, v", are placed into a part i t ion V". We call this new graph G' = (V U V",E'). Whenever an edge uv appears in G, we include an edge from u" to v' in E' (see figure 3.4). Therefore, any directed graph, G, may be mapped to Figure 3.3: v v' and v 20 Figure 3.4: mapping a 2-factor problem to a matching problem an undirected bipartite graph G' such that uv G E O u"v' G E'. Thus, there exists a perfect matching in G' if and only if there exists a d i -rected 2-factor in G. The bipartite matching problem is solvable in polynomial-t ime [LP86]. The 2-factor problem, therefore, is also solvable in polynomial-t ime. Hell et al. show that disallowing /c-cycles makes the undirected 2-factor prob-lem polynomial-t ime solvable if k < 4 and N P - h a r d if k > 4 [ H K K K 8 8 ] . Th is polynomial-t ime solution to finding cycle-restricted undirected 2-factors provides motivating evidence for a possible polynomial-t ime solution to the globally-happy 2-factor problem. It wi l l follow later that disallowing fc-cycles makes the directed 2-factor prob-lem N P - h a r d for k = 2 and k = 3 (see Corol lary 3.2). We go on to show that re-str ict ing the 2-factor problem with colour constraints or disallowing crossing edges renders the problem N P - h a r d . Tha t is, we show that imposing properties 1, 2, or 4 render the problem N P - h a r d . 3.2 Res t r i c t ing the 2-Factor P r o b l e m The unconstrained directed 2-factor problem is polynomial-t ime solvable [GJ79, LP86] . Our polygon reconstruction problem differs from the basic 2-factor problem simply by the addition of one or more of the four additional constraints. The addition of these seemingly minor parameters significantly alters the complexity of 21 the problem. We know 2 - F A C T O R lies near the boundary between P and NP-complete since 2 - F A C T O R G P and H A M - C Y C L E G NP-complete [GJ79]. The only dif-ference between these two problems is that H A M - C Y C L E requires the existence of a single spanning cycle, namely, a Hamil tonian cycle, whereas 2 - F A C T O R allows multiple disjoint cycles whose union spans the graph. In addit ion to special colour constraints, one may reasonably require that polygonal regions be non-intersecting, that is, that their interior density be constant and non-negative. Th is corresponds to searching for a 2-factor in which no edges cross. Thus, we define three restrictions of 2 - F A C T O R that model specific aspects of our globally-happy 2-factor problem; these restricted 2-factor problems impose properties 1 (Theorem 3.1) properties 1 and 4 (Corol lary 3.3) and property 2 (Theo-rem 3.4) respectively. We examine the time complexities of each restricted problem. 3.3 Edge-Bico loured Di rec ted 2-Factor 3.3.1 P r o b l e m Instance and Question When imposing the first property, that the resulting 2-factor respect global-happiness, our problem reduces to the following: E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R I N S T A N C E : Directed graph G = (V,E), where edges of E are coloured red or blue at each end. Q U E S T I O N : Does G admit a directed 2-factor H wi th red-degree 1 and blue-degree 1 at each vertex? 22 3.3.2 E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R is N P - h a r d Using a component-based proof, we give a reduction from 3 - D I M E N S I O N A L M A T C H -I N G [GJ79] to E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R . To facilitate colouring within this proof, we interchange the colours of out-edges at every vertex. In doing so, vertex happiness may be achieved by finding a directed Figure 3.5: reversing out-edge colours at a vertex 2-factor such that, at every vertex, both edges have similar colour (see figure 3.5). Note that this does not alter the problem but simply alters the interpretation of the colour rules. A n instance of 3 - D I M E N S I O N A L M A T C H I N G consists of three sets of equal size, X , Y, and Z , along with triples of the form T = {(xi,yj, z^)} C X X Y X Z, such that every X{,yj, and zk appears in at least one triple. A solution to 3-D I M E N S I O N A L M A T C H I N G consists of a subset T* C T such that every £ 4 , % , X Y Z T X Y Z T Figure 3.6: example of 3 - D I M E N S I O N A L M A T C H I N G instance and solution 2:5 and Zk is visited exactly once. We represent a single point, Xi,yj, or z/. by a pair of vertices connected by a single blue edge (see figure 3.7). Figure 3.7: single point component We create a component that connects three points, xt, yt, and z, into a triple (see figure 3.8). Each triple has three pairs of blue edges that link the points to the component. Figure 3.8: We represent a triple, (a^, z,), by this component. In an edge-bicoloured directed 2-factor, every vertex must be met by exactly one in-edge and one out-edge of similar colour. Thus, either all three or zero outside blue paths may visit the construction (see figure 3.9). This forces all three or none of the points to be included in a edge-bicoloured directed 2-factor on the triple component. A point Xi may be a member of several triples, z , is linked up to every triple 24 Figure 3.9: In an edge-bicoloured directed 2-factor, the triple component may be in one of two states. component to which it belongs by a pair of blue edges. Thus, several pairs of blue edges may meet xt. We call this entire graph of linked triples and points, G' (see figure 3.10). In any edge-bicoloured directed 2-factor, only a single pair of blue edges may visit any xt. Thus, every Xj may only be included in exactly one triple. Since individual points may only be visited by one pair of edges and since points must be included in given triples, a 3-dimensional matching in T corre-sponds to an edge-bicoloured directed 2-factor in G'. Given any X, Y, Z, and T , a 3-dimensional matching can be found if and only if there exists an edge-bicoloured directed 2-factor in G'. We have shown a polynomial-t ime reduction function, fx, such that: x G 3 D M ^ fi(x) G E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R Therefore, we have proven: Theorem 3.1 (Kirkpatr ick-Durocher , 1999) E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R G N P - h a r d Recall that we originally sought to show polynomial-t ime complexity for E D G E -B I C O L O U R E D D I R E C T E D 2 - F A C T O R . In Section 3.1, we described a polynomial-time reduction, f2, from E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R to k-C Y C L E - F R E E D I R E C T E D 2 - F A C T O R for k = 2 and k = 3 such that: 2-") Figure 3.10: example of 3-dimensional matching within G' transformation * £ E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R O f2[x) e fc-CYCLE - F R E E D I R E C T E D 2 - F A C T O R , k G {2,3} If A ; - C Y C L E - F R E E D I R E C T E D 2 - F A C T O R were solvable in polynomial time for k = 2 or k = 3, then E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R could also be solved in polynomial time. B y contradiction, therefore, fc-CYCLE-FREE DI -R E C T E D 2 - F A C T O R cannot be solvable in polynomial t ime. Thus, we have shown: Corol lary 3.2 (Kirkpatr ick-Durocher , 1999) fc-CYCLE - F R E E D I R E C T E D 2 - F A C T O R G N P - h a r d , k G {2,3} 3.3.3 Bounded-Degree Edge-Bicoloured Di rec ted 2-Factor In our problem, the last property l imits a vertex to at most two in-edges and two out-edges of any colour. Through a simple modification of the vertex component, we 2 6 show that B O U N D E D - D E G R E E E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R remains N P - h a r d . We formally define B O U N D E D - D E G R E E E D G E - B I C O L O U R E D D I R E C T E D 2-F A C T O R as follows: B O U N D E D - D E G R E E E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R I N S T A N C E : Directed graph G = (V, E), where edges of E are coloured red or blue at each end and any v £ V has blue in-degree, blue out-degree, red in-degree, and red out-degree < 2. Q U E S T I O N : Does G admit a directed 2-factor H wi th red-degree 1 and blue-degree 1 at each vertex? Garey and Johnson write, 3 - D I M E N S I O N A L M A T C H I N G "also remains NP -complete if no element occurs in more than three triples, but is solvable in polynomial time if no element occurs in more than two triples." [GJ79, page 221] We exploit this fact and replace the two-vertex component with six vertices (see figure 3.11). Exac t ly three pairs of exterior blue edges meet the component. Figure 3.11: bounded-degree component for a vertex or Zk Since every vertex may appear in at most three triples, this new vertex component requires connecting edges to, at most, three triple components. Aga in , in an edge-bicoloured directed 2-factor, only a single pair of exterior blue edges may be followed (see figure 3.12). The difference, however, is that every 2 7 vertex now has blue in-degree, blue out-degree, red in-degree, and red out-degree bounded by two. Figure 3.12: edge-bicoloured directed 2-factor on bounded-degree component Following a proof identical to that from Theorem 3.1 except with use of this new bounded-degree component for points a?,-, jfj, or z&, we show that even wi th a single colour degree bound of two, the problem remains N P - h a r d . Thus, we have demonstrated: Corol lary 3.3 (Kirkpatr ick-Durocher , 1999) B O U N D E D - D E G R E E E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R £ N P - h a r d Final ly , in an attempt to bound degree as tightly as possible, we use a component that bounds red in-degree and out-degree to one (see figure 3.13). In doing so, we Figure 3.13: modified bounded-degree component show that even if we l imit blue in-degree and out-degree to two and red in-degree and out-degree to one, E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R remains N P - h a r d . 28 3.3.4 Degree Four versus Degree Five A t this point, one may wonder about the boundary between P and N P - h a r d . Does the problem become easier if vertices have lower degree? W h a t happens if we bound the degree any more t ightly? In our final reduction, any vertex, v, has red in and out-degree < 1. and, at most, three blue edges, only two of which have similar orientation. Thus, v has at most five edges. a c ^ j b d Figure 3.14: three cases when removing an additional edge If we remove any addit ional edge, one of three cases may arise. We may remove a red edge in which case only a single red edge remains (figure 3.14a), we may remove a blue edge such that two blue edges of similar orientation remain (figure 3.14b) or we may remove a blue edge such that two blue edges of opposite orientation remain (figure 3.14c). In each of these cases, the problem of finding an edge-bicoloured directed 2-factor can be described logically as a simple conjunction of disjunctions. The colour constraints on the above examples may be rewritten, respectively, as follows: b A {a © d) b A ( c © d) {a © d) A (b © c) A {a © 6) A (c © d) Note that exclusive-OR is itself logically equivalent to a conjunction of disjunctions: {x®y)= {x V y) A ( I V y) 29 The vertices of any graph of degree < 4, therefore, could be described by a conjunction of such disjunctions corresponding to local colour constraints. Every disjunctive clause contains at most two literals meaning that the problem reduces 1 to 2 - S A T . 2 -SAT is solvable in polynomial t ime [GJ79]. Reducing the number of edges to 4, therefore, brings the complexity down within range of polynomial- t ime solvabil-ity. When edges are orthogonal, Rendl and Woegingner show that reconstruction of sets of orthogonal line segments in the plane from the set of their vertices can also be done in polynomial time [RW93]. Thus , we have shown that with at least five edges at every vertex, E D G E - B I C O L O U - R E D D I R E C T E D 2 - F A C T O R is N P - h a r d . However, wi th at most four edges at any vertex, E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R G P . Even under ex-tensive pruning of edges, therefore, E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R remains N P - h a r d . 3.4 Non-Cross ing 2-Factor 3.4.1 P r o b l e m Instance and Question If we ignore colour constraints and simply require that property 2 be respected, that polygonal regions be non-intersecting, our 2-factor problem reduces to a restricted 2-factor problem in which we disallow crossing edges. For simplicity, we first ex-amine the problem of finding a non-crossing 2-factor on an undirected graph. We formalize the problem as follows: N O N - C R O S S I N G 2 - F A C T O R I N S T A N C E : Undirected embedded graph G = (V, E). 1 A reduction from problem p to problem q shows that q is "at least as hard" as p. Thus, when showing NP-hardness of q, we reduce a known NP-hard problem to q. When showing q E P, the argument is reversed and we reduce q to a known P problem. 30 Q U E S T I O N : Does G admit a 2-factor H, none of whose edges intersect except at their endpoints? 3.4.2 NON-CROSSING 2-FACTOR is NP-hard Using a component-based proof, we give a reduction from 3 - D I M E N S I O N A L M A T C H -I N G to N O N - C R O S S I N G 2 - F A C T O R . 2 We wil l present a reduction which is in i -t ial ly undirected but for which every component may be directed without any effect on functionality. The first component essential to the reduction is one that may be inserted at the intersection of two crossing edges, A and B, to force a logical exclusive-OR within a non-crossing 2-factor (see figure 3.15). Tha t is, either edge A or edge B may be A B A B B A B A Figure 3.15: following either edge A or edge B Figure 3.16: X O R component 2Jansen and Woeginger show that given an undirected graph G whose edges are axis-parallel, the problem of deciding whether G has a crossingfree two-factor is NP-complete [JW93]. Here we show that both the directed and undirected cases are NP-hard. 31 followed, but not both, nor neither, nor some fragment of either. The component construction is displayed in figure 3.16. Note that any non-crossing 2-factor wi th in this component must find itself in one of two states. Ei ther either the path A — A or the path B — B is followed. A n y other combination forces edges to cross (see figure 3.17). Figure 3.17: two states of X O R component in a non-crossing 2-factor Figure 3.18: crossover component We require a second component to eliminate unwanted edge-crossings. In-serting this component does not affect membership of edges within a 2-factor but eliminates actual crossing. In a non-crossing 2-factor, this construction forces one of A — A, B — B, neither or both edges to be followed (see figures 3.18 and 3.19). No other combination of edges is possible. For example, it is impossible to visit only the bottom B edge and the top A edge without forcing edges to cross. 32 Figure 3.19: four states of crossover component in a non-crossing 2-factor We may now begin the reduction from 3 - D I M E N S I O N A L M A T C H I N G . Let S = X U Y U Z. The sets S and T form a bipartite graph G (see figure 3.20a). S T S T Figure 3.20: 3-dimensional matching instance and solution in bipartite graph F ind ing a 3-dimensional matching amounts to finding a subset of edges of G which meet every vertex in the S parti t ion exactly once and every vertex in the T part i t ion exactly zero or three times (see figure 3.20b). S T Figure 3.21: stretching G We first stretch G onto diagonals (see figure 3.21). 33 We replace all crossovers using our crossover component (see figure 3.22). Th is implies that any 2-factor within the graph wi l l be non-crossing. Figure 3.22: eliminate crossovers using crossover component We add a mirror image of the entire graph and connect top vertices to their corresponding neighbours on the bot tom. C a l l this graph G' (see figure 3.23). Figure 3.23: add mirror image and connect vertices We require a special component to connect triples from T to T' (see figure 3.24). In a non-crossing 2-factor, this component forces either all six or zero outgoing edges to be included (see figure 3.25). A s required, therefore, either all three or none of the members of a triple are included in a non-crossing 2-factor. 34 Figure 3.24: connecting triples from T to T" Figure 3.25: two states of component in non-crossing 2-factor Since the edges from S to S' are forced and the edges in T and T1 have the property that either all three or none may be followed, finding a 3-dimensional matching in G corresponds to finding a non-crossing 2-factor in G'. Given any S and T, a 3-dimensional matching can be found if and only if there exists a non-crossing 2-factor in G'. We have shown a polynomial-t ime reduction function, / 3 , such that: x e 3 D M o h{x) e N O N - C R O S S I N G 2 - F A C T O R Therefore, we have proven, N O N - C R O S S I N G 2 - F A C T O R £ N P - hard 35 Figure 3.26: full reduction from bipartite S and T to G In our input domain, graphs are directed. Each component within this con-struction may be directed without any alteration to its function (see figure 3.27) Figure 3.27: reduction components wi th directions added Following a proof identical to that for N O N - C R O S S I N G 2 - F A C T O R , ex-cept with use of these new directed components, we show that D I R E C T E D N O N -C R O S S I N G 2 - F A C T O R remains N P - h a r d . We therefore derive the following theo-rem : Theorem 3.4 (Kirkpatr ick-Durocher , 1999) D I R E C T E D N O N - C R O S S I N G 2 - F A C T O R G N P - h a r d 36 3.5 Summary Using component-based reductions from 3 - D I M E N S I O N A L M A T C H I N G , we have shown that simple restrictions, such as edge-bicoloured constraints or non-crossing constraints, render the 2-factor problem problem N P - h a r d . These restrictions closely model various properties of our polygon reconstruction from moments prob-lem. A s demonstrated, this particular problem seems to lie very close to the bound-ary between P and N P - h a r d . The actual problem, encompassing colour constrains, non-crossing constraints, degree-bounds, and geometric orthogonal constraints re-mains to be shown to be polynomial-t ime solvable or N P - h a r d . 37 Chapter 4 Uniqueness of Moment Sets The vertices in a moment-derived edge-bicoloured graph have special properties which allow for colour constraints to be propagated between neighbouring vertices. We discuss the basis of colour constraint propagation in Section 4.1. Certain graphs embed multiple distinct solutions. Constraints cannot be propagated within such graphs. We discuss the properties of non-unique solutions in Section 4.2. 4.1 Commi tmen t Propaga t ion The global happiness requirement in edge selection forces any vertex v within a solution to be in one of two vertex states: red-in, blue-out ( R I B O ) or blue-in, red-out (BIRO) (see figure 4.1). Thus, v is constrained to having a single pair of Figure 4.1: A vertex may be in one of two colour states. 38 edges: red in and blue out, or, blue in and red out. We refer to these restrictions as colour constraints. Since these constraints are upon the edges of a vertex, vertices at both endpoints may be affected by the restrictions; constraint propagation occurs whenever the constraints at a vertex v affect the constraints at a neighbouring vertex u. F ind ing a 2-factor solution involves commit t ing to edges within the graph. Whenever a vertex v commits to an edge e, several implications arise from that commitment . A l l other edges of similar colour or similar direction at v must be dropped from the possible solutions space. For example, if e is a committed red in-edge at v, then all other red edges and all other in-edges incident on v are dropped; the only remaining type of edges allowed are blue out-edges, v now has vertex state R I B O . A commitment applies both to the head and tai l of an edge. Thus, whenever we commit to an edge uv, the vertex states of both u and v become fixed. For. example, say vertex u is in vertex state R I B O and a blue edge connects u to vertex v. If we commit to uv, then the vertex state of v becomes B I R O (see figure 4.2). Similarly, dropping an edge applies to both the head and tail of an edge. Thus, Figure 4.2: propagation of vertex states whenever we drop an edge uv, the vertex states of both u and v may be affected. If graph H2 C Hi is a spanning subgraph of Hi and all edges E C Hi - H2 may be removed from Hi by constraint propagation, then we say H2 is a reduced graph of Hi. If no further edges may be removed from H2 by constraint propaga-tion, then H2 is maximally reduced. 39 A s we wi l l see in Section 5.4, such commitment propagation forms the basis of our algorithm for finding solutions within a graph. There exist graphs, however, for which simple commitment propagation cannot be used to simplify a graph towards a solution subgraph. Some of these graphs embody more than a single solution subgraph. Commi tmen t propagation alone wi l l not provide a solution on such a graph. 4.2 N o n - U n i q u e Solutions Interestingly, some graphs embed more than one globally-happy 2-factor. Under or-dinary conditions, there would be no reason to expect such a graph to arise naturally; non-unique solutions graphs occur infrequently and require specific contrived con-structions. Thei r properties, however, are quite fascinating to examine and provide insight into the mechanisms and obstacles of constraint propagation. In this section, we explore the uniqueness or non-uniqueness of solutions within edge-bicoloured graphs. A solution to an edge-coloured graph G = (V, E) is a globally-happy 2-factor span-ning subgraph, H C G. For two distinct solutions to exist, there must exist two such subgraphs, Hi and H2, such that Hi ^ H2. Since Hi and H2 have a common vertex set, V, we must have that Ei ^ E2. We distinguish between three types of graphs with non-unique solutions within a hierarchical classification. Graphs with distinct state solutions con-tain exactly two solutions, Hi and H2, such that for any vertex v £ V, v is in vertex state R I B O in Hi and B I R O in H2 or vice-versa. Graphs with distinct edge solu-tions may contain two or more solutions, Hi,..., Hk, such that for any edge e £ E, e appears in at most one solution Hi,..., Hk- Tha t is, the intersection of the edge sets of any two solution subgraphs is empty. Graphs with common edge solutions have one or more edges e which remain present in two or more solutions. 40 If a graph embodies three or more solutions, then in at least two of the so-lutions, there must be some v € V whose vertex-state is unchanged. The solutions of such a graph cannot be distinct state solutions. We further classify solutions by examining connectedness (simple or multiple) and edge crossing (crossing or non-crossing). W i t h respect to common edge solutions, Milanfar et al. state the following propo-sition [ M V K W 9 5 ] : Proposit ion 4.1 (Milanfar et al . , 1995) Consider n distinct points, 2 1 , 2 2 , • • • , 2 n in the Cartesian plane. Let P and P' be simply connected, nondegenerate, n-gons generated by connecting these vertices in two distinct ways. If P and P' have at least one side in common, then for some 1 < j < n, aj(P) aj(P'), where a,j(P) and aj(P') are, respectively, defined by: II, h"(z) dx dy = ^2a]{P)h(zJ) P f I h"(z) dx dy = J2aJ(P')h(zJ) J JP' j = 1 with h denoting any analytic function in the closure of P U P'. Proposi t ion 4.1 claims that if P and P' are two distinct polygons which have at least one edge in common, then P and P' cannot be solutions to the same set of input constraints, otherwise P and P' must include degenerate vertices. Cont ra ry to this proposition, in this section, we wil l demonstrate the existence of such common edge solutions, where all vertices are nondegenerate. We first look at the octagon graph (see figure 4.3). The octagon is the simplest graph (least number of vertices) we have found which contains two simply-connected ambiguous solutions. Figure 4.3a displays the entire supergraph G\. Figures 4.3b and 4.3c display the two possible globally-happy 2-factors of G\. These 2-factors are 41 Figure 4.3: ambiguous solutions within the octagon graph simply-connected but the second obviously involves edge-crossing. Note that at ev-ery vertex v, v is either in vertex state R I B O or B I R O in the different solutions (see figure 4.4). Furthermore, binding any single vertex to a fixed vertex state immedi-Figure 4.4: two vertex states within different solutions ately determines the configuration of the remaining edges in the solution. Thus, G\ is a graph with distinct-state solutions for which all solutions are simply-connected but not all are non-crossing. Figure 4.5: ambiguous solutions within the six-point star 42 Another simple graph which contains non-unique solutions is the hexagonal six-point star (see figure 4.5). Th is graph embodies three solutions. In this case, the star solution, figure 4.5b, is simply-connected, but the other two solutions, figures 4.5c and 4.5d, involve separate components. A g a i n , edge-crossing occurs within some solutions. Strakhov and Brodsky present a very cleverly constructed graph [SB86] which contains two solutions respecting simple-connectedness and non-crossing edge prop-erties (see figure 4.6). The Strakhov-Brodsky graph is created by merging two Figure 4.6: the Strakhov-Brodsky graph [SB86] instances of the six-point star, removing a vertex from each, and displacing two others. To our knowledge, their construction is the simplest graph to embody mul-tiple simply-connected, non-crossing solutions. The interesting behaviour in many ambiguous graphs derives from having outer vertices which allow convexity within two vertex states (see figure 4.4). The two solutions to the Strakhov-Brodsky graph are displayed in figure 4.7. They are symmetrical reflections of each other along a central vertical axis. Wi th in all examples presented up to this point, no two solutions share a 43 Figure 4.7: ambiguous solutions within the St rakhov-Brodsky graph Figure 4.8: ambiguous solutions within the modified St rakhov-Brodsky graph [SB86] common edge unless the common edge belongs to a static disconnected component (as is the case with the outer hexagon in the six-point star in figures 4.5c and 4.5d). Strakhov and Brodsky also present a graph which contains two solutions sharing two common edges [SB86]. This graph may be constructed by simple modification to the regular St rakhov-Brodsky graph (see figure 4.8). Note the two triangles in figure 4.8b. Their inside edge is also present in the first solution in figure 4.8a. Given any graph which contains ambiguous solutions Hi and H2, one may easily add constant edges by selecting any edge e, e 6 Hi, e £ H2, and inserting three additional vertices to form a triangle along the edge (see figure 4.9a). We call this new graph G' and its solutions H[ and H'2. Since e £ Hi, in solution H[, we do not include edge c (see figure 4.9b). Conversely, since e ^ H2, in solution H'2, we include edge c but not edges a or e (see 44 Figure 4.9: general pattern within common-edge solutions figure 4.9c). The resulting graph, G" , is such that, in both solutions, edges b and d remain constant. The modified St rakhov-Brodsky graph has two non-crossing solutions, but one of the solutions is composed of disconnected components. Thus we examine the problem of finding a graph with common-edge ambiguous solutions such that all solutions are non-crossing and simply-connected. B y extension of our observations about inserting constant edges, we can augment the regular Strakhov-Brodsky graph such that all solutions share common edges along the exterior of the graph and all solutions remain simply-connected and non-crossing. Figure 4.10: extended Strakhov-Brodsky graph Let SBi and SB2 be the two solutions to the regular St rakhov-Brodsky graph. We choose two edges e\ and e2 along the perimeter of the graph such that e\ £ SBi, e\ £ SB2, e2 £ SBi, and e2 £ SB2. We add a series of static edges to connect e\ and e 2 (see figure 4.10). These edges are such that only one of the two ends wil l connect to the graph within a solution. Thus, both solutions solutions, SB[ and SB2, remain simply-45 Figure 4.11: four instances of the extended Strakhov-Brodsky graph connected and non-crossing. The difference between the regular and the extended St rakhov-Brodsky graphs is that SB[ and SB'2 share common edges. Significantly, we can join two such extended St rakhov-Brodsky graphs together by l inking their common edges to create a graph which has four simply-connected, non-crossing solutions (see figure 4.11). Figure 4.12: multiple connected instances of ambiguous graphs One quickly observes that we may join k such extended St rakhov-Brodsky graphs together to form a graph which embeds 2k simply-connected, non-crossing solutions (see figure 4.12). Thus, the number of solutions may be exponential wi th respect to the size of the graph. Therefore, we have shown: Theorem 4.2 (Durocher-Kirkpatr ick , 1999) For any n 6 Z+, there exist 2n distinct simple polygons in the Cartesian plane, each composed of 30n + 4 vertices, such that all 2n polygons have identical moment sets. 46 Thus, for any n € Z + , there exists an edge-bicoloured regular graph G = (V, E) such that | V | < kn and G contains 2™ distinct simply-connected non-crossing globally-happy 2-factors, where k = 34. Our various extensions to the St rakhov-Brodsky graph demonstrate the existence of multiple common edge solutions to a single set of input vertices. A l l vertices within these solutions are nondegenerate, which contradicts proposition 4.1. 4.3 Summary We have examined vertex properties which allow for the propagation of colour con-straints. We use this propagation as a means of reducing a graph G towards a solution subgraph G'. Some graphs embed several non-unique solutions; the num-ber of such solutions may be exponential wi th respect to the size of the graph. W i t h i n a multiple solution graph, constraint propagation alone cannot be used to reduce a graph to a solution. In Chapter 5, we discuss various methods which allow for the reduction of both unique-solution and non-unique-solution graphs. 47 Chapter 5 Reconstruction Algorithm We have examined the various properties of input graphs and their embedded so-lutions. We now discuss algorithms that solve the problem of reconstructing the original polygon from which a set of moments were measured. 5.1 Recons t ruc t ion Process Overview Recall the three-phase subdivision of moment-based polygon reconstruction: 1. Given complex moment data as input, approximate the Cartesian coordinates of the vertices and the angles for two axes of potential in-edges and out-edges at each vertex. 2. M a p vertex positioning and potential edge information to an embedded edge-coloured directed graph G. 3. F i n d a spanning subgraph H C G that is a globally-happy 2-factor. Here we describe algorithms that were developed 1 to implement phases two and three of the reconstruction process. The algorithm modules form a pipeline and J Each of the various algorithm modules presented here were implemented in M A T L A B . A l l results and examples discussed were produced by running the M A T L A B code. Some figures were redrawn from M A T L A B plots for clearer presentation. The recons module is based on code written by J. Varah to implement the initial phase of reconstruction de-48 may be broken down as follows: 1. r econs takes k moment measurements and produces a set of n vertex positions and two sets of n angles each, for local red and blue edge axes at each respective vertex. Usually, k = 2n. 2. b u i l d G r a p h takes n vertex posit ions 2 along with blue and red axis angles for each and builds a dense edge-bicoloured graph G\ which includes edges for any matching combination of in-edge and out-edge angles (Section 5.2). 3. e d g e E l i m takes G\ as input and produces a moment-derived edge-bicoloured spanning subgraph G2 such that every vertex has at most two edges of similar colour and orientation and these are at an angle 7r to each other (Section 5.3). 4. commit works recursively on G2 using colour constraint propagation to produce a solution subgraph G3 for which no further constraint propagation is possible (Section 5.4). moment data 2-factor solution Figure 5.1: pipelined reconstruction modules These four phases form the basic assembly line to transform moment data into reconstructed polygons (figure 5.1). A s we wil l discuss, this solution process scribed in his manuscript [GMV99]. A l l other modules were written by S. Durocher and D. Kirkpatrick. 2 For examples that include significant numerical error and cause inaccurate position and angle input data to bui ldGraph, we fix the output of recons to provide perfect information (see Section 6.1). 49 may require extra manipulation and flow-control, and thus, we wil l describe three addit ional modules: 5. t reeSearch works recursively down a search tree towards solutions whenever constraint propagation alone wi th in module commit fails to reduce G3 to a final solution (Section 5.5). 6. f ragmentSearch is used whenever the input domain includes imperfect data. Par t ia l fragmented solutions are researched as opposed to complete 2-factors (Section 5.6). 7. momentDiff allows for extremely noisy data to be reconstructed piecewise through re-iteration of the recons module on differences of moments (Sec-tion 5.7). 5.2 B u i l d G r a p h : B u i l d i n g the In i t ia l G r a p h After having passed through the ini t ial phase of reconstruction, we are presented with a set of vertices, V. Each vertex v £ V has an embedded position in the two-dimensional Cartesian plane and two associated angles for its local red and blue axes. We wish to form a graph G' i which includes an edge for any two vertices u and v such that u and v are compatible. We use the following definition for vertex compatibi l i ty: Definition 5.1 Given two vertex positions, u and v, an in-edge angle /3' at u, an out-edge angle 7 ' at v, and a deviation tolerance angle a, let <f> be the angle of the straight line between u and v, let (3 = \(j> — f3'\, and let 7 = \<f> — v is compatible with u under the relation C(v, u) if and only if (3 < a and 7 < a. Basically, two vertices u and v are compat ib le 3 whenever they have corre-3 The compatibility relation is asymmetric: C(u, v) C(v,u), for u,v £ V. 50 sponding in-edge and out-edge angles which lie within a window of tolerance. F i g -ure 5.2a displays two such vertices with the tolerance angle a and the line segment uv superimposed. In figure 5.2b, the edges at u and v are added and we see the two differences of angles, (5 and 7. Since both /3 and 7 lie within the window a, we create an edge vu (figure 5.2c). U Q v . . •>'JU ""•• ' t> v Figure 5.2: determining whether vertex v is compatible wi th vertex u In this way we build the preliminary graph G\\ for every pair of vertices u and v, we check to see if u and v are compatible according to Definition 5.1. Whenever u is compatible with v, we include the edge uv in G\. Figure 5.3: a parallelogram and its associated input position and axis data For example, figure 5.3a displays a parallelogram. The vertex position and axis angle data which would provide input to b u i l d G r a p h are displayed in fig-51 ure 5.3b. The b u i l d G r a p h module proceeds to check all pairs of vertices for possible edges (figure 5.4a) to produce the graph G\ (figure 5.4b) before passing it along the pipeline to the e d g e E l i m module. Figure 5.4: checking for possible edges between vertices Thus , we complete the first phase of the pipeline, having constructed an edge-bicoloured graph G\ of all compatible vertex pairs, (u, v) 6 V X V. 5.3 E d g e E l i m : Simpl i fy ing the G r a p h The ini t ia l graph G\ produced by b u i l d G r a p h may be very dense. A n y possible pairs of vertices which align are granted an edge between them. Whenever three or more vertices align in a common direction, if the in-edge and out-edge angles fall within the i tolerance, then a semi-complete interconnection may be produced. We would like to reduce the degree of G\ to form a moment-derived edge-bicoloured spanning subgraph. For example, figure 5.5a displays six co-linear vertices whose in-edge and out-edge 52 C O »0« O M O »0 Figure 5.5: applying e d g e E l i m to reduce edge density to constant degree angles align. In this case, b u i l d G r a p h wil l construct the high-degree graph G i dis-played in figure 5.5b. We use e d g e E l i m to reduce the graph to the desired subgraph G2 displayed in figure 5.5c. For every vertex v G G\, e d g e E l i m reduces the degree of v such that there may be at most one edge of any given orientation and colour per hemisphere, where a hemisphere is defined to be half a rotation about the vertex or an angle of w radians. Thus, v wil l have at most one red in-edge, one red out-edge, one blue in-edge, and one blue out-edge per hemisphere. A s required, v will conform to having no more than four edges per colour axis. Our heuristic keeps only the shortest edge and eliminates al l others along a common direction with similar orientation and colour (see figure 5.6). Figure 5.6: edge elimination heuristic Obviously, depending upon the tolerance angle a in b u i l d G r a p h , there wil l be instances when the heuristic eliminates the true edge and retains an invalid edge. This usually results in an equivalent solution. For example, figure 5.7a displays the 53 -*0 o -J a b c Figure 5.7: two different edge eliminations which produce equivalent results ini t ia l reconstruction G\ of an eight-vertex polygon which has four co-linear vertices on its right side. b u i l d G r a p h has included additional edges along these co-linear vertices. The original polygon may have been one of two possible shapes: a simply-connected closed polygon (figure 5.7b) or a multiple-component rectangle with a square hole within it (figure 5.7c). In the latter case, the square hole is positioned very close to the right exterior edge of the rectangle. The two figures differ only by the additional thin strip which links the top and bot tom to form a closed hole. The area of this thin strip is quite small wi th respect to the rest of the polygon, some small e which depends upon the tolerance a and the scale of the figure. Re-constructing the former or the latter shape, therefore, gives a solution which is very close to the desired polygon. Furthermore, given the input information, we have no way of choosing a best solution between figures 5.7b and 5.7c. Thus, we ap-ply our heuristic and eliminate all but the shortest edge along a common direction with similar orientation and colour to produce the second graph, G2. In our exam-ple / th is results in figure 5.7b being passed along to the next phase of reconstruction. Thus, we complete the second phase of the pipeline, having simplified the graph G' i such that each vertex has constant red-degree, blue-degree, in-degree, and out-degree within a hemisphere; e d g e E l i m produces a moment-derived edge-bicoloured graph spanning subgraph, G2-54 5.4 C o m m i t : Co lou r Constra int Propaga t ion After having passed through r econs . b u i l d G r a p h , and edgeEl im, we are given an input graph G2 whose vertices have bounded degree and whose edges fall locally into two geometrically-restricted axes as displayed in figure 5.8. Figure 5.8: axes at a vertex from the graph G2 We now begin the final phase of the reconstruction. Here, we are given a moment-derived edge-bicoloured input graph G2 wi th in which we wish to find a globally-happy 2-factor. The first method employed to achieve this end is through the use of the commit module. The commitment algorithm performs a recursive walk through the graph, visi t ing each vertex no more than a constant number of t imes. 4 The walk propagates colour constraints between neighbouring vertices to eliminate edges and to reduce the graph in a greedy manner. After successive edge eliminations, constraints may no longer be propagated and three types of output graphs, G'3, may be produced: 1. G'3 may be a s o l u t i o n graph, that is, a globally-happy 2-factor. 2. G3 may be an i n v a l i d graph containing one or more invalid vertices (see definition in Section 2.1.4). This case only arises when the original input graph, G'2, does not contain a solution subgraph. 4 A s we will see, vertices may only be revisited after some action, be it edge-commitment or edge-elimination, has occurred at a neighbouring vertex. Since vertices have a maximum degree of eight, no more than eight such visits may take place and, thus, the constant is exactly eight. Therefore, commit has linear worst-case runtime: 0 ( | V | ) . 55 3. G*3 may be in a state where colour constraints can no longer be propagated. The algorithm requires two or more recursive search branches (see Section 5.5). A s mentioned, the essence of the commitment algorithm involves colour constraint propagation. The constraints arise from our requirement for global-happiness. For a vertex to be happy, it must have in-degree one, out-degree one, red-degree one, and blue-degree one. Initially, all edges are in the undecided state. After finding a 2-factor solution, all edges wi l l either be committed edges or they wil l have been dropped. Thus, we work towards a solution by altering the state of an undecided edge to being committed or dropped. We do so by applying two types of rules: local elimination rules and new commitment rules. Local elimination rules follow a basic format: at a vertex v, we check for va-cancies and eliminate edges accordingly. If v does not have any blue in-edges, then v can never be in vertex state B I R O . Thus, v has no need for red out-edges and we eliminate all red out-edges at v (see figure 5.9a). Similarly, if v does not have t o M b Figure 5.9: local elimination rules any blue out-edges, then v can never be in vertex state R I B O , v has no need for red in-edges, and we eliminate all red in-edges at v (see figure 5.9b). We apply respective rules for absent red in-edges and red out-edges. The local elimination rules involve checking for dropped edges. Conversely, we may check for committed edges and, hence, we develop new commitment rules. Recall that a committed edge is one which belongs to the final solution sub-graph. Whenever a vertex has only one edge of a given colour or a given orientation, 56 then that edge must be contained wi th in a solution and, therefore, we commit to the edge. Edge-commitment affects the remaining edges of vertices at both endpoints of the newly-committed edge. For example, vertex u in figure 5.10 has a single blue edge, e\. Since there are no other blue edges, we make e\ a committed edge. Commitment at the head of an edge implies commitment at the ta i l . Thus, vertex v inherits a committed blue out-edge. This new commitment fixes the vertex state of v to R I B O . Vertex v can never be in state B I R O and no longer needs blue in-edges or red out-edges. A l l blue in-edges and red out-edges are dropped. We apply respective rules for all four combinations of commit ted edges. Rules are applied locally at a vertex. WThenever the application of a rule involves a change in edge state, the neighbouring vertex along the affected edge must be alerted; its local edge set has been altered either by having lost an edge or by having one of its edges committed and, consequently, should be revisited. Since the application of a single rule at a vertex can trigger changes at many neighbouring vertices, commitment propagation occurs quite rapidly in a highly reactive recursive fashion. We visit vertices one at a time. Upon visi t ing a vertex, we check to see if any of the local elimination or commitment rules apply and perform actions accordingly. In order to keep track of affected vertices which st i l l need to be Figure 5.10: new commitment rule 57 visited, we maintain a set of active vertices. Thus, our algorithm falls into place. Initially, we know nothing about vertices and we must visit every vertex at least once. Therefore, our ini t ia l active set is simply the set of all vertices. We may visit any vertex in the set 5 and apply the colour rules to i t . After having visited the vertex, we remove it from the active set and add any affected neighbours to the set. Once the set is empty, colour constraints have been propagated as much as the graph allows, and we return the current graph, G3. dt c, Figure 5.11: original polygon and input data after applying commit Let us trace a simple example through the four phases of reconstruction while paying special attention to commitment propagation. The original shape from which moment data has been obtained is an eight-vertex, simply-connected closed figure (figure 5.11a). Given 16 moment measurements for this shape, r e cons returns a set of 8 vertex positions along with a blue and red axis orientation for each (figure 5.11b). 5 T o improve performance, we sort the active set by non-decreasing degree such that vertices of low degree are visited first. Vertices of lower degree d, d > 3, have greater potential to trigger propagation "reactions." 58 Figure 5.12: graphs G\ and G2 produced by b u i l d G r a p h and edgeE l im , respectively Given these 8 positions and 8 pairs of axes, b u i l d G r a p h produces the ini t ial graph, G\ (figure 5.12a). Th is graph includes edges for every possible pair of com-patible vertices. e d g e E l i m takes G\ as input, simplifies the edge set by reducing the degree at every vertex, and produces the bounded-degree edge-bicoloured graph, G2 (figure 5.12b). Figure 5.13: constraint propagation 59 The graph G2 is passed to commit where commitment propagation begins. Initially, the active set, A, is the set of all vertices: A = {a, b, e, d,e, / , § , k}. We begin by visi t ing vertex d. Since d only has one red edge, a red out-edge de, then the vertex state at d becomes fixed to B I R O . We can therefore apply local elimination rules to remove all blue out-edges (see figure 5.13a). Since there are only two edges remaining at d, cd and de, we commit to each of them (represented by bold edges). Vertex d is then removed from A and affected neighbours, g in this case, are added to A: A' = (A - {d}) U {c, e, g) = {a, b, c, e, / , g, h}. We then visit vertex g. Since g only has two edges, a red in-edge fg and a blue out-edge gh, we commit to each of these (see figure 5.13b). Once again, we update A: A' = (A - {g}) U {/, h} = {a, b, c, e, f, h}. Figure 5.14: Constraint propagation continues on to produce a solution graph G3. We now visit vertex / . Vertex / has a committed red out-edge, fg. Vertex / also has another red out-edge, fc, which is undecided. Obviously, edge ft can be dropped (see figure 5.14a). Vertex / now only has two edges remaining, and we commit to each of these. We update A: A' = (A - {/}) U {e} = {a, b, c, e, h}. 60 The remaining edges form a globally-happy 2-factor (see figure 5.14b). The algorithm sti l l requires visits to each of {a, b, c, e, h} to commit to their edges. Note that a happy vertex whose edges are both commit ted cannot be added to the active set again since the state of its edges may no longer be altered. The algorithm ter-minates and the graph G3 is returned as a solution. For most graphs which embed a single unique solution, commit successfully finds and returns the solution subgraph. Figures 5.15 and 5.16 display more complex examples which were solved by commit . In each figure, the first plot is the graph G2 returned by e d g e E l i m and the second plot is the graph G3 returned by commit. In C - * 0 O—O O—+O O—fcO O—WO o—*o cm—o o—*o 0—*o cm—0 0—*o cm—0 -f' o*—0 CM—O m Cm—O A *-? 0*—0 0—*o cm—0 1 0*—0 c—*o cm—o 0 — 0 -*o*—o cm—o cm—o Figure 5.15: complex rectilinear polygon reconstructed by commit figure 5.16a, only six vertices have ini t ia l edge configurations which may propagate constraints. A l l other 30 vertices require constraints to be passed to them. The module commit searches for a globally-happy 2-factor through the prop-agation of colour constraints. This technique often succeeds in finding a solution. Sometimes, however, constraint propagation alone comes to a halt before having found a solution. For these cases, we require a recursive search tree. 61 ^ 4 Figure 5.16: set of 9 boxes reconstructed by commit 5.5 TreeSearch: Recursive Search Trees When the subgraph G'3 produced by commit is not a globally-happy 2-factor, con-straints can no longer be propagated at any of the vertices of G3. Hence, we require another mechanism to decide upon which edges belong to a solution. Given a graph G'3 on which constraint propagation has been exhausted, the t r e e S e a r c h module manages control of a simple backtracking approach which allows propagation to resume. We choose an undecided edge e £ G3 and create two new graphs, G 3 and G 3 , where edge e is dropped in G 3 and committed in G 3 . We then proceed to solve the two separate problems of searching for solutions within G 3 and G3' using commit. Aga in , we have the same three possible outcomes at the end of both of these branches. Either , we have a solution, the resulting graph is invalid, or constraint propagation has again been exhausted. If the last case arises, we simply repeat the process, branch again, and continue. A l l valid solutions are accumulated and returned as a set of possible solutions to the original input graph. In selecting the candidate edge e, we search for a vertex of lowest degree 62 greater than two and choose one of its edges. We do so because any vertex of degree two requires both of its edges in a solution. Forcing a new edge state at a vertex of degree three or greater, however, should trigger some constraint propagation, wi th lower degree vertices being more reactive in general. This basic heuristic for choosing edges works efficiently on most examples examined. Even if only minimal commitment propagation results from a decision, each vertex wil l only have been visited a constant number of times, and successive branching wil l eventually lead to a solution. Let us examine the search tree for a graph which contains three ambiguous so-lutions. Branching within the search tree is displayed in figure 5.18. Figure 5.17: ambiguous input graph G\ and two subgraphs, G'2 and G2. After having passed through recons, buildGraph, and edgeElim, we enter the module treeSearch. The input graph, G\, is displayed in figure 5.17a. G\ is the hexagonal six-point star which we saw in Section 4.2. treeSearch begins by calling commit wi th Gi as input (step 1). Every vertex v € G\ has at least one in-edge and one out-edge of each colour. Thus, an ini t ia l pass of commit fails to simplify G\ and outputs an unaltered graph, G2 = G\. A t this point, t reeSearch creates two modifications of G2 (step 2). A l l vertices along the exterior of G2 have lowest degree, in this case, 4. Thus, we select 63 an undecided edge at one of these vertices, say edge e. G2 is set to be G2 except with edge e dropped (figure 5.17b) and G2 is set to be G2 except wi th edge e committed (figure 5.17c). input graph Gi commit j 3 ^ v 4 0 maximally reduced graph G2 Gi r j ^ t r e e S e a r c h J t ^ G.< commit J [ commit 0 0 2-factor solution//; maximally reduced graph Gi r j | treeSearch jr-1 G." J commit J J commit I) 0 0 2-factor solution 2-factor solution//J Figure 5.18: recursive search tree descent We now branch for the first t ime. T w o parallel recursive calls are made to commit, one on input graph G'2 (step 3) and the other on G2 (step 4). W i t h i n the left branch (step 3) constraint propagation reduces the graph to a solution subgraph, Hi, displayed in figure 5.19a. W i t h i n the right branch (step 4) however, we reach another standsti l l : the maximal ly reduced subgraph, G3 C G2, displayed in figure 5.19b. t r e e S e a r c h creates two modifications of G3: G'z and G3 (step 5). Aga in , we look for a vertex of lowest degree greater than two. Every exterior vertex has degree 64 Figure 5.19: solution Hi and maximally reduced subgraph G3 two and every interior vertex has degree four. Therefore, we select an undecided edge from one of the interior vertices, say edge / . G'3 is set to be G3 except wi th edge / dropped (figure 5.20a) and G'3' is set to be G3 except wi th edge / committed (figure 5.20b). We now branch for the second time. Aga in , two parallel recursive calls are made to commit, one on input graph G3 (step 6) and the other on G'3 (step 7). After propagating constraints, these two calls emerge with solutions H2 and H3, respectively (see figure 5.21). A l l three solutions produced are valid, globally-happy 2-factors of the original graph. Given our input information, any of these 65 Figure 5.21: two solutions H2 and H3 three is as good a solution as the other. When discerning between ambiguous pos-sibilities in edgeElim, alternative cases had solutions which differed in area only by some small e. Non-unique solutions produced by treeSearch, however, may dif-fer greatly in area, connectedness and edge-crossing. In our example, solution H\ is a simply-connected, non-crossing polygon, solution H2 is a multiple-component, crossing polygon, and solution H3 is a multiple-component, non-crossing polygon. Whenever constraint propagation alone fails to provide a solution, treeSearch suc-cessfully reconstructs all solutions, regardless of the complexity of the input graph. For example, figure 5.22 displays the graphs Gi and G2 which are produced by buildGraph and edgeElim, respectively, when given the input vertices for a two-connected, extended St rakhov-Brodsky graph. In this case, treeSearch produced the actual output plots displayed in figure 4.11 (see Section 4.2). Thus, through recursive calls to commit down a search tree, our treeSearch module allows the reconstruction of all solutions contained within a subgraph. 66 after buildgraph after edgeelim Figure 5.22: bui ldGraph and edgeElim results for two-connected Strakhov-Brodsky extension 5.6 Fragment Search: F i n d i n g Fragments of Solutions The reconstruction modules commit and t reeSearch run under the assumption that all required information lies embedded within the input graph. Tha t is, all edges of a solution 2-factor must be edges of the graph G2. Imperfect data, however, may provide a less than perfect input graph for G2. A single missing edge can easily trigger an erroneous chain of constraint propagation which results in an invalid graph. For domains which involve imperfect input data, we need to relax our colour constraint rules and modify our search strategy. We have investigated two such techniques which were implemented in fragmentSearch and momentDiff. We be-gin by discussing module f ragmentSearch. Instead of looking for a globally-happy 2-factor, we search for fragments of happy 67 vertices. Thus , we seek portions of a solution which, when pieced together with missing edges, form potential reconstruction solutions. Unlike solutions found by commit and treeSearch, solutions constructed by f ragmentSearch are of a more subjective nature; t reeSearch wi l l return every globally-happy 2-factor contained within a graph, whereas f ragmentSearch must heuristically decide between possi-ble collections of fragments contained within a graph, and return those which might form pieces of a solution. Furthermore, in f ragmentSearch, eliminating an edge e may cause a vertex v to become invalid. Thus, unlike commit and treeSearch, in which ordering of events does not affect constraint propagation in the solution process, solutions produced by f ragmentSearch are subject to the ordering of elim-ination and commitment actions. A n input graph to f ragmentSearch may include invalid vertices, that is, vertices which may be without a given colour or orientation of edge (see figure 5.23). In this new algori thm, constraint propagation must account for such vertices. Thus, propagation is altered as follows: whenever we visit a vertex v from the active set A, we apply commitment and elimination rules as before, but only if v is valid. Upon visit ing an invalid vertex u, we simply remove u from A and continue. We retain our search tree approach and branch recursively on two calls to commit until the output graph embeds a collection of happy vertex fragments. When comparing two solutions, we use a simple heuristic and compare the lengths 6 of the longest fragment contained within each. If these have equal length, 6Here, "length" refers to the number of vertices in a fragment and not to geometric Figure 5.23: two invalid vertices lengt h. 63 we compare the next longest, and so on. Obviously, the solution wi th the longer fragment may not always be the better one; generally, however, a solution composed of one long fragment of k vertices provides a closer partial reconstruction than a different solution composed of several shorter fragments. In most examples, the fragment approach efficiently locates correct portions of solutions. For example, figure 5.24a displays the reconstructed vertices of an E -shaped polygon produced by r e c o n s . Note the irregularities in vertex position and potential angle data, especially near the middle of the figure. Figures 5.24b and 5.24c display the graphs G\ and G2 produced by b u i l d G r a p h and e d g e E l i m respectively. Neither Gi nor G2 contain a globally-happy 2-factor. Thus, as expected, when passed through commit and t r e e S e a r c h , no solution is found. The f r agmentSearch module, however, finds the fragment displayed in figure 5.24d. U p o n observation, we note that G2 does not embed any longer fragment. Thus, given our l imited input constraints, f ragmentSearch provides a valid partial solution. initial vertex reconstruction from moments 8 X ++_++ 00,00 8 X after buiidgraph after edgeelim segment found CO CO ++ 8 8 ++ + + ++, 8 8 Figure 5.24: 9-edge fragment found in 12-vertex polygon 69 Whenever the input domain includes imperfections in the data such that a globally-happy 2-factor is not contained within the input graph, we may use f r agmentSearch to reconstruct part ial solution composed of fragments of happy vertices. Such a partial solution often provides a close approximation to the original polygon and allows the reconstruction to overcome some degree of error arising from numerical computation or input data. 5.7 MomentDi f f : Component Recons t ruc t ion by Differ-ence of Momen t s The part ial solution provided by f r agmentSearch identifies portions of a graph in which data is more likely to be accurate. A long reconstructed fragment usually follows a string of vertices whose position and angle data closely match those of the original polygon. Long fragments of accurate vertices can be used along wi th the original moment input data in subsequent iterations of the reconstruction pipeline to obtain better position and angle approximations for inaccurate vertices. Given a polygon, P , and its moment vector, mp, for any subdivision of P into non-intersecting subcomponents, P i , . . . , P^ , the sum of the moment vectors of the sub-components of P is exactly equal to the moment vector of P: mp = mp1 +.. . + mpk. For example, figures 5.25a and 5.25b display a simple polygon P and a two-piece decomposition of P into P\ and P2. If we separately measure n moments for P , n moments for F i , and n moments for P2, we find that mp = mpl + mp2. Module momentDif f implements the following algori thm. Using a difference of moments, we can reconstruct a polygon, one component at a t ime. The reunion of all reconstructed components forms the complete original reconstructed polygon. Given a set of moments, m p , which correspond to an n vertex polygon F , n > 4, we use r econs , b u i l d G r a p h , and e d g e E l i m to create an n-vertex input graph, G\. 70 Figure 5.25: sum of subcomponent moments: mp — mpl + mp2 A call to f ragmentSearch on input G\ returns a part ial solution composed of edge fragments. Let us assume the longest fragment, 5 , has k vertices, S\,...,Sk, 3 < k < n. We form a new polygon P i , by taking the endpoints S\ and Sk, and creating a new edge siSfc. Polygon P i is a closed cycle of edges which corresponds to the closure of the edges of fragment 5 . If the vertices of 5 are accurate with respect to corresponding vertices wi th in the original polygon P , then P i is a subcomponent of P . We find the moments of P i , mpl, and a new difference of moments, ma = mp — mp1. We call recons again with this new difference of moments, ma , as input. The output vertices are run through buildGraph and edgeElim to produce a re-constructed graph G*2 of n — k + 2 vertices which correspond to the component P2 = P — P\- We search wi th in G2 using fragmentSearch for another longest par-tial solution. If G2 contains a globally-happy 2-factor, then we have successfully reconstructed P2 and we may assemble P by joining P i and P 2 . If not, then we take the longest fragment wi th in G2, and repeat this process recursively. Let us examine a simple example. A s we saw in Section 5.6, the recon-struction of a 12-vertex, E-shaped polygon P includes some inaccurate vertex posi-tions and angles which ini t ia l ly prevent a complete solution from being discovered, f ragmentSearch successfully finds the 9-edge fragment S\ displayed in figure 5.26a. 71 c Iri c o o A Figure 5.26: reconstruction by component decomposition Module momentDiff takes the closure of Si (figure 5.26b) finds its moments, rnsi: and the difference of moments, m& = mp — ms1. Upon a second pass through the pipeline, the reconstruction of forms the four-vertex polygon P2 displayed in figure 5.26c. If we adopt the premise that clockwise fragments of closed edges bound areas of positive density and counter-clockwise fragments of closed edges bound areas of negative density, then we find that the union of P i and P2 forms an exact reconstruction of P (figure 5.26d). We must note, however, that at this point in time, our experiments using differ-ences of moments as a method for polygon reconstruction have produced successful results only under very controlled conditions. Errors in moment differences produce "ghost" vertices which correspond to the differing regions between the perimeters of the two polygons (see Section 7.4). These addit ional vertices easily fool the algo-r i thm when searching for the second polygon, P2. For imperfect input domains, we successfully reconstruct partial solutions by search-ing for fragments of happy vertices. Reiteration of the reconstruction process on differences of moments provides interesting possibilities for piecewise polygon re-72 construction, and for complete solutions on these input domains. 5.8 Summary The process of reconstructing a polygon from its complex moments involves a multiple-phase pipeline of algorithms. Given a set of moments, we build vertex po-sitions and potential edge angles using module r e c o n s . We then construct a dense edge-bicoloured graph G\ of all possible pairs of compatible vertices using module b u i l d G r a p h . We simplify G\ into a moment-derived edge-bicoloured graph G2 using an edge elimination heuristic in module e d g e E l i m . Given that the input domain assumes accurate and complete information, modules commit and t r e e S e a r c h allow the reconstruction of all globally-happy 2-factor solutions, G'3. Whenever the input domain includes inaccurate or incomplete information, modules f r agmen tSea rch and momentDiff provide partial solutions and attempts at piecewise reconstruc-tions of complete solutions. Together, these algorithms present various approaches to the polygon reconstruction from moments problem. 73 Chapter 6 From Models to Real Data Upon being presented real moment data, the reconstruction of vertex positions and local angle axes often acquires some inaccuracies from numerical computat ion error and imperfect input moment data. Cer ta in types of vertices seem to be affected more than others upon encountering inaccuracies. In this chapter, we examine the various levels of control we may impose on input data (Section 6.1) we briefly discuss the success of reconstruction on specific families of graphs (Section 6.2) and, finally, we discuss the effect of varying the number of moments provided as input to the reconstruction (Section 6.3). 6.1 V a r y i n g C o n t r o l of the Input D a t a W i t h i n the reconstruction process, four decreasing levels of control may be imposed on input data to module b u i l d G r a p h . These determine the degree to which we fix the vertex position and potential angle information being passed on from module r econs . Vary ing the level of control allows us to test the functionality of the re-construction algorithms under various environments ranging from ideal to realistic conditions. We differentiate between the degrees of control as follows: 74 1. exact vertex and angle information: We may fix both position and angle data such that information passed onto buildGraph is exact. 2. exact vertex locations and exact moments: We may fix only vertex positions and reconstruct potential angle axes in recons using this positioning. Thus, half of the input data passed onto buildGraph is exact and half is reconstructed. 3. exact moment data: We may use perfect moment data as input to recons and reconstruct both position and angle data to be passed onto buildGraph. 4. actual moment data: We may acquire actual moment data, containing measurement imperfections, to be used as input to recons. Posi t ion and angle data reconstructed from these moments is then passed onto buildGraph. W i t h i n our research, we examined the performance of our algorithms on the input domains of exact vertex and angle information and exact moment data. 6.2 E x a m i n i n g the Behaviour of Var ious Graphs B y nature of the quadrature formula, vertices within a polygon that are co-linear or interior often trigger numerical computat ion errors in the reconstruction; positioning and potential edge angle reconstruction for these vertices often includes significant inaccuracy. Inaccuracies arise quite differently in slightly different graphs. For example, figure 6.1 displays the vertex positions and potential edge angles reconstructed by module recons for two graphs, G\ and G2, where G\ is a six-point star and G2 is an eight-point star. In each plot, the original polygon whose complex moments pro-vided input to module recons is displayed in solid lines overtop the reconstructed data. B o t h G\ and G2 contain sets of four co-linear vertices as well as many interior 75 initial vertex reconstruction from moments Figure 6.1: position and angle reconstructions for two graphs G\ and G2 vertices. Reconstructed vertex positions and potential angles are reconstructed ac-curately in graph G\. In graph G2, however, only exterior vertices are reconstructed accurately: {a, c, e, g, i, k, m , o). Interior vertices either include minor inaccuracies, {b,f,j,n}, or extreme, irrecoverable error, {d,h,l,p}. In the case of the last four vertices, their reconstructed positions appear at points 1, 2, 3, and 4. Thus, when working specifically with the graph-theoretic aspects of the re-constructions algorithm on graphs such as G\, we fix the output from module r econs and input perfect information to module b u i l d G r a p h . W h e n examining error-recovery abilities and partial solution search heuristics wi th in the reconstruction algorithms, we input actual position and angle information from module r econs , allowing inaccuracy to enter the input domain. Cer ta in families of shapes demonstrate interesting behaviour. The success of re-construction directly depends upon the relative location from which moments are measured within the plane. 76 Figure 6.2: a northeast translation of polygon P by +(1,1) For example, given a 12-sided regular polygon of radius 1, P, figure 6.2 displays two reconstructions of the vertices of P. In figure 6.2a, P is centered at (1,1). In figure 6.2b, P is centered at (2,2). In both figures, the original polygon is plotted in solid lines. W h e n centered at (1,1), vertices of P are accurately reconstructed. When centered at (2,2), however, the reconstruction becomes indecipherable. If we center a regular polygon P at the origin, the reconstruction remains per-fect. Upon at tempting to reconstruct a subcomponent of this same P, however, we again notice the introduction of inaccuracies. Figure 6.3a displays the reconstructed positions of the upper right 12 vertices of a regular 48-sided polygon centered at the origin. Figure 6.3b displays the results after processing by b u i l d G r a p h and fig-Figure 6.3: top right corner of a regular 48-sided polygon 77 ure 6.3c displays the results after processing by edgeElim and fragmentSearch. Note that one out lying vertex lies out of the displayed domain. Interestingly, a polygon including all 48 vertices can be reconstructed accurately, whereas as subset of size 12 cannot. Thus, subsets of sets of accurately reconstructible vertices are not necessarily accurately reconstructible themselves. 6.3 Dea l ing w i t h N u m e r i c a l E r r o r i n the Reconstruc-t ion Polygons that present challenges to the reconstruction require us to consider al-ternative approaches to reconstruct their vertex positioning and potential angles. Experimentat ion demonstrates that reconstruction inaccuracies may be reduced by increasing the number of moment measurements input to module recons. For example, figure 6.4 displays our familiar 12 vertex, E-shaped polygon P i whose vertices are independently reconstructed three times using an increasing number of moments. In figure 6.4a, module recons is given 8 complex moments and produces 8 vertex positions and axis angles. Undersampling provides an idea as to the general positioning of the polygon within the plane. In figure 6.4b, module recons is given 12 complex moments and produces 12 vertex positions and axis angles. In this case, reconstructed vertices lie close to actual positions but some <!• 4. •* Figure 6.4: varying the number of sample points: n = 8, 12, and 16 78 angles st i l l contain significant inaccuracies. F ina l ly , in figure 6.4c, module r e c o n s is given 16 complex moments and produces 16 vertex positions and axis angles. Thus, by oversampling, all vertices and angles of P i are accurately reconstructed. Increasing the number of samples usually improves reconstruction, but the results are not always as successful as for P i . For example, figure 6.5 displays an extended E-shaped polygon, P2. Here, we display the vertex reconstruction for increasing numbers of moments: n — 16, 24, 32, and 64. Note that extra reconstructed vertices lie close to a circle centered at origin. * * -2 0 2 * * # St >*P dp * » » * St ss % * 2 p» •» Figure 6.5: varying the number of sample points: n = 16, 24, 32, and 64 79 6.4 Summary Given complex moments, reconstruction of vertices sometimes includes inaccuracies. For some vertices, these imperfections remain recoverable and may be dealt wi th from within the domain of graph theory. In these instances, inaccurate vertices are left unaltered and error tolerance wi th in the reconstruction algorithms allows suc-cessful reconstruction. Other vertices, however, acquire significant position or angle error. For these cases, we require alternative methods of reconstructing position and angle, since we are provided too li t t le information from the ini t ia l reconstruction. 80 Chapter 7 Further Research Various partially explored and even completely unexplored questions branch out from the problems analyzed within this thesis. A m o n g these possible research paths are the following interesting areas: • W i t h i n our research, density is assumed to be uniform. We may consider the reconstruction of polygons wi th in domains of variable density (Section 7.1). • W h e n given two solutions to a reconstruction problem, we may wish to certify the validity of each answer, measure the closeness of the moment vectors of the two solutions, and choose a best solution between the two (Section 7.2). • Upon encountering inaccurate information, iteration of the ini t ia l reconstruc-tion formula could be used to create additional constraints using part ial results. Th is added input information might provide more accurate position and angle data (Section 7.3). • Block reconstruction by differences of moments as currently implemented only allows very l imited functionality. Greater error-tolerance wi th in module momentDif f could provide improved reconstruction of inaccurate input da ta (Section 7.4). • Current theorems about N P - h a r d restricted 2-factors could be used to show 81 NP-hardness for the problem of searching for a globally-happy 2-factor within a moment-derived edge-bicoloured graph (Section 7.5). In this chapter, we briefly visit each of these potential research areas and describe the motivating ideas from which they derive. 7.1 Var iable Internal Dens i ty A l l models examined include polygons of constant density. A r e a wi th in the polygon is assumed to be bipartite, such that, for any point a; in the Cartesian plane, only two states are possible: either x G P or x £ P. Real-world polygons, or 2-dimensional polygonal slices of 3-dimensional objects, most definitely include varying degrees of density. Explor ing reconstruction issues among such polygons might provide insight into additional realistic and application-oriented examples. Figure 7.1 displays three shapes, A , B, and C , which have components of different density. These represent three models that may be assumed. Densities may be assumed to be discrete units, or low positive integer values, as in example A . Alternat ively, densities may be assumed to be real positive values, as in example B . Final ly , reversed loops within a polygon may be interpreted as negative densities, as in example C . Figure 7.1: two shapes with multiple densities Thus, issues of varying or non-uniform density remain to be considered within polygon reconstruction from moments. 82 7.2 Cer t i fy ing Solutions Given two solutions, A and B, how do we measure which is a better solution? W i t h i n module f ragmentSearch , we discussed a heuristic that chose the solution with the longer fragment of happy vertices. Certainly, many other comparisons are possible. How do we differentiate between levels of validity? For example, figure 7.2 displays four solutions discovered by module f r agmentSearch on a = .157T and moments for an E-shaped polygon. W h i c h is the better solution? Figure 7.2: differentiating between part ial solutions One may hypothetically derive some measure of closeness by comparing mo-ments of the reconstructed polygon to the original input moments. Perhaps sta-tistical measurement of the differences between moments can provide a numerical description of this closeness. Thus, comparative certification of solutions, remains a mostly unexplored domain wi th in polygon reconstruction from moments. 83 7.3 Iterative Recons t ruc t ion Reiteration of the quadrature formula on a greater number of constraints may pro-vide a reconstruction that more closely resembles the original polygon. After an ini t ia l run of recons, upon encountering inaccurate information, vertices deemed accurate or inaccurate could be tagged and divided into corresponding parti t ions. Positions of vertices from the part i t ion of accurate vertices could then be used as addit ional constraints in a subsequent iteration of the reconstruction formula. The motivation being that additional information in a reiteration on a greater number of constraints may provide more accurate reconstruction for those vertices ini t ia l ly in the inaccurate part i t ion. For example, figure 7.3 displays a polygon P and its reconstruction P'. A s -suming we have a mechanism for identifying inaccurate vertices, we separate vertices Figure 7.3: identifying accurate and inaccurate vertices into two partitions: accurate (white) and inaccurate (black). The positions and edge angles of vertices in the accurate part i t ion are then used as addit ional input con-straints within a subsequent iteration of recons. This second call to recons could hypothetically provide a better reconstruction for the vertices of the inaccurate par-t i t ion. 84 7.4 Improving E r r o r Tolerance using Differences of M o -ments Instead of at tempting to improve the original vertex and angle positions recon-structed by recons, we may attempt to improve error tolerance within module momentDiff. Currently, differences between moments of the original polygon and subcomponents of the reconstructed polygon result in noisy errors wi th in moments causing ghost vertices. For example, figure 7.4a displays a polygon Q. Let us assume f ragmentSearch successfully finds the partial solution fragment in figure 7.4b. Modu le momentDiff takes the closure of this fragment, Qi, and searches for a reconstruction matching the difference of moments. Note that the position of vertex v is inaccurate. In at tempting to reconstruct the six-vertex polygon Q2, shadows of the difference Qs (figure 7.4c) cause error in the reconstruction. Hypothetically, ghost polygonal re-IA A Figure 7.4: error in differences of moments gions such as Q3 may be identified and reconstructed. In our example, i f vertex v were known to have inaccurate position, then module momentDiff could search for two subcomponent polygons, Q2 and Q3 (figure 7.4d). 85 7.5 A d d i t i o n a l Complex i t y Issues In Chapter 3, we proved that restricting the 2-factor problem in ways which resemble aspects of the polygon reconstruction problem are N P - h a r d . The actual problem involves finding a globally-happy 2-factor wi th in a moment-derived edge-bicoloured graph. Our proof demonstrated that searching for a globally-happy 2-factor within a bounded-degree edge-bicoloured graph is N P - h a r d . Thus, we ask ourselves the question, can we incorporate geometric orthogonality constraints into a reduction to prove that searching for a globally-happy 2-factor within a moment-derived edge-bicoloured graph is also NP -ha rd? Modif icat ions to current components may provide a reduction from 3 - D I M E N S I O N A L M A T C H I N G . Alternatively, new components imposing orthogonality of frameworks may allow a mapping from E D G E - B I C O L O U R E D 2 - F A C T O R . Perhaps the ex-ploitation of planarity, connectedness, and orthogonality within solutions might pro-vide assistance in designing a reduction. These complexity questions remain unanswered and invite future examination from the complexity theoreticians. 7.6 Summary M a n y avenues within polygon reconstruction from moments, including varying den-sity, solution validation, iterative reconstruction, error tolerance wi th in differences of moments, and problem of complexity, remain open and unexplored. These potential research domains present very tangible and genuine possibilities for improving the success of polygon reconstruction algorithms and for deepening our understanding of the nature of this problem. 86 Chapter 8 Conclusion Previous work by Davis [Dav64, Dav77] and Strakhov and Brodsky [SB86], along with recent work by Milanfar et al. [ M V K W 9 5 ] and Go lub et al. [ G M V 9 9 ] has inspired interest in the problems associated with the reconstruction of polygonal shapes from moments. Through their techniques, one may gather potential position and vector information about the vertices which lie on the perimeter of a polygon being reconstructed. This preliminary acquisition process finds an approximation to the Cartesian coordinates of the vertices along with two axes of possible in-edges and out-edges for each vertex. Each axis has two possible out-edges along a line perpendicular to two possible in-edges. A reconstructed polygon must pass through every vertex exactly once visit ing one out-edge and one in-edge from each axis. Our work consists of reconstructing the polygon based on this input infor-mation. We develop and analyze reconstruction algorithms wi th respect to their dependence on numerical error and spatial variation, their t ime complexity, and their abili ty to recognize ambiguous solutions when more than one exists. 87 The main results of this thesis include: • We have proved that some restricted 2-factor problems relating to the recon-struction problem are N P - h a r d . These include: - E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R - & - C Y C L E - F R E E D I R E C T E D 2 - F A C T O R (jfc £ {2, 3}) - B O U N D E D - D E G R E E E D G E - B I C O L O U R E D D I R E C T E D 2 - F A C T O R - N O N - C R O S S I N G 2 - F A C T O R - D I R E C T E D N O N - C R O S S I N G 2 - F A C T O R • We have examined the occurrence and properties of non-unique solutions within graphs. We have proven that there exist graphs that embed an ex-ponential number of distinct, simply-connected, non-crossing solutions with respect to the size of the input graph. • We have formulated edge-elimination rules which can be applied to reduce a graph towards a solution subgraph. Based on these rules, we have developed a linear-time reconstruction algorithm using constraint propagation. A s an extension to this algori thm, we have implemented a tree-based search routine which finds all possible solutions contained within a graph. • We have examined techniques to find part ial solutions within domains of im-perfect or inaccurate input data. These include searching for segments of solutions, iterative differences of moments, and use of addit ional input mo-ments. • We have observed the behaviour of the reconstruction algorithms on various classes of graphs, both those which reconstruct successfully and unsuccessfully. U n t i l now, research on the polygon reconstruction problem did not address the latter phase of reconstruction, namely, the problem of taking vertex positions 88 and potential angles, and reconstructing the final solutions. A s demonstrated wi th in this thesis, polygon reconstruction involves a multiple-phase geometric and graph-theoretic reconstruction process. Issues of non-uniqueness, ambiguity, position and angle inaccuracy, and erroneous input data must be considered when searching for solutions. Algor i thms and theorems presented here address these issues and present methods at deriving complete and partial solutions. These advances, along wi th other current developments, have revealed many un-explored branches wi th in polygon reconstruction from moments, in turn providing avenues for potential future research. 89 Bibliography [CLR92] T . H . Gormen, C . E . Leiserson, and R . L . Rivest . Introduction to Algorithms. M c G r a w - H i l l , New York , 1992. [Dav64] P. J . Davis . Triangle formulas in the complex plane. Mathematics of Computation, 18:569-577, 1964. [Dav77] P. J . Davis . Plane regions determined by complex moments. Journal of Approximation Theory, 19:148-153, 1977. [DK99] S. Durocher and D . Ki rkpa t r i ck . Resctricted 2-factor problems arising from moment-based polygon reconstruction. In Workshop on Computa-tional Graph Theory and Combinatorics, pages 55-57. Pacific Institute for the Mathemat ica l Sciences, 1999. [GJ79] M . R . Garey and D . S. Johnson. Computers and Intractability. W . H . Freeman and Company, New York , 1979. [C;MV99] G . H . Golub , P . Milanfar , and J . Varah . A stable numerical method for inverting shape from moments. SIAM Journal of Scientific Computa-tion, to appear, 1999. [ H K K K 8 8 ] P. Hel l , D . Ki rkpa t r ick , J . Kratochvf l , and I. K H z . O n restricted two-factors. SIAM Journal of Discrete Mathematics, l (4):472-484, 1988. 90 [JW93] K . Jansen and G . J . Woeginger. The complexity of detecting cross-ingfree configurations in the plane. BIT, 33(4):580-595, 1993. [LP86] L . Lovasz and M . D . P lummer . Ma tch ing theory. In Annals of Discrete Mathematics, volume 29. Nor th -Hol land Mathemat ics Studies, 1986. [ M V K W 9 5 ] P . Milanfar , G . C . Verghese, W . C . K a r l , and A . S. Wi l l sky . Recon-structing polygons from moments with connections to array processing. IEEE Transactions on Signal Processing, 43:432-443, 1995. [0 'R88] J . O 'Rourke . Uniqueness of orthogonal connect-the-dots. In G . T . Toussaint, editor, Computational Morphology, pages 97-104. Elsevier Science Publishers B . V . (North-Hol land) , 1988. [Pap94] C . H . Papadimi t r iou . Computational Complexity. Addison-Wesley, New York , 1994. [RW93] F . Rendl and G . Woeginger. Reconstructing sets of orthogonal line segments in the plane. Discrete Mathematics, 119:167-174, 1993. [SB86] V . Strakhov and M . Brodsky. O n the uniqueness of the inverse log-ar i thmic potential problem. SIAM Journal of Applied Mathematics, 46:324-344, 1986. [ST43] J . Shohat and J . Tamark in . The problem of moments. In Mathematical Surveys, volume 1. Waverly Press, Bal t imore, 1943. 91 Appendix A Glossary of Terms A . l Genera l G r a p h Theory graph A graph, G = (V,E), is a collection of vertices, V, and edges, E. vertex A vertex, v £ V", is a single point or node in a graph G. edge A n edge, e £ represents a relationship between two vertices in G . We say edge uv £ E 1 if and only if there exist vertices u, v £ V such that u and u are related under some relation R C V X V. Graphical ly, we represent e by drawing a straight line from u to v. directed graph If the edge relation is asymmetric, then G is a directed graph or digraph, uv and vu are distinct possible edges between vertices v and u. subgraph Given graphs G = (V, E) and H = (V, E'), i f is a subgraph of G if and only if i f is a graph, V C V, and E' C E. If V = V then i i is a spanning subgraph of G . in-edge, out-edge A n edge coming from a vertex u into vertex u is called an in-edge locally at v. Conversely, an edge going from vertex v out to a vertex u is described as an out-edge locally at v. 92 adjacency matrix We may represent vertex adjacency through a boolean adja-cency matr ix , M, where Mu<v = true if and only if there exists an edge from vertex u to vertex v. degree The degree of a vertex v is the total number of edges incident upon v. Similarly, the in-degree of v is the number of in-edges at v and the out-degree of v is the number of out-edges at v. The degree of a graph, G , is defined as the maximum degree amongst all vertices v £ V. embedded graph If we are given a pre-determined fixed positioning for the ver-tices of a graph G , then we say that G is an embedded graph. A n y fixed positioning of the vertices of G is described as an embedding of G . planar If there exists a two-dimensional embedding of graph G in the plane in which none of the edges of G cross, then we say G is planar. Such and embedding is defined as a non-crossing embedding. simply-connected A graph G is simply-connected if for any two vertices u, v £ V we can find some sequence of vertices {v\,... ,Vk} C V such that v\ = u, Vk = v, and for all 1 < i < k — 1, £ E or i>;+ii>; £ E. connected component A connected component G' C G is a maximal simply-connected subgraph of G. There cannot exist vertices v £ V — V and u £ V such that uv £ E or vu £ E. cycle A cycle is a collection of neighbouring vertices, {v\,.. .,Vk} C V, such that ViVi+i £ E for all 1 < i < k — 1 and VkV\ £ E. A fc-cycle is a cycle of length k. interior, exterior A vertex v is an interior vertex within an embedded graph G , if there exists a cycle C C G such that v £ C and C encloses v within it. Conversely, v is an exterior vertex, if there does not exist such a cycle C. 93 bipartite A graph G = (V, E) is bipartite if there exists a part i t ion of its vertices, •V = V i U V 2 , such that, V i + Q), V2 ^ © , V i n V 2 = © , and every edge Viv2 G f? has one endpoint in each part i t ion, v\ G V i and u 2 € V2 or U i G V 2 and v2 G V i . rectilinear A l l of the edges in a rectilinear embedding of a graph lie along a single orthogonal north-south, east-west axis. A . 2 Class ica l Complex i t y P Garey and Johnson [GJ79, page 27] formally define the class P as follows: P = { L : there is a polynomial time deterministic Turing machine program M for which L = Lm} Informally, P unites all problems which have deterministic polynomial-t ime algorithmic solutions. Tha t is, their solutions can be found deterministically in time proportional to some polynomial function in terms of the input size of the problem. N P Garey and Johnson [GJ79, page 31] formally define the class N P as follows: N P = { L : there is a polynomial time nondeterministic Turing machine program M for which L = Lm} Informally, the class N P unites all problems which have nondeterministic polynomial-t ime algorithmic solutions. reduction function To compare the difficulty of two decision problems, we make use of a reduction function, R, which allows us to reduce one problem to another. Papadimi t r iou writes: 94 Tha t is, we shall be prepared to say that problem A is at least as hard as problem B if B reduces to A . Recall what "reduces" means. We say that B reduces to A if there is a transformation R which, for every input x of B , produces an equivalent input R(x) of A . Here by "equivalent" we mean that the answer to R(x) considered as an input for A , "yes" or "no," is a correct answer to x, considered as an input of B . In other words, to solve B on input x we just have to compute R(x) and solve A on it . [Pap94, page 159] N P - h a r d If we can show a polynomial-t ime reduction from some problem q to a problem p, then we say p is at least as hard as q. We define a special class of problems, the class of N P - h a r d problems. If q is N P - h a r d and q is reducible to p in polynomial time, then we say p is also N P - h a r d . Th is special class of N P problems have the property that, for any N P - h a r d problem q other than S A T , there is another N P - h a r d problem p, such that, p is reducible to q in polynomial t ime. Thus, problem q is "at least as complex" as problem p. Therefore, NP-hardness is a lower bound of complexity in a hierarchy of problems for which no deterministic polynomial- t ime algorithmic solution is known. A . 3 G r a p h Theoret ic and Complex i t y Prob lems n-factor Lovasz and P lummer write, "a spanning subgraph regular of degree n is called an 7i-factor."[LP86, page xxx] N - F A C T O R is solvable in polynomial time [LP86, GJ79] . 2-factor A 2-factor is an n-factor of degree 2. A directed 2-factor of G is a spanning subgraph H C G for which every vertex v £ V has exactly one in-edge and one out-edge. The problem finding an unconstrained 2-factor in a general graph G is polynomial-t ime solvable [LP86, GJ79] . matching A matching is an n-factor of degree 1. Every vertex is met by exactly one 95 edge. The problem of finding a matching in a general graph G is polynomial-time solvable [GJ79]. Hamiltonian cycle Lovasz and P lummer define, "a cycle which includes every point of a graph G is called a Hami l ton cycle of G." [LP86] The problem H A M I L T O N I A N C I R C U I T is N P - c o m p l e t e [GJ79, page xxx]. 3-dimensional matching Garey and Johnson explain 3 - D I M E N S I O N A L M A T C H -I N G as follows. The 3 - D I M E N S I O N A L M A T C H I N G problem is a generalization of the classical "marriage problem": Given n unmarried men and n unmarried women, along wi th a list of all male-female pairs who would be wil l ing to marry one another, is it possible to arrange n marriages so that polygamy is avoided and everyone receives an ac-ceptable spouse? Analogously, in the 3 - D I M E N S I O N A L M A T C H -I N G problem, the sets W, X, and Y correspond to three different sexes, and each triple in M corresponds to a 8-way marriage that would be acceptable to all three participants. Traditionalists wi l l be pleased to note that, whereas 3 D M is NP-comple t e , the ordinary marriage problem can be solved in polynomial time. [GJ79, page 50] S A T Papadimi t r iou defines, " S A T I S F I A B I L I T Y (or S A T , for short) then is the following problem: Given a Boolean expression <f> in conjunctive normal form, is it satisfiable?"[Pap94, page 77] S A T I S F I A B I L I T Y is the best-known and, historically, the first N P - c o m p l e t e problem [GJ79]. 3 - S A T Garey and Johnson write, "the 3 - S A T I S F I A B I L I T Y problem is just a re-stricted version of S A T I S F I A B I L I T Y in which all instances have exactly three literals per clause." [GJ79, page 48] 3-SAT is also N P - c o m p l e t e . 2 - S A T 2 - S A T restricts instances to two literals per clause. Th is tighter restriction on the problem makes 2 - S A T solvable in polynomial time [GJ79]. 96 A.4 Po lygon Recons t ruc t ion P r o b l e m polygon reconstruction from complex moments Given a finite set of complex moments measured from a two-dimensional polygon P embedded wi thin the plane, we attempt to reconstruct the original shape of P. moment The moments of a region are the integrals of the powers of the independent variables over that region. The fcth harmonic moment of a 2-dimensional polygon P is given by [ G M V 9 9 ] : colour A t a vertex v, we assign a single colour to each edge. Th i s colouring is local; the colour at the head and ta i l of an edge may differ. We sometimes refer to global colouring in a graph, in which case, head and tai l colours match for all edges e G E. W i t h i n our domain, a vertex may only have two different colours of edges; we often refer to these locally as red and blue. For presentation of graphs, however, a graph, may have several different colours globally. edge-bicoloured A graph G = (V, E) is edge-bicoloured if, for every v G V, every edge at v has local blue or red colour. bounded-degree edge-bicoloured Given an edge-bicoloured graph G = (V,E), if every v G V contains no more than two red in-edges, two red out-edges, two blue in-edges, and two blue out-edges, then G is a bounded-degree edge-bicoloured graph. moment-derived edge-bicoloured G iven a bounded-degree edge-bicoloured graph G = (V,E), if edges of similar colour and direction align along an axis (see figure 2.1 in Section 2.3) then G is a moment-derived edge-bicoloured graph. 97 framework The angular constraints on potential edges, fa and fa, impose an or-thogonality between edges of similar colour. Thus, under a geometric interpre-tat ion of these constraints, edges of similar colour at a given vertex to belong to a common framework or axis. Generally, edges wi th in an axis lie orthogo-nal to each other. We refer to a global framework whenever frameworks of common colour across all vertices in the graph lie wi th in the same orthogonal axis. commitment Whenever an edge is selected as being part of a partial solution, we say that we commit to that edge. We refer to this decision as an edge commitment . vertex state A vertex v which is part of a solution may be in one of two states: red-in, blue-out (RIBO) or blue-in, red-out (BIRO) . Th is state directly corresponds to edge commitments. edge state A n edge e exists in one of three states: undecided, committed or dropped. valid, invalid If a vertex v has at least one in-edge of a given colour and one out-edge of a different colour, then we say v is valid. If v does not have any in-edges, does not have any out-edges or only has edges of one colour, then we say v is invalid. red-degree, blue-degree The red-degree of a vertex v is the total number of red edges incident upon v. Similarly, the blue-degree of v is the total number of blue edges at v. If a graph G has global colouring, then we may refer to the red-degree or blue-degree of G. happy, unhappy When a vertex v has in-degree one, out-degree one, red-degree one and blue-degree one, then we say v is happy. If v is not happy, then we say v is unhappy. 98 fragment A fragment is any sequence of vertices v%,..., u; such that VkVk+i £ -E\ for all 1 < A; < i — 1 and and every vertex U 2 , . . . , is happy. solution If H = ( V , £") is a spanning subgraph of G which has the property that every v 6 V is happy, then i f is a solution subgraph of G. We describe the state of H as global happiness. ambiguous solution Several graphs embody more than one possible solution. A n y such non-unique solution is an ambiguous solution. constraint Vertex happiness requires a single pair of edges: red in and blue out, or, blue in and red out. We refer to these restrictions as colour constraints. constraint propagation Constraint propagation occurs whenever the constraints at a vertex v affect the constraints at a neighbouring vertex u. reduction If graph H2 C H\ is a spanning subgraph of H\ and all edges E C Hi — H2 may be removed from i i i by constraint propagation, then we say H2 is a reduced graph of H\. If no further edges may be removed from H2 by constraint propagation, then H2 is maximally reduced. A . 5 Recons t ruc t ion A l g o r i t h m M o d u l e s recons Module r econs takes k moment measurements and produces a set of n vertex positions and two sets of n angles each, for local red and blue edge axes at each respective vertex. Usually, k = In. bui ldGraph Module buildGraph takes n vertex positions along wi th blue and red axis angles for each and builds a dense edge-bicoloured graph G\ which includes edges for any matching combination of in-edge and out-edge angles (Section 5.2). 99 edgeElim Modu le edgeElim takes G' i as input and produces a regular edge-bicoloured spanning subgraph Gi such that every vertex has at most two edges of simi-lar colour and direction which are geometrically opposite to each other (Sec-tion 5.3). c o m m i t Module commit works recursively on G2 using colour constraint propa-gation to produce a solution subgraph G'3 for which no further constraint propagation is possible (Section 5.4). treeSearch Modu le treeSearch works recursively down a search tree towards so-lutions whenever constraint propagation alone wi th in module commit fails to reduce G 3 to a final solution (Section 5.5). fragmentSearch Modu le f ragmentSearch is used whenever the input domain in-cludes imperfect data. Par t ia l fragmented solutions are researched as opposed to complete 2-factors (Section 5.6). momentDiff Modu le momentDiff allows for extremely noisy data to be recon-structed piecewise through re-iteration of the recons module on differences of moments (Section 5.7). 100
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Graph-theoretic and geometric algorithms associated...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Graph-theoretic and geometric algorithms associated with moment-based polygon reconstruction Durocher, Stéphane 1999
pdf
Page Metadata
Item Metadata
Title | Graph-theoretic and geometric algorithms associated with moment-based polygon reconstruction |
Creator |
Durocher, Stéphane |
Date Issued | 1999 |
Description | The problem of reconstructing an unknown polygonal shape P, viewed as a region in the complex plane, from a finite number of its complex moments is motivated by a number of mathematical, computational, and application-oriented considerations. Complex moment information can be derived from such diverse physical processes as tomographic (line integral) measurement, exterior gravitational, or magnetic field measurement, or thermal radiation measurement, associated with an otherwise unspecified object [GMV99, M V K W 9 5 , SB86]. Milanfar et al. [MVKW95], building on earlier work of Davis [Dav64, Dav77], show how a finite number of complex moments of P can be effectively used to reconstruct the vertices of P. If sufficient additional information (for example, convexity or rectilinearity) about P is known, P itself can be reconstructed. Very recently, Golub et al. [GMV99] address some of the formidable numerical difficulties associated with this reconstruction. In addition, they demonstrate that partial information concerning a polygon's edges can also be derived from a finite number of its complex moments, raising the possibility of a more complete and general reconstruction scheme. In general, note that even simply-connected polygonal regions are not uniquely specified by even infinitely many of their complex moments [SB86], thereby precluding a completely general reconstruction scheme. Given vertex positions for the set V of vertices of P in the Cartesian plane and partial information (expressed in terms of geometric constraints) about the edges bounding P, we examine the problem of constructing polygonal regions con sistent with this information. Although in practice, the vertex positions and edge constraints may contain error in their specifications (due either to error originating in the data or introduced in the numerical computations) it is of interest to study the reconstruction problem with error-free moment information. As we shall see, this translates to a constrained directed 2-factor problem in a directed graph G defined on the vertex set V. As observed in [GMV99], the potential edges incident on a vertex are subject to very specific local restrictions. These restrictions have the following simple geometric interpretation. Each vertex has two independent axes assigned to it: a blue and a red axis. Each axis specifies two in-directions and two out-directions such that in-directions and out-directions are orthogonal. A n edge joining vertex u to vertex v belongs to the edge set of G if and only if its direction agrees with one of the axes specified at each of u and v. We will colour the head and tail of each such edge with the colour of its associated axis. A solution to the polygon reconstruction problem is a spanning subgraph H of the resulting directed and edge-bicoloured graph in which every vertex has both in-degree and out-degree one and both red-degree and blue-degree one. Thus, we are looking for a directed 2-factor of G that satisfies some local colour constraints. This thesis addresses graph-theoretic and geometric concerns arising from momentbased polygon reconstruction. We show NP-hardness of various restrictions to the 2-factor problem. We investigate properties of moment sets whose graphs contain non-unique solutions. We develop algorithms to solve the problem of polygon reconstruction given both perfect and imperfect input moment data. Finally, we examine the success of reconstruction on various classes of graphs. |
Extent | 11223211 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-06-26 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051485 |
URI | http://hdl.handle.net/2429/9688 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1999-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1999-0488.pdf [ 10.7MB ]
- Metadata
- JSON: 831-1.0051485.json
- JSON-LD: 831-1.0051485-ld.json
- RDF/XML (Pretty): 831-1.0051485-rdf.xml
- RDF/JSON: 831-1.0051485-rdf.json
- Turtle: 831-1.0051485-turtle.txt
- N-Triples: 831-1.0051485-rdf-ntriples.txt
- Original Record: 831-1.0051485-source.json
- Full Text
- 831-1.0051485-fulltext.txt
- Citation
- 831-1.0051485.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051485/manifest