A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron

Nina Amenta; Dominique Attali; Olivier Devillers

inria-00277899, version 2

A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron

Nina Amenta ()^a^, 1, Dominique Attali () ², Olivier Devillers () ³

N° RR-6522 (2008)

Résumé : We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)), where k = ceil(d+1)/(p+1)$. This bound is tight, and improves on the prior upper bound for most values of p.

a – University of California at Davis
1 : Visualization and Graphics Research Group.
University of California at Davis
2 : Grenoble Images Parole Signal Automatique (GIPSA-lab)
CNRS : UMR5216 – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Université Stendhal - Grenoble III – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
3 : GEOMETRICA (INRIA Sophia Antipolis)
INRIA

inria-00277899, version 2
http://hal.inria.fr/inria-00277899
oai:hal.inria.fr:inria-00277899
Contributeur : Olivier Devillers <>
Soumis le : Mardi 13 Mai 2008, 10:14:29
Dernière modification le : Lundi 14 Décembre 2009, 13:03:26

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00277899"><monogr>
<author><persName><forename>Nina</forename><surname>Amenta</surname></persName>
<affiliation>
<orgName type="team">Visualization and Graphics Research Group.</orgName>
<country>US</country>
<orgName type="institution">University of California at Davis</orgName>
</affiliation>
</author>
<author><persName><forename>Dominique</forename><surname>Attali</surname></persName>
<affiliation>
<orgName type="laboratory">GIPSA-lab</orgName>
<orgName type="team">Grenoble Images Parole Signal Automatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5216</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
<orgName type="institution">Université Stendhal - Grenoble III</orgName>
<orgName type="institution">Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Devillers</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<title type="main" level="m">A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron</title><title type="main" level="m">A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron</title><imprint><biblScope type="publicationDate">2008-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00277899</idno><idno type="HALFile">http://hal.inria.fr/inria-00277899/PDF/RR-6522.pdf</idno></biblStruct>
</listBibl>
</listBibl>