Open Collections

Graph-theoretic and geometric algorithms associated with moment-based polygon reconstruction

University of British Columbia

The problem of reconstructing an unknown polygonal shape P, viewed as a region in the complex plane, from a finite number of its complex moments is motivated by a number of mathematical, computational, and application-oriented considerations. Complex moment information can be derived from such diverse physical processes as tomographic (line integral) measurement, exterior gravitational, or magnetic field measurement, or thermal radiation measurement, associated with an otherwise unspecified object [GMV99, M V K W 9 5 , SB86]. Milanfar et al. [MVKW95], building on earlier work of Davis [Dav64, Dav77], show how a finite number of complex moments of P can be effectively used to reconstruct the vertices of P. If sufficient additional information (for example, convexity or rectilinearity) about P is known, P itself can be reconstructed. Very recently, Golub et al. [GMV99] address some of the formidable numerical difficulties associated with this reconstruction. In addition, they demonstrate that partial information concerning a polygon's edges can also be derived from a finite number of its complex moments, raising the possibility of a more complete and general reconstruction scheme. In general, note that even simply-connected polygonal regions are not uniquely specified by even infinitely many of their complex moments [SB86], thereby precluding a completely general reconstruction scheme. Given vertex positions for the set V of vertices of P in the Cartesian plane and partial information (expressed in terms of geometric constraints) about the edges bounding P, we examine the problem of constructing polygonal regions con sistent with this information. Although in practice, the vertex positions and edge constraints may contain error in their specifications (due either to error originating in the data or introduced in the numerical computations) it is of interest to study the reconstruction problem with error-free moment information. As we shall see, this translates to a constrained directed 2-factor problem in a directed graph G defined on the vertex set V. As observed in [GMV99], the potential edges incident on a vertex are subject to very specific local restrictions. These restrictions have the following simple geometric interpretation. Each vertex has two independent axes assigned to it: a blue and a red axis. Each axis specifies two in-directions and two out-directions such that in-directions and out-directions are orthogonal. A n edge joining vertex u to vertex v belongs to the edge set of G if and only if its direction agrees with one of the axes specified at each of u and v. We will colour the head and tail of each such edge with the colour of its associated axis. A solution to the polygon reconstruction problem is a spanning subgraph H of the resulting directed and edge-bicoloured graph in which every vertex has both in-degree and out-degree one and both red-degree and blue-degree one. Thus, we are looking for a directed 2-factor of G that satisfies some local colour constraints. This thesis addresses graph-theoretic and geometric concerns arising from momentbased polygon reconstruction. We show NP-hardness of various restrictions to the 2-factor problem. We investigate properties of moment sets whose graphs contain non-unique solutions. We develop algorithms to solve the problem of polygon reconstruction given both perfect and imperfect input moment data. Finally, we examine the success of reconstruction on various classes of graphs.

Thesis/Dissertation

application/pdf

2009-06-26

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/9688

Computer Science

University of British Columbia

UBCV

DSpace