removing points from a 3-D Delaunay tetrahedralization

[Olivier Devillers]

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

 
@inproceedings{d-ddt-99
, author =      "Olivier Devillers"
, title =       "On Deletion in {Delaunay} Triangulation"
, booktitle =   "Proc. 15th Annu. ACM Sympos. Comput. Geom."
, year =        1999
, pages =       "181--188"
, url = "http://www-sop.inria.fr/prisme/publis/d-ddt-99.ps.gz"
, 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 
2-dimension
, 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 
information
 system community. Unfortunately Heller algorithm is false as 
explained in this
paper."
}


----------------------------------------------------------------------
-----
O. Devillers, INRIA, 2004 route des Lucioles, BP 93, 06902 Sophia 
Antipolis
Olivier.Devillers at sophia.inria.fr, +33 4 92 38 77 63, Fax +33 4 92 38 
76 43
         http://www-sop.inria.fr/prisme/personnel/devillers/



-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/maillist.html.