Polygon reconstruction from visibility information
LillAnne Jackson · Open ULeth Scholarship (OPUS) (University of Lethbridge) · 1996
Reconstruction results attempt, to rebuild polygons from visibility information.Rmmstruction 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 cdg<!s around nodes that, corresponds to the order of the visibilities around vertices is frequently added.The first, section of this thesis extracts, in 0(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 0(E) time.The second, and major result is an algorithm to reconstruct an orthogonal poly gon that is consistent with the Hamiltonian cycle and visibility stabs of the sides of an unknown polygon.The algorithm uses O(nlogn) time, assuming there are no col linear sides, and 0(rr) time otherwise.There are many people who have contributed substantially to this thesis.My appreciation goes out. to every person.My supervisor, Professor Stephen K. Wismat.h, is an excellent teacher and re searcher whose patience, encouragement and motivation were instrumental in com pleting this thesis.The friendship Steve,