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+O1/2) and (1 - O(ε))-1