Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra

Nina Amenta; Dominique Attali; Olivier Devillers

inria-00182835, version 2

Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra

Nina Amenta ()^a^, 1, Dominique Attali ()^b^, 2, Olivier Devillers ()^c^, 3

18th ACM-SIAM Sympos. Discrete Algorithms (2007) 1106--1113

Abstract: We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p between 2 and d-1, this improves on the well-known worst-case bound of $O(n^ceil(d/2))$.

a – University of California at Davis
b – CNRS
c – INRIA
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-00182835, version 2
http://hal.inria.fr/inria-00182835
oai:hal.inria.fr:inria-00182835
From: Olivier Devillers <>
Submitted on: Thursday, 8 November 2007 10:11:20
Updated on: Monday, 21 April 2008 13:38:49

See detailed view

Associated documents

PDF :

Export

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="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00182835"><analytic>
<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="a">Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra</title></analytic><monogr><meeting>18th ACM-SIAM Sympos. Discrete Algorithms</meeting><imprint><pubPlace><settlement>New Orleans</settlement><country>United States</country></pubPlace><biblScope type="publicationDate">2007-00-00</biblScope><biblScope type="pp">1106--1113</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00182835</idno><idno type="HALFile">http://hal.inria.fr/inria-00182835/PDF/hal.pdf</idno></biblStruct>
</listBibl>
</listBibl>