### On Kinetic Delaunay Triangulations: A Near-Quadratic Bound for Unit Speed MotionsOn Kinetic Delaunay Triangulations: A Near-Quadratic Bound for Unit Speed Motions

Access Restriction
Subscribed

 Author Rubin, Natan Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Computational geometry ♦ Delaunay triangulation ♦ Voronoi diagram ♦ Combinatorial complexity ♦ Discrete changes ♦ Geometric arrangements ♦ Kinetic data structures ♦ Moving points Abstract Let $\textit{P}$ be a collection of $\textit{n}$ points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of $O(n^{2+ε}),$ for any ε > 0, on the maximum number of discrete changes that the Delaunay triangulation $DT(\textit{P})$ of $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 3 Page Count 85 Starting Page 1 Ending Page 85

#### Open content in new tab

Source: ACM Digital Library