On Deletion in Delaunay Triangulation

Details On Deletion in Delaunay Triangulation On Deletion in Delaunay Triangulation

1999-07-16

arxiv.org/abs/cs/9907023v1

Computer Science

Computational Geometry

15 pages 5 figures. in Proc. 15th Annu. ACM Sympos. Comput. Geom., 181--188, 1999

Scientific paper

This paper presents how the space of spheres and shelling may be used to delete a point from a $d$-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex, the complexity is O(k log k), but we notice that this number only applies to low cost operations, while time consuming computations are only done a linear number of times. This algorithm may be viewed as a variation of Heller's algorithm, which is popular in the geographic information system community. Unfortunately, Heller algorithm is false, as explained in this paper.

Affiliated with

Also associated with

No associations

Rating

On Deletion in Delaunay Triangulation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Deletion in Delaunay Triangulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Deletion in Delaunay Triangulation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162625