Up front two remarks to avoid any confusion and misconceptions.
First, it is more cumbersome to distinguish between d=2 and d=3
dimensions than to phrase all definitions in ,
for some arbitrary but fixed positive integer d.
Second, we use square roots of real numbers as weights.
Since negative weight squares do make sense,
we choose
as the domain for all point weights.
This is the set of all (positive) square roots of
real numbers, and it inherits its linear order from
.
A point
with weight
,
is interpreted as a spherical ball,
with center p and
radius ,
where |yz| denotes the Euclidean distance between points y and z.
All points with non-real weight correspond to empty balls.
Figure 1: The union of a set of disks in the plane.
The shape of a finite set
of weighted points is defined in terms of a decomposition of
the union of balls,
, into convex sets
(see, for example, figures 1 and 2).
Figure 2: The decomposition of the union of disks defind by their
Voronoi cells.
The (weighted) Voronoi cell of a ball is
It is a convex polyhedron, and its intersection with the ball union
is convex because
.
Note that the convex cells have pairwise disjoint interiors,
but some of them overlap along common boundary pieces.
These pieces of overlap are instrumental in the construction
of a set system closed under the subset operation.
In topology, such a system is referred to as an
abstract simplicial complex.
Specifically, we define the nerve of
as
Assuming general position of the points or balls, the largest
set in is
of size d+1, i.e.,
a triple in
and
a quadruple in
.
Under this assumption,
has a natural geometric realization
by mapping each cell
to the point
.
This realization is a (geometric) simplicial complex,
,
see e.g. [10].
Each set
is represented by the convex hull of the
corresponding points:
the points are the images of the cells in X and their convex
hull is a simplex of dimension one less than the cardinality of X.
Formally,
Figure 3: The dual complex of the disk union.
We refer to this complex as the dual complex of ,
and to its underlying space,
,
as the dual shape (see figures 3 and 4).
Figure: The decomposition of the union of disks and its dual complex
(figures 2 and 3 overlapped).
Among the most useful properties of are the homotopy
equivalence between
and
, and the
fact
can be expressed as the alternating sum of common
ball intersections, with one term per simplex in
.
This implies short inclusion-exclusion formulas for the
d-dimensional volume and other measures of
,
see [5].