Exact Computation of the Voronoi Diagram of Polyhedra in Space
Final Report Abstract
An important research motivation in Applied Computational Geometry is that many geometric algorithms, for instance used in Computer Aided Design systems, are actually not robust, e.g., due to use of fast but inexact floating point arithmetic. Within this general setting we are interested in the robust solution of general geometric problems that steam from the context of robot motion planing. The initial proposal for this project was to investigate the Voronoi Diagram of polyhedra in three-dimensional space as the diagram encodes the set of positions that keep maximal clearance from the obstacles. Important milestones where the improvement of the basic algebraic tools as well as a guaranteed logarithmic planar point location within planar subdivisions of general (possibly unbounded) algebraic curves. The second milestone was a unexpected success as we fully achieved the milestone and in addition also improved the runtime of the general algorithm from O(nlog2^n) to O(nlogn). This was unexpected as planar point location is very fundamental and well studied field. For the first milestone, we where able to extend ideas for lazy construction for algebraic numbers of low algebraic degree, but we where not able to generalize ideas to algebraic numbers of arbitrary (i.e. the required) degree. As a consequence the runtimes for an input of around 25 lines in generic position remained above several hours, which is not an acceptable runtime for a practical application of the approach. Therefore, I had to draw my attention to several other topics that are directly or indirectly motivated by exact computing and robot motion planing. Together with Alon Braham I worked on exact planar Minkowski sum computation for simple polygons. The work covers different convolution methods and provides concrete proofs of several theoretical aspects. Up to a few pathological examples the implementation computes Minkowski sums significantly faster than the old exact implementation within CGAL. Working with Oren Salzman on robot motion planing we suggest to take samples of the robots configuration space that are entire low-dimensional manifolds. These samples capture the connectivity of the configuration space much better than isolated point samples. Moreover, together with Andreas von Dziegielewski and Elmar Schomer I introduce a novel and efficient technique to generate a high quality mesh that approximates the outer boundary of a swept volume (SV) with guarantees.
Publications
- 2D Arrangements, CGAL - Computational Geometry Algorithms Library. CGAL, 4.0 edition, May 2012
Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman
- 2D Arrangements, CGAL - Computational Geometry Algorithms Library. CGAL, 4.1 edition, October 2012
Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman
- High quality conservative surface mesh generation for swept volumes. In Proceedings of the 2012 IEEE Intemational Conference on Robotics and Automation, pages 764-769, St. Paul, Minnesota, USA, May 2012. IEEE
Andreas von Dziegielewski, Michael Hemmer, and Elmar Schömer
- Improved implementation of point location in general two-dimensional subdivisions. In Proceedings of the 20th European Symposium on Algorithms, pages 611-623, Ljubljana, Slovenia, September 2012. Springer
Michael Hemmer, Michal Kleinbort, and Dan Halperin
- Lines through segments in 3D space. In Proceedings of the 20th European Symposium on Algorithms, pages 455-466, Ljubljana, Slovenia, September 2012. Springer
Efi Fogel, Michael Hemmer, Asaf Porat, and Dan Halperin
- On the power of manifold samples in exploring configuration spaces and the dimensionality of narrow passages. In Proceedings of the 10th International Workshop on the Algorithmic Foundations of Robotics, Cambridge, Massachusetts, USA, June 2012. Springer
Oren Salzman, Michael Hemmer, and Dan Halperin
- Motion planning via manifold samples. Algorithmica, pages 1-19, 2013
Oren Salzman, Michael Hemmer, Barak Raveh, and Dan Halperin
(See online at https://doi.org/10.1007/s00453-012-9736-1)
