Ph.D Thesis

Ph.D StudentHanniel Iddo
SubjectRobust Arrangements and Voronoi Diagrams of Free-form Curves
and Surfaces
DepartmentDepartment of Computer Science
Supervisor PROF. Gershon Elber
Full Thesis textFull thesis text - English Version


Voronoi diagrams and medial axis transforms have proven to be useful tools in a variety of application domains. Several algorithms for constructing Voronoi diagrams of low-order objects in R2 (points, line segments and circular arcs) and in R3 (medial axes of polyhedra) have been published.

This work will focus on algorithms for computing Voronoi cells of free-form curves in R2 and of planes, spheres and cylinders in R3. The union of the Voronoi cells is the Voronoi diagram. Both algorithms compute lower envelopes for constructing the Voronoi cell. The first algorithm uses a two-dimensional lower envelope algorithm on the arrangement of the bisector curves, while the second algorithm uses a three-dimensional lower envelope algorithm on the arrangement of the bisector surfaces.

The algorithms are based on solving sets of multivariate polynomial equations. For this we use a multivariate solver for sets of piecewise polynomial equations, which has been developed at the Technion for the last several years. We present a novel result we had on an algorithm for identifying and isolating domains having a single solution in this subdivision-based solver. We incorporated this algorithm into the solver, making its solution more robust.

Robustness in geometric computation is a fundamental, difficult and well-known problem arising from the special nature of geometric algorithms. The exact geometric computation paradigm was successful in robustly solving many computational geometry problems. However, until recently algorithms on free-form objects were not implemented using exact arithmetic. This was a consequence of the high degree of free-form objects and their inherent complexity. We also present a novel implementation of arrangements of Bezier curves, which is implemented using exact arithmetic. To the best of our knowledge this is the first complete implementation that can construct arrangements of Bezier curves of any degree, and handle all degenerate cases in a robust manner.