Constrained edges on kinetic delaunay triangulation

Abstract

Real world can be described as an interaction of moving objects and obstacles. To address this fact, we consider how to transform a straightforward set of vertices into a simple and enriched structure that includes obstacles. It has been done by representing obstacles with constrained edges. To model motion, Kinetic Data Structure has demonstrated to be suitable and adaptable for different geometrical and logical structures. However, for modeling collision detection has been proposed Kinetic Delaunay Triangulation. First, we proposed a Kinetic Constrained Delaunay Triangulation, which is as Delaunay as possible and represents obstacles by constrained edges and objects by vertices. Second, we contribute with a Kinetic Delaunay Constrained Triangulation model that guarantees both: constrained edges and the Delaunay Triangulation structure. Third, we show experiments for each kinetic model to compare their performance. The purpose of this article is to show and evaluate new models to understand its strengths and weaknesses.