O'Reilly logo

Handbook of Computer Aided Geometric Design by M.-S. Kim, J. Hoschek, G. Farin

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required