No description available.

Thesis (Ph. D.)--University of Chicago, Dept. of Statistics, August 2003. / Includes bibliographical references. Also available on the Internet.

published_or_final_version / abstract / toc / Computer Science / Master / Master of Philosophy

published_or_final_version / Computer Science / Master / Master of Philosophy

Reconstruction results attempt to rebuild polygons from visibility information. Reconstruction of a general polygon from its visibility graph is still open and only known to be in PSPACE; thus additional information, such as the ordering of the edges around nodes that corresponds to the order of the visibilities around vertices is frequently added. The first section of this thesis extracts, in o(E) time, the Hamiltonian cycle that corresponds to the boundary of the polygon from the polygon's ordered visibility graph. Also, it converts an unordered visibility graph and Hamiltonian cycle to the ordered visibility graph for that polygon in O(E) time. The secod, and major result is an algorithm to reconstruct an arthogonal polygon that is consistent with the Hamiltonian cylce and visibility stabs of the sides of an unknown polygon. The algorithm uses O(nlogn) time, assuming there are no collinear sides, and )(n2) time otherwise. / vii, 78 leaves ; 28 cm.

No description available.

No description available.

Let <a1,..., a m | wn> be a presentation of a group G, where w is freely and cyclically reduced and n ≥ 2 is maximal. We define a system of codimension-1 subspaces in the universal cover, and invoke a construction essentially due to Sageev to define an action of G on a CAT(0) cube complex. By proving easily formulated geometric properties of the codimension-1 subspaces we show that when n ≥ 4 the action is proper and cocompact, and that the cube complex is finite dimensional and locally finite. We also prove partial results when n = 2 or n = 3. It is also shown that the subgroups of G generated by non-empty proper subsets of {a1, a 2,..., am} embed by isometries into the whole group.

We produce a nonpositively curved square complex, X, containing exactly four squares. Its universal cover, X̃ ≅ T4 x T 4, is isomorphic to the product of two 4-valent trees. The group, pi1X, is a lattice in Aut (X̃) but π1X is not virtually a nontrivial product of free groups. There is no such example with fewer than four squares. The main ingredient in our analysis is that X̃ contains an "anti-torus" which is a certain aperiodically tiled plane.

If G is a group acting on a set Ω, and α, β ∈ Ω, the directed graph whose vertex set is Ω and whose edge set is the orbit (α, β)^G is called an orbital graph of G. These graphs have many uses in permutation group theory. A graph Γ is said to be primitive if its automorphism group acts primitively on its vertex set, and is said to have connectivity one if there is a vertex α such that the graph Γ\{α} is not connected. A half-line in Γ is a one-way infinite path in Γ. The ends of a locally finite graph Γ are equivalence classes on the set of half-lines: two half-lines lie in the same end if there exist infinitely many disjoint paths between them. A complete characterisation of the primitive undirected graphs with connectivity one is already known. We give a complete characterisation in the directed case. This enables us to show that if G is a primitive permutation group with a locally finite orbital graph with more than one end, then G has a connectivity-one orbital graph Γ, and that this graph is essentially unique. Through the application of this result we are able to determine both the structure of G, and its action on the end space of Γ. If α ∈ Ω, the orbits of the stabiliser G_α are called the α-suborbits of G. The size of an α-suborbit is called a subdegree. If all subdegrees of an infinite primitive group G are finite, Adeleke and Neumann claim one may enumerate them in a non-decreasing sequence (m_r). They conjecture that the growth of the sequence (m_r) is extremal when G acts distance transitively on a locally finite graph; that is, for all natural numbers m the stabiliser in G of any vertex α permutes the vertices lying at distance m from α transitively. They also conjecture that for any primitive group G possessing a finite self-paired suborbit of size m there might exist a number c which perhaps depends upon G, perhaps only on m, such that m_r ≤ c(m-2)^r-1. We show their questions are poorly posed, as there exist primitive groups possessing at least two distinct subdegrees, each occurring infinitely often. The subdegrees of such groups cannot be enumerated as claimed. We give a revised definition of subdegree enumeration and growth, and show that under these new definitions their conjecture is true for groups exhibiting exponential subdegree growth above a prescribed bound.