Manifolds in R3
Christian Scheffer
This talk will present two topics to do with manifolds in R3
Simplified Medial-Axis Approximation with Guarantees
We present an algorithm that approximates the medial axis of a smooth
manifold in R3 which is given by a sufficiently dense point
sample. The resulting, non-discrete approximation converges to the medial
axis as the sampling density approaches infinity, and we establish a
homotopy between the canonical parameterizations of both structures. While
there is no sub- quadratic upper bound on the output complexity of
previous algorithms for non-discrete medial axis approximation, the
output of our algorithm is guaranteed to be of linear size. Moreover,
the algorithm is (arguably) simpler than previous approaches, and its
practical efficiency is demonstrated by an experimental evaluation.
Approximating Geodesic Distances on 2-Manifolds in R3
We present an algorithm for approximating geodesic distances on 2-manifolds in R3. Our algorithm works on an ε-sample of the underlying manifold and computes approximate geodesic distances between all pairs of points in this sample. The approximation error is multiplicative and depends on the density of the sample. For an ε-sample S, the algorithm has a near-optimal running time of O(n2 log(n)) and approximates the geodesic distances up to a factor of 1+O(ε1/2) and (1 - O(ε))-1