Ph.D Thesis | |

Ph.D Student | Hanniel Iddo |
---|---|

Subject | Robust Arrangements and Voronoi Diagrams of Free-form Curves and Surfaces |

Department | Department of Computer Science |

Supervisor | PROF. Gershon Elber |

Full Thesis text |

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 R^{2} (points, line segments
and circular arcs) and in R^{3} (medial axes of polyhedra) have been
published.

This work will focus on algorithms for computing Voronoi cells
of free-form curves in R^{2} and of planes, spheres and cylinders in R^{3}.
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.