The Star Unfolding from a Geodesic Curve

computational geometry;unfolding;shortest paths;Computer Science

Kiazyk, Stephen

University of Waterloo

关键词: computational geometry;    unfolding;    shortest paths;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/8935/3/Kiazyk_Stephen.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

An unfolding of a polyhedron P is obtained by `cutting;; the surface of P in such a way that it can be flattened into the plane into a single polygon. For most practical and theoretic applications, it is desirable for an algorithm to produce an unfolding which is simple, that is, non-overlapping. Currently, two methods for unfolding which guarantee non-overlap for convex polyhedra are known, the source unfolding, and the star}unfolding.Both methods involve computing shortest paths from a single source point on the polyhedron;;s surface. In this thesis, we attempt to prove non-overlap of a variant called the geodesic star unfolding. This unfolding, much like the star unfolding, is computed by cutting shortest paths from each vertex to λ, a geodesic curve on the surface of a convex polyhedron P, and also cutting λ itself. Non-overlap of this case was conjectured by Demaine and Lubiw (2011). We are unsuccessful in completely proving non-overlap, though we present a number of partial results, and discuss some areas for future study. We first develop a new proof for non-overlap of the star unfolding from a point. The original proof of non-overlap was given by Aronov and O;;Rourke (2009). This new proof uses a partitioning of the unfolding around the ridge tree.Each edge of the ridge tree serves as a base edge to a pair of congruent triangles; in this way, the whole unfolding is decomposed into these pairs which are called kites. We prove non-overlap by showing that pairwise, no two kites in the unfolding overlap each other, by a method which bounds the surface angle of the source images to either side of any path through the ridge tree.In addition to its simplicity compared to the previous proof, this new method easily generalizes to prove non-overlap for some cases of the star unfolding from geodesic curves. Specifically, we show non-overlap for two classes of geodesic curves, geodesic loops, and fully-extended S-shaped geodesics, by showing that the surface angle of the source images in those two cases are bounded.We also investigate a class of curves called fully-extended C-shaped geodesics for which the proof cannot hold directly.We show some specific cases where we are able to create a supplementary proof to show non-overlap, though non-overlap for the class as a whole remains unproven.