Handbook of Computer Aided Geometric Design

Chapter 18

Voronoi Diagrams

Kokichi Sugihara

This chapter surveys the Voronoi diagram and related topics. First, the most primitive version of the Voronoi diagram is defined, and its basic properties together with the algorithms for constructing it are summarized. Next possible applications of the Voronoi diagram are presented, where special emphasis is placed on offsetting and interpolations. Finally the Voronoi diagram is generalized in various directions; they include generalization of the metric and the generalization of the generators.

18.1 ORDINARY VORONOI DIAGRAM

The topic in this chapter is a partition of a space into territories, which is called a ‘Voronoi diagram’. This concept is so natural that it was rediscovered in many areas ...