Digital Geometry

CHAPTER 13

Hulls and Diagrams

The convex hull of a set can be regarded as a “domain of influence” of the set. Similarly, the Voronoi diagram of a set of points defines “domains of influence” of the points. This chapter discusses hulls and diagrams in Euclidean space or in a grid, with emphasis on 2D. We discuss definitions of digital convexity and digital Voronoi diagrams and give algorithms based on adjacency grid models. We also discuss “domains of influence” in pictures.

13.1 Hulls

Let S be a class of subsets of a set S. A function H that takes sets in S into sets in S is called a hull operator iff it has the following properties:

H1: M ⊆ H (M) for all M ∈ S.

H2: M₁ ⊆ M₂ implies H(M₁) ⊆ H(M₂) for all M_1,M₂ ∈ S.

H3: H (H (M)) ⊆ H (M) for ...