Files in this item



application/pdfSurface and Med ... ed by Discrete Samples.pdf (7MB)
(no description provided)PDF


Title:Surface and Medial Axis Topology Through Distance Flows Induced by Discrete Samples
Author(s):Sadri, Bardia
Subject(s):computer science
Abstract:The distance function induced by a surface in R^n is known to carry a great deal of topological information about the surface and its embedding in space. It is an important question, from both theoretical and practical standpoints, whether such information about a surface can be extracted from the distance function induced by a discrete sample of it. Distance functions induced by discrete samples of surfaces and their associated mathematical structures are the main focus of this dissertation. These functions lead to continuous flow maps that turn out to be powerful topological tools. Based on these flow maps we design and analyze a number of simple and natural shape and medial axis reconstruction algorithms for which we can guarantee the topological type of output. We prove that critical points of distance functions induced dense enough (relative) epsilon-samples of surfaces are concentrated around the surface and its medial axis. These two types of critical points can be distinguished from each other algorithmically. This ``separation'' of critical points is crucial to the design and analysis of of the above-mentioned algorithms. Specifically, we present an algorithm for homeomorphic reconstruction of surfaces in 3D. This algorithm generalizes to higher dimensions with a slight change in the type of the provided topological guarantee. We also present an algorithm for medial axis approximation that computes a piece-wise linear core for the given sample. This core is guaranteed to be homotopy equivalent to the medial axis of the shape enclosed by the original surface. We then show that the core can be enhanced by any geometric medial axis approximation scheme without compromising the topological equivalence of the output and the medial axis being approximated. Finally, we present an analysis of Herbert Edelsbrunner's well-known Wrap reconstruction algorithm and show that under relative epsilon-sampling in 3D, the output of Wrap is homotopy equivalent to the original shape.
Issue Date:2006-12
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2006-2789
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-21

This item appears in the following Collection(s)

Item Statistics