Skip to Main content Skip to Navigation
Reports

Delaunay Triangulations of Point Sets in Closed Euclidean d-Manifolds

Manuel Caroli 1 Monique Teillaud 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We give a definition of the Delaunay triangulation of a point set in a closed Euclidean d-manifold, i.e.\ a compact quotient space of the Euclidean space for a discrete group of isometries (a so-called Bieberbach group or crystallographic group). We describe a geometric criterion to check whether a partition of the manifold actually forms a triangulation (which subsumes that it is a simplicial complex). We provide an algorithm to compute the Delaunay triangulation of the manifold defined by a given set of points, if it exists. Otherwise, the algorithm returns the Delaunay triangulation of a finitely sheeted covering space of the manifold. Whereas there was prior work for the special case of the flat torus, as far as we know this is the first result for general closed Euclidean d-manifolds. This research is motivated by application fields, like computational structural biology for instance, showing a need to perform simulations in quotient spaces of the Euclidean space by more general groups of isometries than the groups generated by d independent translations.
Document type :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00506017
Contributor : Manuel Caroli <>
Submitted on : Monday, July 26, 2010 - 7:21:05 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Long-term archiving on: : Tuesday, October 23, 2012 - 11:25:29 AM

File

RR-7352.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00506017, version 1

Collections

Citation

Manuel Caroli, Monique Teillaud. Delaunay Triangulations of Point Sets in Closed Euclidean d-Manifolds. [Research Report] RR-7352, INRIA. 2010. ⟨inria-00506017⟩

Share

Metrics

Record views

407

Files downloads

416