Ph.D Thesis | |

Ph.D Student | Reem Daniel |
---|---|

Subject | Voronoi and Zone Diagrams |

Department | Department of Mathematics |

Supervisor | PROFESSOR EMERITUS Simeon Reich |

Full Thesis text |

This thesis deals with topics from computational geometry and fixed point theory.

It consists of two parts.

The first part deals with Voronoi diagrams. Voronoi diagrams appear in many areas in science and technology and have diverse applications. Roughly speaking, they are a certain decomposition of a given space into cells, induced by a distance function and by a tuple of subsets called the generators or the sites. Voronoi diagrams

have been the subject of extensive research during the last 35 years, and many algorithms for computing them have been published. However, these algorithms are for specific cases. They impose various restrictions on the space (often R^2 or R^3), the generators (distinct points, special shapes), the distance function (Euclidean or variations thereof) and more. Moreover, their implementation is not always simple and their success is not always guaranteed.

We present and analyze an efficient and simple algorithm for computing Voronoi diagrams in general normed spaces, possibly infinite dimensional. We allow infinitely many generators of a general form. The algorithm computes each of the Voronoi cells independently of the others, and to any required precision.

It is also generalized to other settings, such as manifolds, graphs and weighted distances. We also discuss the question of stability, and as a by-product we obtain the geometric stability of Voronoi diagrams under small perturbations of the generators in a class of normed spaces.

The second part of the thesis deals with zone diagrams, trisectors and double zone diagrams. These are fixed points of certain mappings, and they are related to Voronoi diagrams. The first two concepts were introduced recently by T. Asano,

J. Matousek and T. Tokuyama, and the third one is our contribution. The above authors considered the Euclidean plane with singleton sites and proved the existence and uniqueness of zone diagrams and trisectors there. In addition, they described an iterative algorithm for approximating them.

We
consider general sites and investigate the above objects in various settings,
including *m*-spaces and (uniformly convex) normed spaces. We prove
several (non)existence and (non)uniqueness results there, as well as other
properties of the relevant objects. Our methods are significantly different
from the methods used in previous papers. We also present an algorithm for
approximating the above objects in several settings.

The above algorithms for computing the Voronoi and zone diagrams were implemented, and several pictures which were produced by these implementations are also included.