Proximity: Variants and Generalizations

The main conclusion derived from the preceding chapter is that the Voronoi diagram is both an extremely versatile tool for the solution of some fundamental proximity problems and an exceptionally attractive mathematical object in its own right. Indeed, these two facets—the instrumental and the aesthetic—have been the inspiration of a considerable amount of research on the topic. This chapter is devoted to the illustration of these extensions. Specifically, we shall at first discuss two very important applications: the already mentioned Euclidean Minimum Spanning Tree problem (and its ramifications) and the general problem of plane triangulations. We shall then show how the locus concept can be generalized in a number of directions. We shall then close the chapter with the analysis of “gaps and covers,” which will afford us a chance to appreciate the power of different computation models.