Robotics, video games, simulations, virtual reality, and many other domains that involve motion planning rely on kinetic triangulation data structures of a set of moving points. Delaunay triangulation is a method in which no point in the scheme is inside the circumcircle of any triangle of the triangulation. In Rubin’s paper, under the assumption that points in the plane are moving along a straight line at unit speed, an approach of upper bound of O(n2+ε), for any positive ε, is established in a recursive fashion. This complexity refers to the number of changes in the triangulation in motion under the following restrictions: during the motion, any four points can be on the same circle at most three times and on the same line twice. The study is purely topological in nature.
The paper is written in a strict and structured mathematical language, with detailed proofs of theorems that indicate (to computer scientists) which algorithms could be applied to make use of the findings and to speed up projects that are in need of triangulations. The multiple examples and illustrations ease its reading, as does the introductory part that lays out the big picture of the rest of the work.
