Proximity structures for moving objects in constrained and unconstrained environments.

摘要

Proximity structures are of central importance in Computational Geometry. They appear in several applications such as robotics, motion planning, collision detection and also in simulations of virtual and physical systems. In the real world, in most of these applications the geometric objects involved are often moving. It is thus essential to be able to maintain in an efficient way proximity structures for moving objects.; In this thesis we deal with two kinds of proximity structures: sparse spanner graphs and Voronoi diagrams. We prove that bounded aspect ratio triangulations in two and three dimensions are spanner graphs. We also show that both conforming two-dimensional bounded aspect ratio triangulations and the Constrained Delaunay triangulation are spanner graphs.; Using the Kinetic Data Structures (KDS) framework, we show how to maintain near neighbors for moving points in two and three dimensions when the underlying structure is the Voronoi diagram. In the more realistic case of a set of possibly intersecting disks moving on the plane we show how to maintain the Euclidean Voronoi diagram. Using then the Voronoi diagram as a basis, we describe how to maintain the closest pair of the set of disks, a spanning sub-graph of the connectivity graph of the set of disks and near neighbors of disks.; Finally, we discuss the problem of handling kinetic simulations of geometric objects whose motion is represented as polynomials of high degree. In this setting, the moments in time that a change happens in the combinatorial structure of the attribute of interest are roots of polynomials of high degree. We present an algorithm that speeds up the kinetic simulations by representing the roots of the afore-mentioned polynomials as intervals, instead of computing them explicitly.