ausblenden:
Schlagwörter:
Computer Science, Computational Geometry, cs.CG
Zusammenfassung:
We present an algorithmic framework for producing Delaunay triangulations of
manifolds. The input to the algorithm is a set of sample points together with
coordinate patches indexed by those points. The transition functions between
nearby coordinate patches are required to be bi-Lipschitz with a constant close
to 1. The primary novelty of the framework is that it can accommodate abstract
manifolds that are not presented as submanifolds of Euclidean space. The output
is a manifold simplicial complex that is the Delaunay complex of a perturbed
set of points on the manifold. The guarantee of a manifold output complex
demands no smoothness requirement on the transition functions, beyond the
bi-Lipschitz constraint. In the smooth setting, when the transition functions
are defined by common coordinate charts, such as the exponential map on a
Riemannian manifold, the output manifold is homeomorphic to the original
manifold, when the sampling is sufficiently dense.