Graph-Theoretic and Geometric A l g o r i t h m s Associated with Moment-Based Polygon Reconstruction by Stephane D u r o c h e r B . S c . (Computer Science w i t h M a t h e m a t i c s M a j o r ) University of Toronto, 1997 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F THE REQUIREMENTS FOR T H E DEGREE OF M a s t e r of Science in T H E F A C U L T Y OF G R A D U A T E STUDIES (Department of C o m p u t e r Science) we accept this thesis as conforming to the required standard T h e UnrV^rsity of B r i t i s h C o l u m b i a A u g u s t 1999 © Stephane Durocher, 1999 In presenting degree this thesis in partial fulfilment of the requirements at the University of British Columbia, 1 agree freely available for reference copying of this department publication or thesis by of this and study. f o r scholarly his or thesis I further purposes gain of Co/y\ pcjVgJV" Sx^e./\if>^ The University of British Vancouver, Canada Date DE-6 (2/88) Columbia permission It is make it for extensive by the head understood shall not be allowed permission. Department that the Library shall may b e granted her representatives. for financial agree that for an advanced that without of my copying or my written Abstract 0 T h e 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, c o m p u t a t i o n a l , and application-oriented considerations. C o m p l e x moment information can be derived from such diverse physical processes as tomographic (line integral) measurement, exterior g r a v i t a t i o n a l , or magnetic field measurement, or thermal radiation measurement, associated w i t h an otherwise unspecified object [ G M V 9 9 , M V K W 9 5 , SB86]. M i l a n f a r et al. [ M V K W 9 5 ] , building on earlier work of D a v i s [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. V e r y recently, G o l u b et al. [ G M V 9 9 ] address some of the formidable numerical difficulties associated w i t h this reconstruction. In add i t i o n , they demonstrate that p a r t i a 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. G i v e n 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 w i t h this information. A l t h o u g h in practice, the vertex positions and edge constraints may contain error in their specifications (due either to error originating in the d a t a or introduced in the numerical computations) it is of interest to study the reconstruction problem w i t h error-free moment i n f o r m a t i o n . 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 geometric interpretation. E a c h vertex has two independent axes assigned to it: a blue and a red axis. E a c h axis specifies two in-directions and two out-directions such that in-directions and out-directions are orthogonal. A n edge j o i n i n g vertex u to vertex v belongs to the edge set of G if and only if its direction agrees w i t h one of the axes specified at each of u and v. W e will colour the head and t a i l of each such edge w i t h 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. T h u s , we are looking for a directed 2-factor of G that satisfies some local colour constraints. T h i s thesis addresses graph-theoretic and geometric concerns arising from momentbased polygon reconstruction. W e show N P - h a r d n e s s of various restrictions to the 2-factor problem. W e investigate properties of moment sets whose graphs contain non-unique solutions. W e develop algorithms to solve the problem of polygon reconstruction given both perfect and imperfect input moment d a t a . F i n a l l y , we examine the success of reconstruction on various classes of graphs. 111 Contents Abstract ii Contents iv List of Figures vii Acknowledgements xi Dedication 1 2 xii Introduction 1 1.1 P r o b l e m and M o t i v a t i o n 1 1.2 Previous W o r k 1 1.3 Thesis O r g a n i z a t i o n 4 P r o b l e m Definition 2.1 2.2 6 Definition of Terms 6 2.1.1 General G r a p h T h e o r y 6 2.1.2 Classical C o m p l e x i t y 8 2.1.3 G r a p h Theoretic and C o m p l e x i t y P r o b l e m s 9 2.1.4 P o l y g o n Reconstruction P r o b l e m M o d e l s Used and P r o b l e m Overview iv 11 12 3 R e s t r i c t e d 2-Factors 3.1 2-Factors 19 3.2 R e s t r i c t i n g the 2-Factor P r o b l e m 21 3.3 E d g e - B i c o l o u r e d Directed 2-Factor 22 3.3.1 P r o b l e m 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 F o u r versus Degree F i v e 29 3.4 3.5 4 5 6 18 N o n - C r o s s i n g 2-Factor 30 3.4.1 P r o b l e m 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 Summary 37 Uniqueness of M o m e n t Sets 38 4.1 Commitment Propagation 38 4.2 N o n - U n i q u e Solutions 40 4.3 Summary 47 Reconstruction Algorithm 48 5.1 Reconstruction Process Overview 48 5.2 B u i l d G r a p h : B u i l d i n g the Initial G r a p h 50 5.3 E d g e E l i m : Simplifying the G r a p h 52 5.4 C o m m i t : Colour Constraint Propagation 55 5.5 TreeSearch: Recursive Search Trees 62 5.6 FragmentSearch: F i n d i n g Fragments of Solutions 67 5.7 M o m e n t D i f f : C o m p o n e n t Reconstruction by Difference of M o m e n t s . 70 5.8 Summary 73 F r o m M o d e l s to R e a l D a t a 6.1 74 V a r y i n g C o n t r o l of the Input D a t a v 74 7 8 6.2 E x a m i n i n g the Behaviour of Various G r a p h s 6.3 D e a l i n g w i t h N u m e r i c a l E r r o r in the Reconstruction 78 6.4 Summary 80 Further Research • • • 75 81 7.1 Variable Internal Density 82 7.2 C e r t i f y i n g Solutions 83 7.3 Iterative Reconstruction 84 7.4 I m p r o v i n g E r r o r Tolerance using Differences of M o m e n t s 85 7.5 A d d i t i o n a l C o m p l e x i t y Issues 86 7.6 Summary 86 Conclusion 87 Bibliography Appendix A 90 G l o s s a r y of T e r m s 92 A.l General G r a p h T h e o r y 92 A.2 Classical C o m p l e x i t y 94 A.3 G r a p h Theoretic and C o m p l e x i t y P r o b l e m s 95 A.4 P o l y g o n Reconstruction P r o b l e m 97 A.5 Reconstruction A l g o r i t h m M o d u l e s 99 VI List of Figures 1.1 Even with as few as four non-convex points, given only vertex positions w i t h o u t additional i n f o r m a t i o n , three different polygons may be reconstructed 1.2 3 G i v e n the same four vertex positions along w i t h possible edge directions 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 initial graph G2 and a solution subgraph H 15 2.5 odd-length cycle edge colouring 15 2.6 an initial graph G3 and a solution subgraph H 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 3 2-cycles are disallowed, respectively 20 3.3 u ^ 20 3.4 m a p p i n g a 2-factor problem to a m a t c h i n g 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 u ' and u " vii 3.8 W e 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 w i t h i n 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 . . . . 3.20 3-dimensional matching instance and solution in bipartite graph 3.21 stretching G '. . . 33 33 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 bipartite S and T to G 36 3.27 reduction components w i t h 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 w i t h i n the octagon graph 42 4.4 two vertex states w i t h i n different solutions 42 4.5 ambiguous solutions w i t h i n the six-point star 42 4.6 the S t r a k h o v - B r o d s k y graph [SB86] 43 4.7 ambiguous solutions w i t h i n the S t r a k h o v - B r o d s k y graph 44 viii 4.8 4.9 ambiguous solutions within the modified S t r a k h o v - B r o d s k y graph [SB86] 44 general pattern w i t h i n common-edge solutions 45 4.10 extended S t r a k h o v - B r o d s k y graph 45 4.11 four instances of the extended S t r a k h o v - B r o d s k y 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 w i t h vertex u 51 5.3 a parallelogram and its associated input position and axis d a t a 5.4 checking for possible edges between vertices 5.5 a p p l y i n g e d g e E l i m to reduce edge density to constant degree 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 G 55 5.9 local elimination rules 56 5.10 new c o m m i t m e n t rule 57 5.11 original polygon and input d a t a after a p p l y i n g commit 58 . . . 52 . . . . 2 5.12 graphs G\ and G 2 51 53 produced by b u i l d G r a p h and e d g e E l i m , respectively 59 5.13 constraint propagation 59 5.14 C o n s t r a i n t 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' and G 63 5.18 recursive search tree descent . 64 2 • 2 5.19 solution Hi and m a x i m a l l y reduced subgraph G3 65 5.20 two subgraphs of G'3: G' and G' ' 65 3 5.21 two solutions H 2 3 and H '. 66 3 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 S t r a k h o v - B r o d s k y 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 = mp i + mp 71 2 5.26 reconstruction by component decomposition 72 6.1 position and angle reconstructions for two graphs G\ and G2 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 w i t h 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 • • • • 76 Acknowledgements I am indebted to several individuals for their extensive contributions in time, ideas, suggestions, and encouragement over the last few years. Professor F a i t h F i c h started me on the road to graduate research in computer science at the U n i v e r s i t y 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 University of B r i t i s h C o l u m b i a and initiated our research on parallel game trees and o p t i m a l routing policies. Professor J i m V a r a h is responsible for introducing the problem of polygon reconstruction from moments. His continued interest, enthusiasm, and involvement, as well as his patient explanations 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 R o b i l l a r d and M i c h a e l M c A l l i s t e r generously acted as proofreaders, both p r o v i d i n g very helpful reviews. T h e big thanks go out to Professor D a v i d K i r k p a t r i c k . He provided essential guidance and m o t i v a t i o n , shared his innumerable ideas, and gave up endless hours of his time, day after day and month after m o n t h , allowing this thesis and all our work on polygon reconstruction to come into being. H i s 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 o p p o r t u n i t y to work closely w i t h such a great i n d i v i d u a l . STEPHANE The University August of British Columbia 1999 xi DUROCHER a mes chers parents, Y v e s et Christiane Duroch' Xll Chapter 1 Introduction 1.1 P r o b l e m and M o t i v a t i o n T h e 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, c o m p u t a t i o n a l , and application-oriented considerations. M o m e n t information derived from such diverse physical processes as tomographic (line integral) measurements, exterior gravitational, or magnetic field measurements, or thermal radiation measurements often provides the input d a t a in reconstructing a two-dimensional object. In each case, these measurements represent available i n formation associated w i t h an otherwise unspecified object. T h i s complex moment d a t a potentially provides enough information to allow the complete or partial reconstruction of the original polygon, P [Dav64, D a v 7 7 , S B 8 6 , M V K W 9 5 , G M V 9 9 ] . 1.2 Previous Work For years, mathematicians and physicists have studied the relationship between shape and moment [ST43]. T h e moments of a region are the integrals of the powers of the independent variables over that region. 1 T h e kth harmonic moment of a 2-dimensional polygon P is given by [ G M V 9 9 ] : (1.1) In early work, D a v i s showed t h a t given only its complex moments up to the third order, the positions of a l l vertices of a triangle w i t h i n the Cartesian plane can be successfully reconstructed [Dav64]. T h u s , any three-vertex polygon can be recon- structed from its complex moments. D a v i s 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\,.. in the Cartesian zi,.. .,z n plane. but independent .,z n designate the vertices of a polygon P Then we can find constants a\,..., of f, such that for all f analytic a n depending upon in the closure of P: (1.2) T h i s formula allowed M i l a n f a r et al. [ M V K W 9 5 ] t o generalize D a v i s ' result and show how a finite number of complex moments of P can be used effectively to reconstruct the vertices of P. U s i n g their method, given complex moments for a polygon P w i t h i n the Cartesian plane, one may reconstruct the positions of the vertices of P. Given sufficient additional information about the interconnection of vertices w i t h i n P, such as convexity, one may reconstruct P itself. F o r n vertices, there are n(n — l ) / 2 possible edges. T h u s , 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, G o l u b et al. [ G M V 9 9 ] address some of the formidable numerical difficulties associated w i t h this reconstruction. In addition, they demonstrate that partial information concerning a polygon's edges can also be derived from a 2 F i g u r e 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. T h i s further development not only allows the reproduction of original vertex positions, but also provides edge orientation constraints between vertices of P (see example in figure 1.2). A Figure 1.2: G i v e n the same four vertex positions along w i t h 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 C a r t e sian plane, for every v € V, we may derive two angles, <f>\ and fa, each allowing in-edges at angles fa m o d 7r and fa mod n, and out-edges at angles fa mod 7r + ^ and fa mod TT + f [ G M V 9 9 ] . T h i s 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 specified 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 C h a p t e r 4) reconstruction from moments is l i m i t e d , independent of any reconstruction approach. In cases involving ambiguity, differentiating between possible reconstructed solutions requires additional information, aside from the input complex moments. H a v i n g applied this initial phase of the solution, the reconstruction problem remains far from being solved. T h e numerical methods provide positions for vertices of P and partial information about potential bounding edges of P, expressed in terms of geometric constraints. W e examine the problem of constructing polygonal regions consistent w i t h this information. For many non-convex polygons, this latter phase of the reconstruction process becomes quite convoluted. T h e problem involves i n terconnecting reconstructed vertices with a superset of potential edges and a p p l y i n g constraint propagation along neighbouring vertices in search of a polygonal subset of edges. A l t h o u g h , in practice, the vertex positions and edge constraints may contain error in their specifications, due either to error o r i g i n a t i n g in the moment d a t a or error introduced in the numerical computations, it is of interest to study the reconstruction problem w i t h error-free moment information. A s we shall see, w i t h i n 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. W e examine the problem of reconstructing polygonal regions, or 2-factors, consistent w i t h the derived partial information about vertex positioning and edge orientation. 1.3 Thesis O r g a n i z a t i o n T h e organization of the material in this thesis is as follows. C h a p t e r 1 introduces the polygon reconstruction problem, gives motivation for its examination, and presents a brief discussion of related research. C h a p t e r 2 provides general background and definitions from graph theory, complexity, and polygon reconstruction. Chapter 3 discusses the 2-factor problem along with proofs t h a t restrictions to the 2-factor 4 problem specific to our polygon reconstruction setting are N P - h a r d . C h a p t e r 4 deals with properties of various graphs w i t h respect to solutions to the reconstruction problem and discusses the uniqueness of solutions w i t h i n specific graphs. C h a p t e r 5 explains the various modules of the reconstruction a l g o r i t h m . C h a p t e r 6 examines the behaviour of the algorithm on various classes of graphs and challenges faced by the a l g o r i t h m . C h a p t e r 7 presents a list of potential future research areas which remain open w i t h i n the domain of polygon reconstruction from moments. Finally, C h a p t e r 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 t h a t arise in general graph theory, related complexity theory, c o m m o n problems found in graphtheoretic and classical complexity, and terms that arise in our discussion of polygon reconstruction. F i n a l l y , we formally define the problem of reconstructing the polygon P from its complex moments. 2.1 2.1.1 D e f i n i t i o n of T e r m s General Graph Theory T h e following t e r m s 1 arise in many general graph theory problems. A graph, G = (V,E), is a collection of vertices, V, and edges, E. v € V, is a single point or node in G. A vertex, A n edge, e G E, represents a relationship between two vertices in G. W e 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. we represent e by drawing a s t r a i g h t J 2 2 Graphically, line from u to v. If the edge relation is asym- See the glossary in Appendix A for a complete list of definitions. W i t h i n our domain, all edges are assumed to be straight lines. 6 metric, then G is a directed g r a p h or digraph, uv and vu are distinct possible edges between vertices v and u. G i v e n graphs G = (V, E) and H = ( V , E'), i f is a s u b g r a p h 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 c o m i n g 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 m a t r i x , M, M UiV where = true if and only if there exists an edge from vertex u to vertex v. The degree of a vertex v is the t o t a l 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. T h e degree of a graph, G, is defined as the m a x i m u m 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 e m b e d d e d graph. A n y fixed positioning of the vertices of G is described as an e m b e d d i n g of G. 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 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} 1 < i < k — 1, V{Vi i £ E or + C V such t h a t v\ = u, Vk = v, and for all £ E. A connected c o m p o n e n t G " C G is a m a x i m a l simply-connected subgraph of G. There cannot exist vertices v G V and u G V such that uv £ E or vu £ E. vertices, { u i , . . . , U j t } C V, such t h a t V A cycle is a sequence of neighbouring £ 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 w i t h i n an embedded graph G, if there exists a cycle C C G such that v £ C and C encloses v w i t h i n i t . Conversely, v is an exterior vertex, if there does not exist such a cycle C. A graph G = (V, E) is bipartite if there exists a p a r t i t i o n of its vertices, V such that, V\ 7^ 0 , V 7^ (J), V i D V ^ = Q), and every edge viv 2 2 in each p a r t i t i o n , vi £ V\ and v 2 2.1.2 £ V or v% € V and v 2 2 2 = V1UV2, € E has one endpoint € V\. Classical C o m p l e x i t y A s is often the case w i t h the presentation of algorithms in theoretical computer science, the classes of problems P and N P find themselves present w i t h i n our d o m a i n . G a r e y and Johnson [GJ79, page 27] formally define the class P as follows: P = { L : there is a polynomial Turing machine program time M for deterministic which L = Lm} Informally, the class P unites all problems that have deterministic p o l y n o m i a l time algorithmic solutions. T h a t is, their solutions can be found deterministically in time proportional to some p o l y n o m i a l function in terms of the input size of the problem. Similarly, G a r e y and Johnson [GJ79, page 31] formally define the class N P as follows: NP = { L : there is a polynomial Turing machine program time M for nondeterministic which L = Lm} Informally, the class N P unites all problems t h a t have nondeterministic polynomial-time algorithmic solutions. B y these definitions, P C N P . T h u s , we 8 require a distinction between those problems that have known polynomial-time deterministic solutions and those that do not. To compare the difficulty of two decision problems, we use a r e d u c t i o n function, R, which allows us to transform one problem to another. P a p a d i m i t r i o u writes: T h a 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. W e 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] If we can show a polynomial-time 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. W e 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 p o l y n o m i a l time, then p is also N P - h a r d . T h i s 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 p o l y n o m i a l time. T h u s , problem q is "at least as complex" as problem p. Therefore, N P - h a r d n e s s is a lower bound of complexity in a hierarchy of problems for which no deterministic polynomial-time algorithmic solution is k n o w n . 2.1.3 G r a p h T h e o r e t i c and C o m p l e x i t y P r o b l e m s T h e following problems have been studied extensively in classical graph theory and complexity. These problems will be relevant in our examination of complexity issues w i t h respect to the polygon reconstruction from moments problem. A s we will see in C h a p t e r 3, our reconstruction problem is very closely related to the problem of finding an n-factor w i t h i n a graph. Lovasz and P l u m m e r write, 9 "a spanning subgraph regular of degree n is called an rc-factor." [LP86, page xxx] N-FACTOR 3 is solvable in p o l y n o m i a l time [LP86, G J 7 9 ] . 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. T h e problem of finding an unconstrained 2-factor in a general graph G is polynomial-time solvable [LP86, G J 7 9 ] . Closely related to the 2-factor is the H a m i l t o n i a n cycle. Lovasz and P l u m m e r define, "a cycle which includes every point of a graph G is called a H a m i l t o n cycle of G . " [ L P 8 6 , page xxx] T h e problem H A M I L T O N I A N CIRCUIT is N P - h a r d [GJ79]. A matching is an n-factor of degree 1. E v e r y vertex is met by exactly one edge. T h e problem of finding a m a t c h i n g in a general graph G is polynomial-time solvable [GJ79]. W i t h i n our reductions, we will refer to 3-dimensional matching. G a r e y and Johnson explain 3-dimensional matching as follows: T h e 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 p r o b l e m " : G i v e n n unmarried men and n unmarried women, along with a list of all male-female pairs who would be willing to m a r r y 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 correspond to three different sexes, and each triple in M corresponds to a 3-way marriage t h a t would be acceptable to all three participants. T r a ditionalists will be pleased to note that, whereas 3 D M is N P - c o m p l e t e , the o r d i n a r y marriage problem can be solved in p o l y n o m i a l time. [ G J 7 9 , page 50] A n o t h e r family of problems that will be of interest is S A T . P a p a d i m i t r i o u 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: G i v e n a Boolean expression <j> in conjunctive n o r m a l 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]. G a r e y and Johnson write, "the 3 - S A T I S F I A B I L I T Y problem F o r m a l descriptions of problems in complexity theory are traditionally given an identifier composed of a few brief descriptive words written in capital letters. 3 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 - S A T is also N P - c o m p l e t e . 2 - S A T restricts instances to two literals per clause. T h i s tighter restriction on the problem makes 2 - S A T solvable in p o l y n o m i a l time [GJ79]. 2.1.4 Polygon Reconstruction Problem T h e following definitions are specific to our discussion of moment-based polygon reconstruction. G i v e n a graph G — (V,E), each edge. at every vertex v E V, we assign a single colour to W e say G is an edge-bicoloured graph. T h i s colouring is local; the colour at the head and tail of an edge may differ. W i t h i n our d o m a i n , a vertex may only have two different colours of edges; we refer to these locally as red and b l u e . 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 m o m e n t - d e r i v e d edge-bicoloured graph. T h e angular constraints on potential edges, 4>\ and (j>2, impose an orthogonality between edges of similar colour. T h u s , under a geometric interpretation of these constraints, edges of similar colour at a given vertex to belong to a c o m m o n framework or axis. E a c h vertex has two such local axes with edges w i t h i n an axis lying orthogonal to each other. W e refer to a global framework whenever frameworks of c o m m o n colour across all vertices in the graph lie within the same orthogonal axis. T h e red-degree of a vertex v is the t o t a l number of red edges incident upon We 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. 4 11 v. Similarly, the blue-degree of v is the t o t a l 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. subgraph of G w i t h the property t h a t every v £ V If H = ( V , E') is a spanning is happy, then i f is a solution subgraph of G. W e describe the state of H as global happiness. Under the edge constraints o f the reconstruction, a vertex v that is part of a solution may be in one of two vertex states: r e d - i n , blue-out ( R I B O ) or blue-in, redout ( B I R O ) . T h i s state directly corresponds to edge c o m m i t m e n t s . A n edge e exists in one of three edge states: undecided, c o m m i t t e d , or d r o p p e d . Whenever an edge is selected as being part of a p a r t i a l solution, we say that we c o m m i t to that edge. W e refer to this decision as an edge c o m m i t m e n t . 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 Models Used and P r o b l e m Overview T h e basis of all models we study will be t h a t 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>\ m o d ix 12 and 4>2 mod TT, and out-edges at angles <j>i mod k + | and 02 mod 7r + | [GMV99]. These restrictions have the following simple geometric interpretation. E a c h vertex has two independent axes assigned to it: a blue and a red axis. E a c h axis specifies two in-directions and two out-directions such that in-directions and out-directions within the axis are orthogonal (see F i g u r e 2.1). Figure 2.1: local blue and red axes for potential edges at a vertex 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 w i t h one of the axes specified at each of u and v. We will colour the head and tail of e w i t h the colour of its associated axis. For example, say we have a graph G\ w i t h four vertices, v\,..., v , and each vertex 4 F i g u r e 2.2: axes for potential edges 13 has red and blue axes given as in figure 2.2. T h e axes and their dotted extensions represent allowable edge directions. Whenever the out-direction from vertex u aligns w i t h the in-direction at another vertex v., we have an edge uv. F i g u r e 2.3 displays the actual edge set E\ t h a t corresponds to this particular graph. F i g u r e 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. T h u s 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 c o m m i t m e n t to a single in-edge having some colour and a single out-edge of the opposite colour. Obviously, commitment at the head of an edge implies c o m m i t m e n t at the t a i l and vice-versa. For example, figure 2.4 displays a graph G2 = ( V , E ) 2 2 for which we wish to find a globally-happy directed 2-factor. Every vertex v £ V2 is valid. Several v, however, are unhappy. H 2 = (V ', E' ) is a spanning subgraph of G . 2 2 both valid and happy. Furthermore, H 2 2 represents a 2-factor of G 2 1 1 Every v £ V is 2 for which every F i g u r e 2.4: an initial graph G% and a solution subgraph H2 vertex has both in-degree and out-degree one and both red-degree and blue-degree one. T h u s , 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 w i t h i n 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. T o facilitate the i n terpretation and presentation of such graphs, we introduce a new colour to allow global colouring, (see figure 2.5b). A A F i g u r e 2.5: odd-length cycle edge colouring 15 Figure 2.6 displays a second example, a more involved graph, G3 = (V 3l i J ) , and a 3 solution subgraph, H3. Unlike the previous graphs, in this case, edge set colouring can be made global only through the use of a t h i r d colour. T h u s , G 3 has three global frameworks. N o t e that locally, however, every vertex v £ V3 has exactly two colours of edges. A g a i n , J f is a globally-happy directed 2-factor of G3. 3 F i g u r e 2.6: an initial 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 d a t a 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 w i t h a focus on the last challeng the problem of finding a globally-happy 2-factor. 17 Chapter 3 Restricted 2-Factors T h e t h i r d phase in the problem of reconstructing a polygon from its complex moments involves searching for a spanning subgraph H C G which is a globally-happy 2-factor. T h u s , we are searching for a 2-factor w i t h 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 general 2-factor. In Section 3.2, we define three restrictions to the 2-factor problem. In Sections 3.3 and 3.4, we show N P - h a r d n e s s 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 . Finally, Section 3.5 summarizes our discussion of restricted 2-factors. T h e unconstrained directed 2-factor problem is polynomial-time solvable [GJ79, L P 8 6 ] . T h e problem of finding a globally-happy 2-factor in polygon reconstruction from moments involves the i m p o s i t i o n of specific restrictions on the unconstrained 2-factor problem. W e identify these additional properties by four specific restrictions to the input graph and output 2-factor: 1. W e may constrain edge choice by requiring global happiness in the resulting 2-factor. 18 2. W e may require that edges of the 2-factor be non-crossing. 3. W e may require that each local blue axis and red axis of the vertices of the input graph be orthogonal. 4. W e may limit 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. W e discuss the relationship between our colour-constrained 2-factor problem and the unconstrained 2-factor problem. W e show N P - h a r d n e s s for specific 2-factor restrictions which embody essential aspects of the globally-happy 2-factor problem. 3.1 2-Factors T h e undirected 2-factor problem involves t a k i n g an undirected graph, G = and finding a spanning subgraph, H = (V',E'), such that every vertex v G V (V,E), has t degree 2 (see figure 3.1). T h e directed 2-factor problem is similar to the undirected F i g u r e 3.1: a graph G and three subgraphs which are 2-factors of G problem but w i t h the additional requirement that every vertex v G V' in the 2-factor must have in-degree 1 and out-degree 1. T h e colour constraints on edges may be restated as a cycle-restricted 2-factor problem by replacing each vertex by a simple component. F i g u r e 3.2 displays two com19 red in red out red in red out blue in blue out blue in blue out F i g u r e 3.2: W e replace vertices w i t h 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 w i t h use of the first component and if 2-cycles are disallowed w i t h use of the second component. B y replacing all vertices w i t h 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 w i t h i n the component would allow two edges of similar colour to be included in a 2-factor. G i v e n any directed graph, G = (V,E), an unconstrained 2-factor may be solved by mapping to a matching problem [LP86]. T o 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 partition V F i g u r e 3.3: v v' and v all out-edge vertices, v", are placed into a partition V". G' = (V U V",E'). and W e call this new graph 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 20 F i g u r e 3.4: m a p p i n g a 2-factor problem to a m a t c h i n g problem an undirected bipartite graph G' such t h a t uv G E O u"v' G E'. T h u s , there exists a perfect matching in G' if and only if there exists a d i rected 2-factor in G. T h e bipartite matching problem is solvable in polynomial-time [LP86]. T h e 2-factor problem, therefore, is also solvable in p o l y n o m i a l - t i m e . Hell et al. show t h a t disallowing /c-cycles makes the undirected 2-factor prob- lem polynomial-time solvable if k < 4 and N P - h a r d if k > 4 [ H K K K 8 8 ] . This polynomial-time solution to finding cycle-restricted undirected 2-factors provides motivating evidence for a possible polynomial-time solution to the globally-happy 2-factor problem. It will follow later that disallowing fc-cycles makes the directed 2-factor problem N P - h a r d for k = 2 and k = 3 (see C o r o l l a r y 3.2). W e go on to show that restricting the 2-factor problem with colour constraints or disallowing crossing edges renders the problem N P - h a r d . T h a t is, we show that imposing properties 1, 2, or 4 render the problem N P - h a r d . 3.2 R e s t r i c t i n g the 2-Factor P r o b l e m T h e unconstrained directed 2-factor problem is polynomial-time solvable [GJ79, L P 8 6 ] . O u r 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 N P - c o m p l e t e since 2 - F A C T O R G P and H A M - C Y C L E G N P - c o m p l e t e [GJ79]. T h e only difference between these two problems is that H A M - C Y C L E requires the existence of a single spanning cycle, namely, a H a m i l t o n i a n cycle, whereas 2 - F A C T O R allows multiple disjoint cycles whose union spans the g r a p h . In addition 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. T h i s corresponds to searching for a 2-factor in which no edges cross. T h u s , 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 (Corollary 3.3) and property 2 (Theorem 3.4) respectively. W e examine the time complexities of each restricted problem. 3.3 3.3.1 E d g e - B i c o l o u r e d D i r e c t e d 2-Factor P r o b l e m Instance and Question W h e n imposing the first property, that the resulting 2-factor respect global-happiness, our problem reduces to the following: EDGE-BICOLOURED DIRECTED I N S T A N C E : Directed graph G = (V,E), 2-FACTOR 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 w i t h 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 w i t h i n 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 w i t h triples of the form T = {(xi,yj, z^)} C X X Y X Z, such that every X{,yj, and z k 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 F i g u r e 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). F i g u r e 3.7: single point component We create a component that connects three points, x , y , and z, into a triple t t (see figure 3.8). Each triple has three pairs of blue edges that link the points to the component. F i g u r e 3.8: W e 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. T h u s , either all three or zero outside blue paths may visit the construction (see figure 3.9). T h i s 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 F i g u r e 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. T h u s , several pairs of blue edges may meet x . t W e 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 x . T h u s , every Xj may only be included in exactly one triple. t 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 corresponds to an edge-bicoloured directed 2-factor in G'. G i v e n 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-time reduction function, fx, such that: x G3DM^ fi(x) GEDGE - BICOLOURED DIRECTED 2-FACTOR Therefore, we have proven: T h e o r e m 3.1 ( K i r k p a t r i c k - D u r o c h e r , 1999) EDGE - BICOLOURED DIRECTED 2-FACTOR G NP-hard Recall that we originally sought to show polynomial-time 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 polynomialtime reduction, f , 2 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 w i t h i n G' transformation * £ EDGE - BICOLOURED DIRECTED O f [x) 2 e fc-CYCLE 2-FACTOR - 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 p o l y n o m i a l 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 p o l y n o m i a l time. T h u s , we have shown: C o r o l l a r y 3.2 ( K i r k p a t r i c k - D u r o c h e r , fc-CYCLE 3.3.3 1999) - 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} 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-Factor In our problem, the last property limits a vertex to at most two in-edges and two out-edges of any colour. T h r o u g h a simple modification of the vertex component, we 26 show t h a t 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-FACTOR 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 2F A C T O R as follows: BOUNDED-DEGREE EDGE-BICOLOURED DIRECTED 2-FACTOR 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 w i t h red-degree 1 and blue-degree 1 at each vertex? G a r e y 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 N P - c o m p l e t e 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). E x a c t l y 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. A g a i n , in an edge-bicoloured directed 2-factor, only a single pair of exterior blue edges may be followed (see figure 3.12). T h e difference, however, is that every 27 vertex now has blue in-degree, blue out-degree, red in-degree, and red out-degree bounded by two. F i g u r e 3.12: edge-bicoloured directed 2-factor on bounded-degree component Following a proof identical to that from T h e o r e m 3.1 except with use of this new bounded-degree component for points a?,-, jfj, or z&, we show that even w i t h a single colour degree bound of two, the problem remains N P - h a r d . T h u s , we have demonstrated: C o r o l l a r y 3.3 ( K i r k p a t r i c k - D u r o c h e r , 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 £ NP-hard F i n a l l y , 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 limit 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 NP-hard. 28 DIRECTED 2-FACTOR remains 3.3.4 Degree Four versus Degree F i v e 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 tightly? 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. T h u s , 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 a d d i t i o n a l edge, one of three cases may arise. W e 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 2factor can be described logically as a simple conjunction of disjunctions. T h e colour constraints on the above examples may be rewritten, respectively, as follows: b A {a © d) b {a © d) A A (b © c) ( c © d) 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 T h e 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 t h a t the problem reduces 1 to 2 - S A T . 2 - S A T is solvable in p o l y n o m i a l time [GJ79]. R e d u c i n g the number of edges to 4, therefore, brings the c o m p l e x i t y down w i t h i n range of p o l y n o m i a l - t i m e solvability. W h e n edges are orthogonal, R e n d l and Woegingner show t h a t reconstruction of sets of orthogonal line segments in the plane from the set of their vertices can also be done in p o l y n o m i a l time [RW93]. T h u s , we have shown that w i t h 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, w i t h 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 . E v e n under extensive 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-FACTOR remains N P - h a r d . 3.4 3.4.1 N o n - C r o s s i n g 2-Factor P r o b l e m Instance and Question If we ignore colour constraints and s i m p l y 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. F o r simplicity, we first examine the problem of finding a non-crossing 2-factor on an undirected graph. W e formalize the problem as follows: NON-CROSSING 2-FACTOR I N S T A N C E : Undirected embedded graph G = (V, E). 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. 1 30 Q U E S T I O N : Does G a d m i t a 2-factor H, none of whose edges intersect except at their endpoints? 3.4.2 N O N - C R O S S I N G 2 - F A C T O R is NP-hard U s i n g 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 W e will present a reduction which is ini- tially undirected but for which every component may be directed without any effect on functionality. T h e 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 e x c l u s i v e - O R w i t h i n a non-crossing 2-factor (see figure 3.15). T h a t is, either edge A or edge B may be A B A B B A B A F i g u r e 3.15: following either edge A or edge B F i g u r e 3.16: X O R component Jansen and Woeginger show that given an undirected graph G whose edges are axisparallel, 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. 2 31 followed, but not b o t h , nor neither, nor some fragment of either. T h e component construction is displayed in figure 3.16. Note that any non-crossing 2-factor w i t h i n this component must find itself in one of two states. E i t h e r 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). F i g u r e 3.17: two states of X O R component in a non-crossing 2-factor F i g u r e 3.18: crossover component We require a second component to eliminate unwanted edge-crossings. In- serting this component does not affect membership of edges w i t h i n 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). N o other combination of edges is possible. For example, it is impossible to visit only the b o t t o m B edge and the top A edge w i t h o u t forcing edges to cross. 32 F i g u r e 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 . L e t S = X U Y U Z. T h e sets S and T form a bipartite graph G (see figure 3.20a). S T S T F i g u r e 3.20: 3-dimensional matching instance and solution in bipartite graph F i n d i n g a 3-dimensional matching amounts to finding a subset of edges of G which meet every vertex in the S partition exactly once and every vertex in the T p a r t i t i o n exactly zero or three times (see figure 3.20b). S T F i g u r e 3.21: stretching G We first stretch G onto diagonals (see figure 3.21). 33 W e replace all crossovers using our crossover component (see figure 3.22). This implies that any 2-factor w i t h i n the graph will be non-crossing. F i g u r e 3.22: eliminate crossovers using crossover component We add a m i r r o r image of the entire graph and connect top vertices to their corresponding neighbours on the b o t t o m . C a l l this graph G' (see figure 3.23). F i g u r e 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 F i g u r e 3.24: connecting triples from T to T" F i g u r e 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 T have the property 1 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'. G i v e n any S and T, a 3- dimensional matching can be found if and only if there exists a non-crossing 2-factor in G'. W e have shown a polynomial-time reduction function, / 3 , such that: x e 3DMo h{x) e NON-CROSSING 2-FACTOR 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 F i g u r e 3.26: full reduction from bipartite S and T to G In our input d o m a i n , graphs are directed. E a c h component w i t h i n this construction may be directed without any alteration to its function (see figure 3.27) F i g u r e 3.27: reduction components w i t h 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 w i t h use of these new directed components, we show t h a t 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 . W e therefore derive the following theorem : T h e o r e m 3.4 ( K i r k p a t r i c k - D u r o c h e r , 1999) DIRECTED NON-CROSSING 2-FACTOR G NP-hard 36 3.5 Summary U s i n g 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 problem. A s demonstrated, this particular problem seems to lie very close to the boundary between P and N P - h a r d . T h e actual problem, encompassing colour constrains, non-crossing constraints, degree-bounds, and geometric orthogonal constraints remains to be shown to be p o l y n o m i a l - t i m e solvable or N P - h a r d . 37 Chapter 4 Uniqueness of Moment Sets T h e 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. C e r t a i n 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 Commitment Propagation 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, redout ( B I R O ) (see figure 4.1). T h u s , 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. W e 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 i n d i n g a 2-factor solution involves c o m m i t t i n g to edges w i t h i n the graph. Whenever a vertex v c o m m i t s 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. F o r example, if e is a c o m m i t t e d red i n 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 RIBO. A c o m m i t m e n t applies both to the head and tail of an edge. Thus, whenever we c o m m i t 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 c o m m i t to uv, then the vertex state of v becomes B I R O (see figure 4.2). Similarly, d r o p p i n g 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 H 2 C Hi is a spanning subgraph of Hi and all edges E C Hi - may be removed from Hi by constraint propagation, then we say H 2 graph of Hi. If no further edges may be removed from H tion, then H 2 2 is m a x i m a l l y reduced. 39 H 2 is a reduced by constraint propaga- A s we will see in Section 5.4, such c o m m i t m e n t propagation forms the basis of our algorithm for finding solutions w i t h i n a graph. There exist graphs, however, for which simple c o m m i t m e n t propagation cannot be used to simplify a graph towards a solution subgraph. subgraph. Some of these graphs embody more than a single solution C o m m i t m e n t propagation alone will 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. U n d e r ordinary conditions, there would be no reason to expect such a graph to arise naturally; non-unique solutions graphs occur infrequently and require specific contrived constructions. T h e i 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 w i t h i n edge-bicoloured graphs. A solution to an edge-coloured graph G = (V, E) is a globally-happy 2-factor spanning subgraph, H C G. F o r two distinct solutions to exist, there must exist two such subgraphs, Hi and H , such that Hi ^ H . 2 2 vertex set, V, we must have that Ei ^ Since Hi and H 2 have a c o m m o n E. 2 We distinguish between three types of graphs w i t h non-unique solutions w i t h i n a hierarchical classification. G r a p h s with distinct state solutions contain exactly two solutions, Hi and H , such that for any vertex v £ V, v is in vertex 2 state R I B O in Hi and B I R O in H 2 or vice-versa. G r a p h s w i t h distinct edge solu- tions may contain two or more solutions, Hi,..., e appears in at most one solution Hi,..., Hk, such that for any edge e £ E, Hk- T h a t is, the intersection of the edge sets of any two solution subgraphs is empty. G r a p h s w i t h c o m m o n 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 solutions, there must be some v € V whose vertex-state is unchanged. T h e solutions of such a graph cannot be distinct state solutions. W e further classify solutions by e x a m i n i n g connectedness (simple or multiple) and edge crossing (crossing or noncrossing). W i t h respect to common edge solutions, M i l a n f a r et al. state the following proposition [ M V K W 9 5 ] : P r o p o s i t i o n 4.1 ( M i l a n f a r et a l . , 1995) in the Cartesian generated plane. by connecting Let P and P' be simply connected, these vertices least one side in common, and aj(P') Consider n distinct points, in two distinct then for some 1 < j < are, respectively, ways. 21,22, nondegenerate, •••,2 n-gons If P and P' have at n, aj(P) aj(P'), where a,j(P) defined by: II, h"(z) dx dy = f I h"(z) J JP' dx dy = ^2a {P)h(z ) ] J P with h denoting any analytic function J2a (P')h(z ) J j = J 1 in the closure of P U P'. P r o p o s i t i o n 4.1 claims that if P and P' are two distinct polygons which have at least one edge in c o m m o n , then P and P' cannot be solutions to the same set of input constraints, otherwise P and P' must include degenerate vertices. C o n t r a r y to this proposition, in this section, we will demonstrate the existence of such c o m m o n edge solutions, where all vertices are nondegenerate. W e first look at the octagon graph (see figure 4.3). T h e octagon is the simplest graph (least number of vertices) we have found which contains two simply-connected ambiguous solutions. F i g u r e 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 n Figure 4.3: ambiguous solutions within the octagon graph simply-connected but the second obviously involves edge-crossing. Note that at every 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. T h u s , 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 A n o t h e r simple graph which contains non-unique solutions is the hexagonal six-point star (see figure 4.5). T h i s 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. S t r a k h o v and B r o d s k y present a very cleverly constructed graph [SB86] which contains two solutions respecting simple-connectedness and non-crossing edge properties (see figure 4.6). T h e S t r a k h o v - B r o d s k y graph is created by merging two Figure 4.6: the S t r a k h o v - B r o d s k y 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 multiple simply-connected, non-crossing solutions. T h e interesting behaviour in many ambiguous graphs derives from having outer vertices which allow convexity within two vertex states (see figure 4.4). T h e two solutions to the S t r a k h o v - B r o d s k y graph are displayed in figure 4.7. T h e y are s y m m e t r i c a l reflections of each other along a central vertical axis. W i t h i n all examples presented up to this point, no two solutions share a 43 F i g u r e 4.7: ambiguous solutions w i t h i n the S t r a k h o v - B r o d s k y graph F i g u r e 4.8: ambiguous solutions within the modified S t r a k h o v - B r o d s k y graph [SB86] common edge unless the c o m m o n edge belongs to a static disconnected component (as is the case w i t h the outer hexagon in the six-point star in figures 4.5c and 4.5d). Strakhov and B r o d s k y also present a graph which contains two solutions sharing two c o m m o n edges [SB86]. T h i s graph may be constructed by simple modification to the regular S t r a k h o v - B r o d s k y graph (see figure 4.8). Note the two triangles in figure 4.8b. T h e i r inside edge is also present in the first solution in figure 4.8a. G i v e n any graph which contains ambiguous solutions Hi and H , 2 one may easily add constant edges by selecting any edge e, e 6 Hi, e £ H , and inserting three additional vertices to form a triangle along the edge (see 2 figure 4.9a). W e call this new graph G' and its solutions H[ and Since e £ Hi, H' . 2 in solution H[, we do not include edge c (see figure 4.9b). Conversely, since e ^ H , in solution H' , we include edge c but not edges a or e (see 2 2 44 F i g u r e 4.9: general pattern w i t h i n common-edge solutions figure 4.9c). T h e resulting graph, G " , is such that, in both solutions, edges b and d remain constant. T h e modified S t r a k h o v - B r o d s k y graph has two non-crossing solutions, but one of the solutions is composed of disconnected components. T h u s 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 S t r a k h o v - B r o d s k y graph such t h a t all solutions share common edges along the exterior of the graph and all solutions remain simply-connected and non-crossing. Figure 4.10: extended S t r a k h o v - B r o d s k y graph Let SBi and SB 2 be the two solutions to the regular S t r a k h o v - B r o d s k y graph. We choose two edges e\ and e along the perimeter of the graph such that e\ £ 2 e\ £ SB , 2 e 2 e £ SBi, 2 and e £ SB . 2 2 SBi, W e add a series of static edges to connect e\ and (see figure 4.10). These edges are such that only one of the two ends will connect to the graph within a solution. T h u s , both solutions solutions, SB[ and SB , 2 45 remain simply- F i g u r e 4.11: four instances of the extended S t r a k h o v - B r o d s k y graph connected and non-crossing. T h e difference between the regular and the extended S t r a k h o v - B r o d s k y graphs is that SB[ and SB' 2 share c o m m o n edges. Significantly, we can join two such extended S t r a k h o v - B r o d s k y graphs together by l i n k i n g their c o m m o n edges to create a graph which has four simply-connected, non-crossing solutions (see figure 4.11). F i g u r e 4.12: multiple connected instances of ambiguous graphs One quickly observes that we may join k such extended S t r a k h o v - B r o d s k y graphs together to form a graph which embeds 2 k simply-connected, non-crossing solutions (see figure 4.12). T h u s , the number of solutions may be exponential w i t h respect to the size of the graph. Therefore, we have shown: T h e o r e m 4.2 ( D u r o c h e r - K i r k p a t r i c k , distinct simple polygons in the Cartesian such that all 2 n polygons have identical 1999) plane, For any n 6 Z , + each composed of 30n + 4 moment sets. 46 there exist 2 n vertices, T h u s , 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. O u r various extensions to the S t r a k h o v - B r o d s k y graph demonstrate the existence of multiple c o m m o n 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 constraints. 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 number of such solutions may be exponential w i t h 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 C h a p t e r 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 solutions. W e now discuss algorithms that solve the problem of reconstructing the original polygon from which a set of moments were measured. 5.1 Reconstruction Process Overview Recall the three-phase subdivision of moment-based polygon reconstruction: 1. Given complex moment d a t a 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 edgecoloured 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 to implement phases two 1 and three of the reconstruction process. T h e algorithm modules form a pipeline and E a c h 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 deJ 48 may be broken down as follows: 1. r e c o n s 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 positions along w i t h blue and red axis angles for 2 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 G 2 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 G 2 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 F i g u r e 5.1: pipelined reconstruction modules These four phases form the basic assembly line to transform moment d a t a into reconstructed polygons (figure 5.1). A s we will discuss, this solution process scribed in his manuscript [GMV99]. A l l other modules were written by S. Durocher and D . Kirkpatrick. For examples that include significant numerical error and cause inaccurate position and angle input data to b u i l d G r a p h , we fix the output of recons to provide perfect information (see Section 6.1). 2 49 may require e x t r a m a n i p u l a t i o n and flow-control, and thus, we will describe three additional modules: 5. t r e e S e a r c h works recursively down a search tree towards solutions whenever constraint propagation alone w i t h i n module commit fails to reduce G3 to a final solution (Section 5.5). 6. f ragmentSearch is used whenever the input d o m a i n includes imperfect d a t a . P a r t i a l fragmented solutions are researched as opposed to complete 2-factors (Section 5.6). 7. momentDiff allows for extremely noisy d a t a to be reconstructed piecewise through re-iteration of the recons module on differences of moments (Section 5.7). 5.2 B u i l d G r a p h : B u i l d i n g the I n i t i a l G r a p h After having passed through the initial phase of reconstruction, we are presented w i t h a set of vertices, V. E a c h 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. W e use the following definition for vertex compatibility: Definition 5.1 Given two vertex positions, out-edge angle 7 ' at v, and a deviation u and v, an in-edge angle /3' at u, an 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 c o m p a t i b l e whenever they have corre3 3 T h e compatibility relation is asymmetric: C(u, v) 50 C(v,u), for u,v £ V. sponding in-edge and out-edge angles which lie w i t h i n a window of tolerance. Fig- ure 5.2a displays two such vertices w i t h 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 .. •>'JU v ""••'t> v F i g u r e 5.2: determining whether vertex v is compatible w i t h 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 w i t h v, we include the edge uv in G\. F i g u r e 5.3: a parallelogram and its associated input position and axis d a t a For example, figure 5.3a displays a parallelogram. T h e vertex position and axis angle d a t a which would provide input to b u i l d G r a p h are displayed in fig- 51 ure 5.3b. T h e 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 T h u s , 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 : S i m p l i f y i n g the G r a p h T h e initial 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. W e 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 »0« C O O M O »0 F i g u r e 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 will construct the high-degree graph G i displayed in figure 5.5b. W e use e d g e E l i m to reduce the graph t o the desired subgraph G 2 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 t h a t 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. T h u s , v will 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 t h a n four edges per colour axis. O u r heuristic keeps only the shortest edge and eliminates a l l others along a c o m m o n direction with similar orientation and colour (see figure 5.6). F i g u r e 5.6: edge elimination heuristic Obviously, depending upon the tolerance angle a in b u i l d G r a p h , there will be instances when the heuristic eliminates the true edge and retains an invalid edge. T h i s usually results in an equivalent solution. F o r example, figure 5.7a displays the 53 -*0 o- a b c J F i g u r e 5.7: two different edge eliminations which produce equivalent results initial 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. T h e original polygon may have been one of two possible shapes: a s i m p l y connected closed polygon (figure 5.7b) or a multiple-component rectangle w i t h 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. T h e two figures differ only by the additional t h i n strip which links the top and b o t t o m to form a closed hole. T h e area of this thin strip is quite small w i t h respect to the rest of the polygon, some small e which depends upon the tolerance a and the scale of the figure. Reconstructing 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. T h u s , we ap- ply our heuristic and eliminate all but the shortest edge along a c o m m o n direction w i t h similar orientation and colour to produce the second graph, G . 2 In our exam- p l e / t h i s results in figure 5.7b being passed along to the next phase of reconstruction. T h u s , 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 outdegree w i t h i n 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 : Colour Constraint Propagation After having passed through r e c o n s . b u i l d G r a p h , and e d g e E l i m , we are given an input graph G 2 whose vertices have bounded degree and whose edges fall locally into two geometrically-restricted axes as displayed in figure 5.8. F i g u r e 5.8: axes at a vertex from the graph We now begin the final phase of the reconstruction. moment-derived edge-bicoloured input graph G 2 G 2 Here, we are given a w i t h i n which we wish to find a globally-happy 2-factor. T h e first method employed to achieve this end is through the use of the commit module. T h e c o m m i t m e n t algorithm performs a recursive walk through the graph, visiting each vertex no more than a constant number of t i m e s . 4 T h e 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). T h i s case only arises when the original input graph, G'2, does not contain a solution subgraph. 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 | ) . 4 55 3. G*3 may be in a state where colour constraints can no longer be propagated. The a l g o r i t h m requires two or more recursive search branches (see Section 5.5). A s mentioned, the essence of the c o m m i t m e n t algorithm involves colour constraint propagation. T h e constraints arise from our requirement for global- happiness. F o r 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 will either be c o m m i t t e d edges or they will have been dropped. T h u s , we work towards a solution by altering the state of an undecided edge to being c o m m i t t e d or dropped. W e do so by applying two types of rules: local elimination rules and new c o m m i t m e n t rules. L o c a l elimination rules follow a basic format: at a vertex v, we check for vacancies 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 . T h u s , 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 F i g u r e 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 c o m m i t t e d edges and, hence, we develop new commitment rules. Recall that a c o m m i t t e d edge is one which belongs to the final solution subgraph. Whenever a vertex has only one edge of a given colour or a given orientation, 56 then that edge must be contained w i t h i n a solution and, therefore, we c o m m i t to the edge. E d g e - c o m m i t m e n t affects the remaining edges of vertices at both endpoints of the newly-committed edge. Figure 5.10: new c o m m i t m e n t rule 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 c o m m i t t e d edge. C o m m i t m e n t at the head of an edge implies commitment at the t a i l . T h u s , vertex v inherits a c o m m i t t e d blue out-edge. T h i s new c o m m i t m e n t 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. W henever the application of a rule involves T 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 c o m m i t t e d and, consequently, should be revisited. Since the application of a single rule at a vertex can trigger changes at many neighbouring vertices, c o m m i t m e n t propagation occurs quite rapidly in a highly reactive recursive fashion. W e visit vertices one at a time. U p o n visiting 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 still need to be 57 visited, we m a i n t a i n a set of active vertices. T h u s , our algorithm falls into place. Initially, we know nothing about vertices and we must visit every vertex at least once. Therefore, our initial active set is simply the set of all vertices. W e may visit any vertex in the s e t and apply the colour rules 5 to it. 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 d a t a after a p p l y i n g commit Let us trace a simple example through the four phases of reconstruction while paying special attention to c o m m i t m e n t propagation. T h e original shape from which moment d a t a has been obtained is an eight-vertex, simply-connected closed figure (figure 5.11a). G i v e n 16 moment measurements for this shape, r e c o n s returns a set of 8 vertex positions along w i t h a blue and red axis orientation for each (figure 5.11b). 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." 5 58 Figure 5.12: graphs G\ and G 2 produced by b u i l d G r a p h and e d g e E l i m , respectively G i v e n these 8 positions and 8 pairs of axes, b u i l d G r a p h produces the initial graph, G\ (figure 5.12a). T h i s graph includes edges for every possible pair of compatible 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, G 2 (figure 5.12b). Figure 5.13: constraint propagation 59 T h e graph G 2 is passed to commit where c o m m i t m e n t propagation begins. Initially, the active set, A, is the set of all vertices: A = {a, b, e, d,e, / , § , k}. We begin by visiting 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 . W e 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 c o m m i t 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 c o m m i t 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: C o n s t r a i n t propagation continues on to produce a solution graph G3. We now visit vertex / . Vertex / has a c o m m i t t e d red out-edge, fg. / also has another red out-edge, fc, which is undecided. Vertex Obviously, edge ft can be dropped (see figure 5.14a). Vertex / now only has two edges remaining, and we commit to each of these. W e update A: A' = (A - {/}) U {e} = {a, b, c, e, h}. 60 T h e r e m a i n i n g edges form a globally-happy 2-factor (see figure 5.14b). T h e algorithm still requires visits t o each o f {a, b, c, e, h} t o c o m m i t to their edges. N o t e that a happy vertex whose edges are both c o m m i t t e d cannot be added t o the active set again since the state o f its edges may no longer be altered. T h e a l g o r i t h m terminates and the graph G3 is returned as a s o l u t i o n . For most graphs which embed a single unique solution, commit successfully finds and returns the solution subgraph. Figures 5.15 a n d 5.16 display more complex examples which were solved by c o m m i t . In each figure, the first plot is the graph G 2 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—*o cm—o 0—*o o—*o cm—0 0—*o CM—O 0—*o 1 c—*o cm—0 0*—0 cm—o -f' cm—o -*o*—o O—WO o*—0 cm—0 0—0 O—fcO m Cm—O A *-? 0*—0 cm—o F i g u r e 5.15: complex rectilinear polygon reconstructed by commit figure 5.16a, only six vertices have initial edge configurations which may propagate constraints. A l l other 30 vertices require constraints t o be passed to t h e m . T h e module commit searches for a globally-happy 2-factor through the propagation of colour constraints. T h i s technique often succeeds in finding a solution. Sometimes, however, constraint propagation alone comes to a halt before having found a solution. F o r these cases, we require a recursive search tree. 61 ^4 Figure 5.16: set of 9 boxes reconstructed by commit 5.5 TreeSearch: R e c u r s i v e Search Trees W h e n the subgraph G'3 produced by commit is not a globally-happy 2-factor, constraints 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. G i v e n 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 , where edge e is dropped in G 3 3 and c o m m i t t e d in G . W e then 3 proceed to solve the two separate problems of searching for solutions w i t h i n G 3 and G ' using commit. 3 A g a i n , we have the same three possible outcomes at the end of both of these branches. E i t h e r , 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. W e 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, w i t h lower degree vertices being more reactive in general. T h i s basic heuristic for choosing edges works efficiently on most examples examined. Even if only m i n i m a l c o m m i t m e n t propagation results from a decision, each vertex will only have been visited a constant number of times, and successive branching will eventually lead to a solution. Let us examine the search tree for a graph which contains three ambiguous so- lutions. B r a n c h i n g within the search tree is displayed in figure 5.18. F i g u r e 5.17: ambiguous input graph G\ and two subgraphs, G' and 2 G. 2 After having passed through recons, b u i l d G r a p h , and edgeElim, we enter the module t r e e S e a r c h . T h e input graph, G\, is displayed in figure 5.17a. G\ is the hexagonal six-point star which we saw in Section 4.2. t r e e S e a r c h begins by calling commit w i t h Gi as input (step 1). E v e r y vertex v € G\ has at least one in-edge and one out-edge of each colour. T h u s , an initial pass of commit fails to simplify G\ and outputs an unaltered graph, G 2 = G\. A t this point, t r e e S e a r c h creates two modifications of G 2 vertices along the exterior of G 2 (step 2). A l l have lowest degree, in this case, 4. T h u s , we select 63 an undecided edge at one of these vertices, say edge e. G is set to be G 2 edge e dropped (figure 5.17b) and G is set to be G 2 2 2 except w i t h except w i t h edge e c o m m i t t e d (figure 5.17c). input graph Gi commit j 0 maximally reduced graph G2 3 ^ v 4 Gicommit r j ^ t rJe e S e a r c[h Jcommit t ^ G.< 0 2-factor solution//; 0 maximally reduced graph Gi r j | treeSearch J commit J 0 2-factor solution jr 1 G." - J commit I) 0 2-factor solution//J Figure 5.18: recursive search tree descent We now branch for the first time. T w o parallel recursive calls are made to commit, one on input graph G' (step 3) and the other on G 2 2 (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 standstill: the m a x i m a l l y reduced subgraph, G3 C G, 2 displayed in figure 5.19b. t r e e S e a r c h creates two modifications of G3: G' and G3 (step 5). A g a i n , we z look for a vertex of lowest degree greater than two. E v e r y exterior vertex has degree 64 Figure 5.19: solution Hi and m a x i m a l l y 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' is set to be G 3 edge / dropped (figure 5.20a) and G' ' is set to be G 3 3 3 except w i t h except w i t h edge / committed (figure 5.20b). We now branch for the second time. A g a i n , two parallel recursive calls are made to commit, one on input graph G 3 (step 6) and the other on G'3 (step 7). After propagating constraints, these two calls emerge w i t h solutions H 2 H, 3 and 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 F i g u r e 5.21: two solutions H 2 and H 3 three is as good a solution as the other. W h e n discerning between ambiguous possibilities in edgeElim, alternative cases had solutions which differed in area only by some small e. Non-unique solutions produced by t r e e S e a r c h , however, may differ greatly i n area, connectedness and edge-crossing. In our example, solution H\ is a simply-connected, non-crossing polygon, solution H is a multiple-component, 2 crossing polygon, and solution H 3 is a multiple-component, non-crossing polygon. Whenever constraint propagation alone fails t o provide a solution, t r e e S e a r c h successfully reconstructs all solutions, regardless of the complexity of the input graph. For example, figure 5.22 displays the graphs Gi and G 2 which are produced by b u i l d G r a p h and edgeElim, respectively, when given the input vertices for a twoconnected, extended S t r a k h o v - B r o d s k y graph. In this case, t r e e S e a r c h produced the actual output plots displayed i n figure 4.11 (see Section 4.2). T h u s , through recursive calls to commit down a search tree, our t r e e S e a r c h module allows the reconstruction of all solutions contained w i t h i n a subgraph. 66 after buildgraph after edgeelim F i g u r e 5.22: b u i l d G r a p h and edgeElim results for two-connected S t r a k h o v - B r o d s k y extension 5.6 Fragment Search: F i n d i n g Fragments of Solutions T h e reconstruction modules commit and t r e e S e a r c h run under the assumption that all required information lies embedded w i t h i n the input graph. T h a t is, all edges of a solution 2-factor must be edges of the graph G . 2 provide a less than perfect input graph for G . 2 Imperfect data, however, may 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. W e have investigated two such techniques which were implemented in fragmentSearch and momentDiff. W e begin by discussing module f ragmentSearch. Instead of looking for a globally-happy 2-factor, we search for fragments of happy 67 vertices. T h u s , we seek portions of a solution which, when pieced together with missing edges, form potential reconstruction solutions. Unlike solutions found by commit and t r e e S e a r c h , solutions constructed by f ragmentSearch are of a more subjective nature; t r e e S e a r c h will return every globally-happy 2-factor contained w i t h i n a graph, whereas f ragmentSearch must heuristically decide between possible collections of fragments contained w i t h i n a graph, and return those which might form pieces of a solution. Furthermore, in f ragmentSearch, eliminating an edge e m a y cause a vertex v to become invalid. Thus, unlike commit and t r e e S e a r c h , in which ordering of events does not affect constraint propagation i n the solution process, solutions produced by f ragmentSearch are subject t o the ordering of elimination and c o m m i t m e n t actions. A n input graph to f ragmentSearch may include invalid vertices, that is, vertices which may be w i t h o u t a given colour or orientation of edge (see figure 5.23). In this new a l g o r i t h m , constraint propagation must account for such vertices. Thus, Figure 5.23: two invalid vertices propagation is altered as follows: whenever we visit a vertex v from the active set A, we apply c o m m i t m e n t and elimination rules as before, but only i f v is valid. U p o n visiting an invalid vertex u, we simply remove u from A and continue. W e retain our search tree approach and branch recursively on two calls to commit until the output graph embeds a collection of happy vertex fragments. W h e n c o m p a r i n g two solutions, we use a simple heuristic and compare the lengths of the longest fragment contained within each. If these have equal length, 6 6 Here, "length" refers to the number of vertices in a fragment and not to geometric lengt h. 63 we compare the next longest, and so o n . Obviously, the solution w i t h 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. F o r example, figure 5.24a displays the reconstructed vertices of an E shaped polygon produced by r e c o n s . N o t e 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 G 2 Neither Gi nor G 2 produced by b u i l d G r a p h and e d g e E l i m respectively. contain a globally-happy 2-factor. T h u s , as expected, when passed through commit and t r e e S e a r c h , no solution is found. T h e f r a g m e n t S e a r c h module, however, finds the fragment displayed in figure 5.24d. U p o n observation, we note t h a t G 2 does not embed any longer fragment. T h u s , given our limited input constraints, f r a g m e n t S e a r c h provides a valid partial solution. initial vertex reconstruction from moments X X 8 8 ++_++ after buiidgraph after edgeelim 00,00 CO CO 8 8 ++ ++ + + 8 8 ++, F i g u r e 5.24: 9-edge fragment found in 12-vertex polygon 69 segment found Whenever the input d o m a i n includes imperfections in the d a t a such that a globally-happy 2-factor is not contained w i t h i n the input graph, we may use f r a g m e n t S e a r c h to reconstruct p a r t i a l solution composed of fragments of happy vertices. Such a partial solution often provides a close a p p r o x i m a t i o n to the original polygon and allows the reconstruction to overcome some degree of error arising from numerical c o m p u t a t i o n or input data. 5.7 M o m e n t D i f f : C o m p o n e n t R e c o n s t r u c t i o n by Difference of M o m e n t s T h e p a r t i a l solution provided by f r a g m e n t S e a r c h identifies portions of a graph in which d a t a is more likely to be accurate. A long reconstructed fragment usually follows a string of vertices whose position and angle d a t a closely m a t c h those of the original polygon. L o n g fragments of accurate vertices can be used along w i t h the original moment input d a t a in subsequent iterations of the reconstruction pipeline to obtain better position and angle approximations for inaccurate vertices. G i v e n a polygon, P , and its moment vector, mp, for any subdivision of P into nonintersecting subcomponents, P i , . . . , P ^ , the sum of the moment vectors of the subcomponents of P is exactly equal to the moment vector of P: mp = mp +.. . + 1 mp . k For example, figures 5.25a and 5.25b display a simple polygon P and a two-piece decomposition of P into P\ and P . 2 If we separately measure n moments for P , n moments for F i , and n moments for P , we find that mp = mp 2 l + mp . 2 M o d u l e momentDif f implements the following a l g o r i t h m . U s i n g a difference of moments, we can reconstruct a polygon, one component at a time. T h e reunion of all reconstructed components forms the complete original reconstructed polygon. G i v e n a set of moments, m p , which correspond to an n vertex polygon F , n > 4, we use r e c o n s , 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, 70 G\. F i g u r e 5.25: s u m of subcomponent moments: mp — mp + mp l 2 A call to f ragmentSearch on input G\ returns a p a r t i a l solution composed of edge fragments. L e t us assume the longest fragment, 5 , has k vertices, S\,...,Sk, 3 < k < n. W e form a new polygon P i , by t a k i n g the endpoints S\ and Sk, and creating a new edge siSfc. P o l y g o n 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 w i t h respect to corresponding vertices w i t h i n the original polygon P , then P i is a subcomponent of P . W e find the moments of P i , mp , l mp — and a new difference of moments, m a = mp . 1 We call recons again w i t h this new difference of moments, m a , as input. T h e output vertices are r u n through b u i l d G r a p h and edgeElim to produce a reconstructed graph G*2 of n — k + 2 vertices which correspond to the component P2 = P — P\- W e search w i t h i n G2 using fragmentSearch for another longest partial solution. If G2 contains a globally-happy 2-factor, then we have successfully reconstructed P2 and we m a y assemble P by joining P i and P . If not, then we take 2 the longest fragment w i t h i n G2, and repeat this process recursively. Let us examine a simple example. A s we saw i n Section 5.6, the recon- struction of a 12-vertex, E-shaped polygon P includes some inaccurate vertex positions and angles which initially prevent a complete solution from being discovered, f ragmentSearch successfully finds the 9-edge fragment S\ displayed in figure 5.26a. 71 Iri c o o c A F i g u r e 5.26: reconstruction by component decomposition M o d u l e m o m e n t D i f f takes the closure of Si (figure 5.26b) finds its moments, and the difference of moments, m& = mp — i: ms . 1 U p o n a second pass through the pipeline, the reconstruction of the four-vertex polygon P rns forms displayed in figure 5.26c. If we adopt the premise that 2 clockwise fragments of closed edges bound areas of positive density and counterclockwise fragments of closed edges bound areas of negative density, then we find that the union of P i and P forms an exact reconstruction of P (figure 5.26d). 2 We must note, however, that at this point in time, our experiments using differences of moments as a method for polygon reconstruction have produced successful results only under very controlled conditions. E r r o r s in moment differences produce "ghost" vertices which correspond to the differing regions between the perimeters of the two polygons (see Section 7.4). These additional vertices easily fool the algor i t h m when searching for the second polygon, P . 2 For imperfect input domains, we successfully reconstruct partial solutions by searching 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 T h e process of reconstructing a polygon from its complex moments involves a multiple-phase pipeline of algorithms. G i v e n a set of moments, we build vertex positions and potential edge angles using module r e c o n s . W e 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 . W e simplify G\ into a moment-derived edge-bicoloured graph G 2 using an edge elimination heuristic in module e d g e E l i m . G i v e n that the input d o m a i n 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 i n f o r m a t i o n , modules fragmentSearch and m o m e n t D i f f provide partial solutions and attempts at piecewise reconstructions of complete solutions. Together, these algorithms present various approaches to the polygon reconstruction from moments problem. 73 Chapter 6 From Models to Real Data U p o n being presented real moment data, the reconstruction of vertex positions and local angle axes often acquires some inaccuracies from numerical c o m p u t a t i o n error and imperfect input moment d a t a . C e r t a i n 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 d a t a (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 I n p u t D a t a W i t h i n the reconstruction process, four decreasing levels of control may be imposed on input d a t a 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 recons. V a r y i n g the level of control allows us to test the functionality of the re- construction algorithms under various environments ranging from ideal to realistic conditions. W e differentiate between the degrees of control as follows: 74 1. exact vertex and angle information: W e may fix b o t h position and angle d a t a such that information passed onto buildGraph is exact. 2. exact vertex locations and exact moments: W e may fix only vertex positions and reconstruct potential angle axes in recons using this positioning. T h u s , half of the input d a t a passed onto buildGraph is exact and half is reconstructed. 3. exact m o m e n t data: W e may use perfect moment d a t a as i n p u t to recons and reconstruct both position and angle d a t a to be passed onto buildGraph. 4. a c t u a l moment data: W e may acquire actual moment d a t a , containing measurement imperfections, to be used as input to recons. P o s i t i o n and angle d a t a 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 d a t a . 6.2 E x a m i n i n g the B e h a v i o u r o f V a r i o u s G r a p h s B y nature of the quadrature formula, vertices w i t h i n a polygon t h a t are co-linear or interior often trigger numerical c o m p u t a t i o n 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. F o r example, figure 6.1 displays the vertex positions and potential edge angles reconstructed by module recons for two graphs, G\ and G , where G\ is a six-point star and G 2 2 is an eight-point star. In each plot, the original polygon whose complex moments provided input to module recons is displayed in solid lines overtop the reconstructed d a t a . B o t h G\ and G 2 contain sets of four co-linear vertices as well as many interior 75 initial vertex reconstruction from moments F i g u r e 6.1: position and angle reconstructions for two graphs G\ and G 2 vertices. Reconstructed vertex positions and potential angles are reconstructed accurately in graph G\. In graph G , however, only exterior vertices are reconstructed 2 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. T h u s , when working specifically w i t h the graph-theoretic aspects of the reconstructions algorithm on graphs such as G\, we fix the output from module r e c o n s and input perfect information to module b u i l d G r a p h . W h e n e x a m i n i n g error- recovery abilities and partial solution search heuristics w i t h i n the reconstruction algorithms, we input actual position and angle information from module r e c o n s , allowing inaccuracy to enter the input d o m a i n . C e r t a i n families of shapes demonstrate interesting behaviour. T h e success of re- construction directly depends upon the relative location from which moments are measured within the plane. 76 F i g u r e 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. W h e n centered at (2,2), however, the reconstruction becomes indecipherable. If we center a regular polygon P at the origin, the reconstruction remains perfect. U p o n a t t e m p t i n g to reconstruct a subcomponent of this same P, however, we again notice the i n t r o d u c t i o n of inaccuracies. F i g u r e 6.3a displays the reconstructed positions of the upper right 12 vertices of a regular 48-sided polygon centered at the origin. F i g u r e 6.3b displays the results after processing by b u i l d G r a p h and fig- F i g u r e 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 o u t l y i n g vertex lies out of the displayed d o m a i n . Interestingly, a polygon including all 48 vertices can be reconstructed accurately, whereas as subset of size 12 cannot. T h u s , subsets of sets of accurately reconstructible vertices are not necessarily accurately reconstructible themselves. 6.3 D e a l i n g w i t h N u m e r i c a l E r r o r i n the R e c o n s t r u c tion Polygons t h a t present challenges to the reconstruction require us to consider alternative approaches to reconstruct their vertex positioning and potential angles. E x p e r i m e n t a t i o n demonstrates that reconstruction inaccuracies may be reduced by increasing the number of moment measurements input to module recons. F o r 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. U n d e r s a m p l i n g provides an idea as to the general positioning of the polygon w i t h i n 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 <!• •* F i g u r e 6.4: varying the number of sample points: n = 8, 12, and 16 78 4. angles still contain significant inaccuracies. F i n a l l y , in figure 6.4c, module r e c o n s is given 16 complex moments and produces 16 vertex positions and axis angles. T h u s , 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 . F o r example, figure 6.5 displays an extended E-shaped polygon, P . Here, we display the vertex reconstruction for increasing numbers of moments: n — 16, 24, 32, and 64. 2 Note t h a t e x t r a reconstructed vertices lie close to a circle centered at origin. * * -2 0 2 * * * St # ss % * 2 p» •» St >*P * » dp » F i g u r e 6.5: varying the number of sample points: n = 16, 24, 32, and 64 79 6.4 Summary G i v e n complex moments, reconstruction of vertices sometimes includes inaccuracies. F o r some vertices, these imperfections remain recoverable and may be dealt w i t h from w i t h i n the d o m a i n of graph theory. In these instances, inaccurate vertices are left unaltered and error tolerance w i t h i n the reconstruction algorithms allows successful reconstruction. O t h e r vertices, however, acquire significant position or angle error. F o r these cases, we require alternative methods of reconstructing position and angle, since we are provided too little information from the initial reconstruction. 80 Chapter 7 Further Research Various partially explored and even completely unexplored questions branch out from the problems analyzed w i t h i n 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. W e may consider the reconstruction of polygons w i t h i n 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). • U p o n encountering inaccurate information, iteration of the initial reconstruction formula could be used to create additional constraints using p a r t i a l results. T h i s added input information might provide more accurate position and angle d a t a (Section 7.3). • B l o c k reconstruction by differences of moments as currently implemented only allows very limited functionality. Greater error-tolerance w i t h i n module momentDif f could provide improved reconstruction of inaccurate input d a t a (Section 7.4). • C u r r e n t theorems about N P - h a r d restricted 2-factors could be used to show 81 N P - h a r d n e s s for the problem of searching for a globally-happy 2-factor w i t h i n a moment-derived edge-bicoloured graph (Section 7.5). In this chapter, we briefly visit each of these potential research areas and describe the m o t i v a t i n g ideas from which they derive. 7.1 Variable Internal Density A l l models examined include polygons of constant density. A r e a w i t h i n the polygon is assumed to be bipartite, such that, for any point a; in the C a r t e s i a n 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. E x p l o r i n g reconstruction issues among such polygons might provide insight into additional realistic and application-oriented examples. F i g u r e 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 . A l t e r n a t i v e l y , densities may be assumed to be real positive values, as in example B . F i n a l l y , reversed loops w i t h i n a polygon may be interpreted as negative densities, as in example C . F i g u r e 7.1: two shapes with multiple densities T h u s , issues of varying or non-uniform density remain to be considered within polygon reconstruction from moments. 82 7.2 C e r t i f y i n g Solutions G i v e n two solutions, A and B, how do we measure which is a better solution? W i t h i n module f r a g m e n t S e a r c h , we discussed a heuristic that chose the solution w i t h the longer fragment of happy vertices. Certainly, many other comparisons are possible. H o w do we differentiate between levels of validity? F o r example, figure 7.2 displays four solutions discovered by module f r a g m e n t S e a r c h on a = .157T and moments for an E-shaped polygon. W h i c h is the better solution? F i g u r e 7.2: differentiating between p a r t i a l solutions One may hypothetically derive some measure of closeness by comparing moments 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. T h u s , comparative certification of solutions, remains a mostly unexplored d o m a i n w i t h i n polygon reconstruction from moments. 83 7.3 Iterative R e c o n s t r u c t i o n Reiteration of the quadrature f o r m u l a on a greater number of constraints may provide a reconstruction that more closely resembles the original polygon. After an initial run of recons, upon encountering inaccurate information, vertices deemed accurate or inaccurate could be tagged and divided into corresponding partitions. Positions of vertices from the p a r t i t i o n of accurate vertices could then be used as additional constraints in a subsequent iteration of the reconstruction formula. T h e motivation being t h a t additional information in a reiteration on a greater number of constraints may provide more accurate reconstruction for those vertices initially in the inaccurate p a r t i t i o n . 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 F i g u r e 7.3: identifying accurate and inaccurate vertices into two partitions: accurate (white) and inaccurate (black). T h e positions and edge angles of vertices in the accurate partition are then used as additional input constraints w i t h i n a subsequent iteration of recons. T h i s second call to recons could hypothetically provide a better reconstruction for the vertices of the inaccurate partition. 84 7.4 I m p r o v i n g E r r o r Tolerance using Differences o f M o ments Instead of a t t e m p t i n g to improve the original vertex and angle positions reconstructed by recons, we may a t t e m p t to improve error tolerance w i t h i n module momentDiff. C u r r e n t l y , differences between moments of the original polygon and subcomponents of the reconstructed polygon result i n noisy errors w i t h i n moments causing ghost vertices. For example, figure 7.4a displays a polygon Q. L e t us assume f ragmentSearch successfully finds the partial solution fragment in figure 7.4b. M o d u l e momentDiff takes the closure of this fragment, Qi, and searches for a reconstruction m a t c h i n g the difference of moments. Note that the position of vertex v is inaccurate. In a t t e m p t i n g to reconstruct the six-vertex polygon Q , shadows of the difference Qs 2 (figure 7.4c) cause error in the reconstruction. Hypothetically, ghost polygonal re- IA A F i g u r e 7.4: error in differences of moments gions such as Q 3 m a y 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, Q 2 and Q 3 (figure 7.4d). 85 7.5 A d d i t i o n a l C o m p l e x i t y Issues In C h a p t e r 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 . T h e actual problem involves finding a globally-happy 2-factor w i t h i n a moment-derived edge-bicoloured g r a p h . O u r proof demonstrated that searching for a globally-happy 2-factor w i t h i n a bounded-degree edge-bicoloured graph is N P - h a r d . T h u s , we ask ourselves the question, can we incorporate geometric orthogonality constraints into a reduction to prove that searching for a globally-happy 2-factor w i t h i n a moment-derived edgebicoloured graph is also N P - h a r d ? Modifications 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 . A l t e r n a t i v e l y , new components imposing orthogonality of frameworks may allow a m a p p i n g from E D G E - B I C O L O U R E D 2 - F A C T O R . Perhaps the exploitation of planarity, connectedness, and orthogonality w i t h i n solutions might provide assistance in designing a reduction. These complexity questions remain unanswered and invite future e x a m i n a t i o n from the complexity theoreticians. 7.6 Summary M a n y avenues within polygon reconstruction from moments, i n c l u d i n g v a r y i n g density, solution validation, iterative reconstruction, error tolerance w i t h i n differences of moments, and problem of complexity, remain open and unexplored. These potential research domains present very tangible and genuine possibilities for i m p r o v i n g the success of polygon reconstruction algorithms and for deepening our understanding of the nature of this problem. 86 Chapter 8 Conclusion Previous work by D a v i s [Dav64, Dav77] and Strakhov and B r o d s k y [SB86], along w i t h recent work by M i l a n f a r et al. [ M V K W 9 5 ] and G o l u b et al. [ G M V 9 9 ] has inspired interest in the problems associated w i t h the reconstruction of polygonal shapes from moments. T h r o u g h their techniques, one may gather potential position and vector information about the vertices which lie on the perimeter of a polygon being reconstructed. T h i s preliminary acquisition process finds an a p p r o x i m a t i o n to the Cartesian coordinates of the vertices along w i t h two axes of possible in-edges and out-edges for each vertex. E a c h 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 visiting one out-edge and one in-edge from each axis. O u r work consists of reconstructing the polygon based on this input information. W e develop and analyze reconstruction algorithms w i t h respect to their dependence on numerical error and spatial variation, their time complexity, and their ability to recognize ambiguous solutions when more than one exists. 87 T h e main results of this thesis include: • W e have proved t h a t some restricted 2-factor problems relating to the reconstruction problem are N P - h a r d . These include: - EDGE-BICOLOURED DIRECTED 2-FACTOR - & - 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 EDGE-BICOLOURED DIRECTED 2-FACTOR - NON-CROSSING - DIRECTED NON-CROSSING 2-FACTOR 2-FACTOR • W e have examined the occurrence and properties of non-unique solutions within graphs. W e have proven that there exist graphs that embed an ex- ponential number of distinct, simply-connected, non-crossing solutions w i t h 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 a l g o r i t h m , we have implemented a tree-based search routine which finds all possible solutions contained w i t h i n a graph. • W e have examined techniques to find p a r t i a l solutions w i t h i n domains of i m perfect or inaccurate input data. These include searching for segments of solutions, iterative differences of moments, and use of additional input moments. • W e 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 t a k i n g vertex positions 88 and potential angles, and reconstructing the final solutions. A s demonstrated w i t h i n this thesis, polygon reconstruction involves a multiple-phase geometric and graphtheoretic reconstruction process. Issues of non-uniqueness, ambiguity, position and angle inaccuracy, and erroneous input d a t a must be considered when searching for solutions. A l g o r i t h m s and theorems presented here address these issues and present methods at deriving complete and partial solutions. These advances, along w i t h other current developments, have revealed many unexplored branches w i t h i n polygon reconstruction from moments, in t u r n p r o v i d i n g avenues for potential future research. 89 Bibliography [CLR92] T . H . G o r m e n , C . E . Leiserson, and R . L . Rivest. Introduction to P . J . D a v i s . Triangle formulas in the complex plane. Mathematics of Algorithms. [Dav64] M c G r a w - H i l l , N e w Y o r k , 1992. Computation, [Dav77] 18:569-577, 1964. P . J . D a v i s . Plane regions determined by complex moments. of Approximation [DK99] Journal Theory, 19:148-153, 1977. S. D u r o c h e r and D . K i r k p a t r i c k . Resctricted 2-factor problems arising from moment-based polygon reconstruction. In Workshop tional Graph Theory and Combinatorics, on Computa- pages 55-57. Pacific Institute for the M a t h e m a t i c a l Sciences, 1999. [GJ79] M . R . G a r e y and D . S. J o h n s o n . Computers and Intractability. W. H. Freeman and C o m p a n y , N e w Y o r k , 1979. [C;MV99] G . H . G o l u b , P . M i l a n f a r , and J . V a r a h . A stable numerical method for inverting shape from moments. SIAM Journal of Scientific Computa- tion, to appear, 1999. [HKKK88] P . Hell, D . K i r k p a t r i c k , J . K r a t o c h v f l , and I. K H z . O n restricted twofactors. SIAM Journal of Discrete 90 Mathematics, l ( 4 ) : 4 7 2 - 4 8 4 , 1988. [JW93] K . Jansen and G . J . Woeginger. T h e complexity of detecting cross- ingfree configurations in the plane. BIT, 33(4):580-595, 1993. [LP86] L . Lovasz and M . D . P l u m m e r . M a t c h i n g theory. In Annals Mathematics, of Discrete volume 29. N o r t h - H o l l a n d M a t h e m a t i c s Studies, 1986. [ M V K W 9 5 ] P . M i l a n f a r , G . C . Verghese, W . C . K a r l , and A . S. W i l l s k y . Recons t r u c t i n g polygons from moments w i t h connections to array processing. IEEE [0'R88] Transactions J . O'Rourke. on Signal Processing, 43:432-443, 1995. Uniqueness of orthogonal connect-the-dots. Toussaint, editor, Computational Morphology, In G . T . pages 97-104. Elsevier Science Publishers B . V . ( N o r t h - H o l l a n d ) , 1988. [Pap94] C . H . P a p a d i m i t r i o u . Computational Complexity. Addison-Wesley, N e w Y o r k , 1994. [RW93] F . R e n d l and G . Woeginger. Reconstructing sets of orthogonal line segments in the plane. Discrete [SB86] Mathematics, 119:167-174, 1993. V . S t r a k h o v and M . B r o d s k y . O n the uniqueness of the inverse loga r i t h m i c potential problem. SIAM Journal of Applied Mathematics, 46:324-344, 1986. [ST43] J . Shohat and J . T a m a r k i n . T h e problem of moments. In Surveys, volume 1. W a v e r l y Press, B a l t i m o r e , 1943. 91 Mathematical Appendix A Glossary of Terms A.l General Graph Theory g r a p h 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 . W e say edge uv £ E if and only if there exist vertices u, v £ V such that u and u 1 are related under some relation R C V X V. Graphically, 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. s u b g r a p h G i v e n 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 c o m i n g from a vertex u into vertex u is called an inedge 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 m a t r i x W e may represent vertex adjacency through a boolean adjacency m a t r i x , M, where M u<v = true if and only if there exists an edge from vertex u to vertex v. degree T h e degree of a vertex v is the t o t a l number of edges incident upon Similarly, the in-degree of v is the number of in-edges at v and the degree of v is the number of out-edges at v. v. out- T h e degree of a graph, G , is defined as the m a x i m u m degree amongst all vertices v £ V. e m b e d d e d g r a p h If we are given a pre-determined fixed positioning for the vertices of a graph G , then we say that G is an embedded g r a p h . A n y fixed positioning of the vertices of G is described as an e m b e d d i n g 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. s i m p l y - c o n n e c t e d A graph G is simply-connected if for any two vertices u, v £ V we can find some sequence of vertices {v\,... Vk = v, and for all 1 < i < k — 1, £ E ,Vk} C V such that v\ = u, or i>;+ii>; £ E. connected component A connected component G' C G is a m a x i m a l simplyconnected 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} ViVi+i £ E for all 1 < i < k — 1 and VkV\ C V, such that £ E. A fc-cycle is a cycle of length k. interior, exterior A vertex v is an interior vertex w i t h i n 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 p a r t i t i o n of its vertices, •V = V i U V , such that, V i + Q), V 2 2 ^ © , Vi n V 2 = © , and every edge Viv G f? has one endpoint in each p a r t i t i o n , v\ G V i and u 2 and v 2 2 € V 2 or U i G V 2 G Vi. 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 Classical Complexity P G a r e y and Johnson [GJ79, page 27] formally define the class P as follows: P = { L : there is a polynomial Turing machine program time M for deterministic which L = Lm} Informally, P unites all problems which have deterministic polynomial-time algorithmic solutions. T h a t is, their solutions can be found deterministically in time p r o p o r t i o n a l to some p o l y n o m i a l function in terms of the input size of the problem. N P G a r e y and Johnson [GJ79, page 31] formally define the class N P as follows: NP = { L : there is a polynomial Turing machine program time M for nondeterministic which L = Lm} Informally, the class N P unites all problems which have nondeterministic polynomial-time algorithmic solutions. reduction function T o compare the difficulty of two decision problems, we make use of a reduction function, R, which allows us to reduce one problem to another. P a p a d i m i t r i o u writes: 94 T h a t is, we shall be prepared to say t h a t 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-time reduction from some problem q to a problem p, then we say p is at least as hard as q. W e 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 p o l y n o m i a l time, then we say p is also N P - h a r d . T h i s 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 p o l y n o m i a l time. T h u s , problem q is "at least as complex" as problem p. Therefore, N P - h a r d n e s s is a lower bound of complexity in a hierarchy of problems for which no deterministic p o l y n o m i a l - t i m e algorithmic solution is known. A.3 G r a p h Theoretic and C o m p l e x i t y Problems n-factor Lovasz and P l u m m e r 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 p o l y n o m i a l time [ L P 8 6 , G J 7 9 ] . 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 in-edge and one out-edge. has exactly one T h e problem finding an unconstrained 2-factor in a general graph G is polynomial-time solvable [LP86, G J 7 9 ] . matching A m a t c h i n g is an n-factor of degree 1. E v e r y vertex is met by exactly one 95 edge. T h e problem of finding a matching in a general graph G is p o l y n o m i a l time solvable [GJ79]. H a m i l t o n i a n cycle Lovasz and P l u m m e r define, "a cycle which includes every point of a graph G is called a H a m i l t o n cycle of G . " [ L P 8 6 ] T h e 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 m a t c h i n g G a r e y 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. T h e 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 p r o b l e m " : G i v e n n unmarried men and n unmarried women, along w i t h a list of all male-female pairs who would be willing 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 correspond to three different sexes, and each triple in M corresponds to a 8-way marriage t h a t would be acceptable to all three participants. Traditionalists will be pleased to note that, whereas 3 D M is N P - c o m p l e t e , the ordinary marriage problem can be solved in polynomial time. [GJ79, page 50] SAT P a p a d i m i t r i o u 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: G i v e n 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 G a r e y and Johnson write, "the 3 - S A T I S F I A B I L I T Y problem 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 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. T h i s tighter restriction on the problem makes 2 - S A T solvable in polynomial time [GJ79]. 96 A.4 Polygon Reconstruction Problem p o l y g o n r e c o n s t r u c t i o n f r o m c o m p l e x m o m e n t s G i v e n a finite set of complex moments measured from a two-dimensional polygon P embedded w i t h i n the plane, we a t t e m p t to reconstruct the original shape of P. m o m e n t T h e moments of a region are the integrals of the powers of the independent variables over that region. T h e 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. T h i s colouring is local; the colour at the head and t a i l of an edge may differ. W e sometimes refer to global colouring in a graph, in which case, head and tail colours match for all edges e G E. W i t h i n our d o m a i n , a vertex may only have two different colours of edges; we often refer to these locally as red and blue. F o r 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 G i v e n 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. m o m e n t - d e r i v e d edge-bicoloured G i v e n 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 T h e angular constraints on potential edges, fa and fa, impose an or- thogonality between edges of similar colour. T h u s , under a geometric interpret a t i o n of these constraints, edges of similar colour at a given vertex to belong to a c o m m o n framework or axis. Generally, edges w i t h i n an axis lie orthogonal to each other. W e refer to a global framework whenever frameworks of c o m m o n colour across all vertices in the graph lie w i t h i n the same orthogonal axis. c o m m i t m e n t Whenever an edge is selected as being part of a partial solution, we say that we c o m m i t to that edge. W e 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: r e d - i n , blue-out ( R I B O ) or blue-in, red-out ( B I R O ) . T h i s state directly corresponds to edge c o m m i t m e n t s . edge state A n edge e exists in one of three states: undecided, c o m m i t t e d 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 T h e red-degree of a vertex v is the t o t a l number of red edges incident upon v. Similarly, the blue-degree of v is the t o t a l 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, u n h a p p y 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. If v is not happy, then we say v is unhappy. 98 fragment A fragment is any sequence of vertices v%,..., for all 1 < A; < i — 1 and and every vertex U 2 , . . . , u; such that VkVk+i £ -E\ 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. W e 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. W e refer to these restrictions as colour constraints. constraint propagation C o n s t r a i n t propagation occurs whenever the constraints at a vertex v affect the constraints at a neighbouring vertex u. r e d u c t i o n If graph H 2 Hi — H 2 C H\ is a spanning subgraph of H\ and all edges E C may be removed from i i i by constraint propagation, then we say H is a reduced graph of H\. 2 If no further edges may be removed from H constraint propagation, then H 2 2 A.5 by is m a x i m a l l y reduced. Reconstruction Algorithm Modules recons M o d u l e r e c o n s 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. b u i l d G r a p h M o d u l e buildGraph takes n vertex positions along w i t h blue and red axis angles for each and builds a dense edge-bicoloured graph G\ which includes edges for any m a t c h i n g combination of in-edge and out-edge angles (Section 5.2). 99 e d g e E l i m M o d u l e 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 similar colour and direction which are geometrically opposite to each other (Section 5.3). c o m m i t M o d u l e commit works recursively on G 2 using colour constraint propa- gation to produce a solution subgraph G'3 for which no further constraint propagation is possible (Section 5.4). treeSearch M o d u l e treeSearch works recursively down a search tree towards solutions whenever constraint propagation alone w i t h i n module commit fails to reduce G 3 to a final solution (Section 5.5). fragmentSearch M o d u l e f ragmentSearch is used whenever the input d o m a i n i n cludes imperfect data. P a r t i a l fragmented solutions are researched as opposed to complete 2-factors (Section 5.6). m o m e n t D i f f M o d u l e momentDiff allows for extremely noisy d a t a to be reconstructed 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 |
File Format | 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 |
Graduation Date | 1999-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | 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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051485/manifest