Chapter 8 - Dirichlet–Voronoi Diagrams - 8 - Fundamental Concepts

Oct 26, 2026

Chapter 8 introduces Voronoi diagrams and Delaunay triangulations as core tools in computational geometry. It motivates the problems of partitioning space into regions associated with points and constructing triangulations of the convex hull with desirable properties. The chapter defines bisector lines and half-planes, extends the idea to bisector planes and half-spaces in higher dimensions, and explains key relationships underpinning Voronoi cells and Delaunay triangulations, including geometric projections tied to convex hulls.

LanguageEnglish

CategoryTechnology

FormatPDF

Pages49

Reading Time2 h 3 min

AccessFree to download

8.1 Dirichlet–Voronoi Diagrams

Voronoi diagrams and Delaunay triangulations overview

Bisector lines and half-planes in 2D

Post office problem and Voronoi regions V(pi)

Bisector planes and half-spaces in 3D

Applications and further sections (8.5–8.7)

Chapter 8 Dirichlet–Voronoi Diagrams and Delaunay Triangulations 8.1 Dirichlet–Voronoi Diagrams In this chapter we present the concepts of a Voronoi diagram and of a Delaunay triangulation. These are important tools in computational geometry and Delaunay triangulations are important in problems where it is necessary to ﬁt 3D data using surface splines. It is usually useful to compute a good mesh for the projection of this set of data points onto the xy-plane, and a Delaunay triangulation is a good candidate. Our presentation of Voronoi diagrams and Delaunay triangulations is far from thorough. We are primarily interested in deﬁning these concepts and stating their most important properties. For a comprehensive exposition of Voronoi diagrams, Delaunay triangulations, and more topics in computational geometry, our readers may consult O’Rourke [31], Preparata and Shamos [32], Boissonnat and Yvinec [8], de Berg, Van Kreveld, Overmars, and Schwarzkopf [5], or Risler [33] . The survey by Graham and Yao [23] contains a very gentle and lucid introduction to computational geometry. In Section 8.6 (which relies on Section 8.5), we show that the Delaunay triangulation of a set of points, P, is the stereographic projection of the convex hull of the set of points obtained by mapping the points in P onto the sphere using inverse stereogrgaphic projection. We also prove that the Voronoi diagram of P is obtained by taking the polar dual of the above convex hull and projecting it from the north pole (back onto the hyperplane containing P) . A rigorous proof of this second fact is not trivial because the central projection from the north pole is only a partial map. To give a rigorous proof, we have to use projective completions. But then, we need to deﬁne what is a convex polyhedron in projective space and for this, we use the results of Chapter 5 (especially, Section 5.2) . Some practical applications of Voronoi diagrams and Delaunay triangulations are brieﬂy discussed in Section 8 .7. Let E be a Euclidean space of ﬁnite dimension, that is, an aﬃne space E whose underlying 146 CHAPTER 8 . DIRICHLET–VORONOI DIAGRAMS Figure 8 . 1: The bisector line L of a and b −→ vector space E is equipped with an inner product (and has ﬁnite dimension) . For concreteness, one may safely assume that E = Em , although what follows applies to any Euclidean space of ﬁnite dimension. Given a set P = {p1 ,..., pn } of n points in E, it is often useful to ﬁnd a partition of the space E into regions each containing a single point of P and having some nice properties. It is also often useful to ﬁnd triangulations of the convex hull of P having some nice properties. We shall see that this can be done and that the two problems are closely related. In order to solve the ﬁrst problem, we need to introduce bisector lines and bisector planes. For simplicity, let us ﬁrst assume that E is a plane i.e. , has dimension 2 . Given any two distinct points a, b ∈ E, the line orthogonal to the line segment (a, b) and passing through the midpoint of this segment is the locus of all points having equal distance to a and b. It is called the bisector line of a and b. The bisector line of two points is illustrated in Figure 8.1. If h = ~~1~~2 a+ ~~1~~2 b is the midpoint of the line segment (a, b), letting m be an arbitrary point on the bisector line, the equation of this line can be found by writing that hm is orthogonal to ab. In any orthogonal frame, letting m = (x, y ), a = (a1 , a2 ), b = (b1 , b2 ), the equation of this line is (b1 − a1 )(x − (a1 + b1 )/2) + (b2 − a2 )(y − (a2 + b2 )/2) = 0 , which can also be written as (b1 − a1 )x +(b2 − a2 )y = (b21 + b22)/2 − (a21 + a22)/2 . The closed half-plane H (a, b) containing a and with boundary the bisector line is the locus of all points such that (b1 − a1 )x +(b2 − a2 )y ≤ (b21 + b22)/2 − (a21 + a22)/2 , 8.1. DIRICHLET–VORONOI DIAGRAMS 147 and the closed half-plane H (b, a) containing b and with bou

FAQs

What is the main purpose of Voronoi diagrams and Delaunay triangulations in this chapter?

They are introduced as important tools in computational geometry, used to partition space into regions for sites and to construct triangulations of convex hulls with useful geometric properties.

How are bisector lines defined for two distinct points in a plane?

For points a and b, the bisector line is the set of points orthogonal to segment (a,b) that passes through its midpoint, consisting of points equidistant from a and b.

What changes when moving from 2D to 3D in the bisector construction?

The locus of points equidistant from two points becomes a bisector plane, obtained by an orthogonality condition similar in spirit to the 2D bisector line derivation.

Oct 26, 2026

Upload by Sophia Brooks