נתן רובין
אקדמי בכיר
On kinetic Delaunay triangulations
A near-quadratic bound for unit speed motions
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.
| שפת פרסום | אנגלית |
| כתב עת | Journal of the ACM |
| כרך | 62 |
| נושא מספר | 3 |
| סטטוס פרסום | פורסם - 01.06.2015 |
| מספר מאמר | 25 |
Keywords
Algorithms
Combinatorial complexity
Computational geometry
Computing methodologies → computer graphics
Delaunay
Design
Discrete changes
Geometric arrangements
Kinetic data structures
Mathematics of computing → combinatorics; combinatorial algorithms
Moving points
Theory
Theory of computation → computational geometry
Triangulation
Voronoi diagram
ASJC Scopus subject areas
Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence
