removing points from a 3-D Delaunay tetrahedralization

Olivier Devillers Olivier.Devillers at
Fri May 19 10:26:23 PDT 2000

The following paper works in 3D (I have imlemented it even if it is
not written in the paper. I ghave done it afterwards).

, author =      "Olivier Devillers"
, title =       "On Deletion in {Delaunay} Triangulation"
, booktitle =   "Proc. 15th Annu. ACM Sympos. Comput. Geom."
, year =        1999
, pages =       "181--188"
, url = ""
, archive =     "XXX:cs.CG/9907023"
, succeeds =    "d-ddt-98"
, cites =       "agss-ltacv-89, a-pdpaa-87, bbp-iayed-98scg, 
bd-irgo-95, bm-sdcs
-71, c-bvdcp-86, ads-rdppw-98, d-iirdt-98, dmt-ssgtu-92i, 
dp-papaf-98, es-itfwr-
96, gs-cdtp-78, h-taatm-90, l-tdam-97, m-smdnt-93, msz-frplw-96, 
obs-stcav-92, p
-gcc-70, s-chdch-86, s-nmpgc-98"
, update =      "99.11 bibrelex+devillers, 99.07 devillers"
, abstract =    "This paper present how space of spheres and shelling 
can be use
d to delete efficiently a point from d-dimensional triangulation. In 
, if k is the degree of the deleted vertex, the complexity is 
$O(k\log k)$, but
we notice that this number apply only to low cost operations; time 
consuming com
putations are done only a linear number of times. This algorithm can 
be viewed a
s a variation of Heller algorithm which is popular in the geographic 
 system community. Unfortunately Heller algorithm is false as 
explained in this

O. Devillers, INRIA, 2004 route des Lucioles, BP 93, 06902 Sophia 
Olivier.Devillers at, +33 4 92 38 77 63, Fax +33 4 92 38 
76 43

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list