 |
 |
 |
Conference papers
Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra
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))$.
Cited literature [16 references]
https://hal.inria.fr/inria-00182835
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, November 8, 2007 - 10:11:20 AM
Last modification on : Thursday, January 20, 2022 - 5:30:37 PM
Long-term archiving on: : Friday, November 25, 2016 - 7:24:51 PM
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, November 8, 2007 - 10:11:20 AM
Last modification on : Thursday, January 20, 2022 - 5:30:37 PM
Long-term archiving on: : Friday, November 25, 2016 - 7:24:51 PM
File
hal.pdf
Files produced by the author(s)