Ph.D Thesis
Ph.D Student Reem Daniel Voronoi and Zone Diagrams Department of Mathematics Professor Emeritus Simeon Reich

Abstract

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.