Show simple item record

dc.contributor.supervisor Wismath, Stephen
dc.contributor.author Jackson, LillAnne Elaine
dc.contributor.author University of Lethbridge. Faculty of Arts and Science
dc.date.accessioned 2007-04-11T17:42:32Z
dc.date.available 2007-04-11T17:42:32Z
dc.date.issued 1996
dc.identifier.uri https://hdl.handle.net/10133/41
dc.description vii, 78 leaves ; 28 cm. en
dc.description.abstract 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. en
dc.language.iso en_US en
dc.publisher Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 1996 en
dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en
dc.subject Polygons en
dc.subject Graph theory en
dc.subject Dissertations, Academic en
dc.title Polygon reconstruction from visibility information en
dc.type Thesis en
dc.publisher.faculty Arts and Science
dc.publisher.department Department of Mathematics and Computer Science
dc.degree.level Masters


Files in this item

This item appears in the following Collection(s)

Show simple item record