Paper Info
Title
On topological changes in the delaunay triangulation of moving points
Abstract
Let P be a collection of n points moving along pseudo-algebraic trajectories in the plane. One of the hardest open problems in combinatorial and computational geometry is to obtain a nearly quadratic upper bound, or at least a subcubic bound, on the maximum number of discrete changes that the Delaunay triangulation DT(P) of P experiences during the motion of the points of P. In this paper we obtain an upper bound of O(n2+ε), for any ε0, under the assumptions that (i) any four points can be co-circular at most twice, and (ii) either no ordered triple of points can be collinear more than once, or no triple of points can be collinear more than twice.
Year
DOI
Venue
2013
10.1145/2261250.2261252
Proceedings of the twenty-eighth annual symposium on Computational geometry
Keywords
DocType
Volume
Delaunay triangulation,Moving points,Discrete changes,Voronoi diagram,Combinatorial complexity
Journal
abs/1304.3671
Issue
ISSN
Citations 
4
0179-5376
7
PageRank 
References 
Authors
0.55
12
1
Name
Order
Citations
PageRank
Natan Rubin19211.03