Delaunay Triangulations of Point Sets in Closed Euclidean d-Manifolds - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2010

Delaunay Triangulations of Point Sets in Closed Euclidean d-Manifolds

(1) , (1)
1
Manuel Caroli
  • Function : Author
  • PersonId : 843218
Monique Teillaud

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.
Nous donnons une définition de la triangulation de Delaunay d'un ensemble de points dans une variété euclidienne fermée de dimension $d$, c'est-à-dire un quotient compact de l'espace Euclidien par l'action d'un groupe discret d'isométries (dit aussi groupe de Bieberbach ou groupe cristallographique). Nous décrivons un critère geométrique permettant de vérifier si une partition de la variété forme réellement une triangulation (ce qui sous-entend que c'est un complexe simplicial). Nous proposons un algorithme calculant, si elle existe, la triangulation de Delaunay de la variété, définie par un ensemble de points donné. Sinon, l'algorithme fournit la triangulation de Delaunay d'un revêtement fini de la variété. Alors qu'il existe des travaux antérieurs pour le cas particulier du tore plat, à notre connaissance c'est le premier résultat pour des variétés euclidiennes fermées générales de dimension $d$. Cette recherche est motivée par des domaines d'application tels que la modélisation moléculaire, par exemple, qui expriment le besoin d'effectuer des simulations dans des espèces quotients de l'espace euclidien par des groupes d'isométries plus généraux que les groupes engendrés par $d$ translations indépendantes.
Fichier principal
Vignette du fichier
RR-7352.pdf (438.44 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00506017 , version 1 (26-07-2010)

Identifiers

  • HAL Id : inria-00506017 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More