Paper Info
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.
Year
DOI
Venue
2015
10.1145/2746228
J. ACM
Keywords
DocType
Volume
Design,Algorithms,Theory,Computational geometry,Voronoi diagram,Delaunay triangulation,moving points,kinetic data structures,combinatorial complexity,geometric arrangements,discrete changes
Journal
62
Issue
ISSN
Citations 
3
0004-5411
3
PageRank 
References 
Authors
0.39
7
1
Name
Order
Citations
PageRank
Natan Rubin19211.03