UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Graph-theoretic and geometric algorithms associated with moment-based polygon reconstruction Durocher, Stéphane 1999

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items