Tel Aviv University, Blavatnik School of Computer Science
"Exact Computation of the Voronoi Diagram of Polyhedra in 3-Dimensional Space"
Summary of Research:
An important research motivation in Computational Geometry is that many geometric algorithms, for instance used in Computer Aided Design systems, are actually not robust. Often, this is caused by the use of fast but inexact floating point arithmetic. For instance, it is very hard to decide whether two objects just come very close or whether they actually touch each other. This can lead to wrong (and inconsistent) decisions within algorithms which may even lead to a full crash of the system.
Computer Algebra has developed very general and exact tools that could solve such problems in principle, but a naive application of these tools is by far too slow to be used in practice. Our cardinal research interest is thus to incorporate the best methods from Computational Geometry, Solid Modeling and Computer Algebra in order to design and implement geometric algorithms that are exact, complete and efficient (the first two imply robustness).
In this context we decided to focus our attention towards a fundamental data structure in Computational Geometry, the Voronoi Diagram (VD). For a set of input objects the VD is the decomposition of the space into cells such that each Voronoi cell exactly contains all points that are closer to a particular object than to all other objects. Our ambition is to develop and implement an efficient, exact and complete algorithm that computes the VD of a set of polyhedral objects in three-dimensional space.
We anticipate that the successful completion of our project will have wider impact on the feasibility of robustly implementing complex three-dimensional geometric structures, an area that is not as well developed as its two-dimensional counterpart.
In particular, we expect that it will pave the way to devising a three-dimensional variant of the visibility-Voronoi complex, a structure that enables to trade-off clearance and path length in robot motion planning, and has proved to be especially useful in the plane.
Moreover, we are certain that our exact approach can be generalized to other geometric objects such as spheres which would open the door for innovative solutions to central problems in Structural Biology.
Update: December 2016