Title :
On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions
Abstract :
Let P be a collection of n points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of O(n2+ε), for any ε > 0, on the maximum number of discrete changes that the Delaunay triangulation DT(P) of P experiences during this motion. Our analysis is cast in a purely topological setting, where we only assume that (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice; these assumptions hold for unit speed motions.
Keywords :
computational complexity; computational geometry; topology; Voronoi diagram; combinatorial complexity; discrete changes; kinetic Delaunay triangulations:; near quadratic bound; topological setting; unit speed motions; Complexity theory; Indexes; Kinetic theory; Maintenance engineering; Probabilistic logic; Trajectory; Upper bound; Delaunay triangulation; Voronoi diagram; combinatorial complexity; discrete changes; moving points;
Conference_Titel :
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location :
Berkeley, CA
DOI :
10.1109/FOCS.2013.62