Ready, Set, Go! The Voronoi diagram of moving points that start from a line |
| |
Authors: | Vladlen Koltun |
| |
Affiliation: | Computer Science Division, University of California, Berkeley, CA 94720-1776, USA |
| |
Abstract: | It is an outstanding open problem of computational geometry to prove a near-quadratic upper bound on the number of combinatorial changes in the Voronoi diagram of points moving at a common constant speed along linear trajectories in the plane. In this note we observe that this quantity is Θ(n2) if the points start their movement from a common line. |
| |
Keywords: | Computational geometry Voronoi diagram Near-quadratic upper bound |
本文献已被 ScienceDirect 等数据库收录! |
|