# Pencils of CGA for Voronoi and Power Diagrams

Clément Chomicki¹, Stéphane Breuils², Venceslas Biri¹, and Vincent Nozick¹

¹ LIGM, Univ Gustave Eiffel, CNRS, France

² LAMA, Univ Savoie Mont-Blanc, CNRS, France

**Abstract.** Geometric Algebra can be considered as a very useful language for dealing with mathematics, physics and computer science. Among the various algebras commonly used by practitioners of GA, Conformal Geometric Algebra (CGA) is of special interest for its powerful transformations and its ability to represent any hypersphere or hyperplane. Moreover, CGA is an algebra capable of representing pencils of hyperspheres. This paper presents an approach for constructing Voronoi diagrams by using pencils of CGA to build cell interfaces from centroid positions. Power, multiplicatively weighted Voronoi and multiplicatively weighted power diagrams are also supported by the presented method. This allows the use of circles as centroids to add control to the weights of the cells and to the curvatures of their borders.

**Keywords:** Voronoi Diagrams, Geometric Algebra, Projective Geometry, Clifford Algebra, Pencil, Conformal Geometric Algebra (CGA)

## 1 Introduction

Clifford Algebras, also known as Geometric Algebras (GA), provide a robust and adaptable mathematical structure, particularly well-suited for exploring geometry and related fields. Many geometric algebras enable the creation of their objects using some of their points or through intersections [15,3,10]. This shared characteristic stems from their ability to handle pencils of objects, as confirmed by prior research [16,8,5]. On the other hand, Voronoi diagrams are a powerful tool for splitting space into cells. Voronoi diagrams have been invented in 1908 by Georgy Voronoi [17], and have since then been heavily used in fields such as physics, geology, meteorology, mathematics and many others. They are also a very important tool in computer graphics where they are used for texture generations [18] or image segmentation [12]. Other diagrams can be derived from Voronoi diagrams, such as the power diagram [1] and the multiplicatively and additively weighted Voronoi diagrams [7].

This paper presents new formulations of Voronoi, power, multiplicatively weighted Voronoi and multiplicatively weighted power diagrams based on CGA and pencils of circles, with a focus on the computation of the interface of two cells. This paper starts with some notations in Sec. 1.1, followed by a short introduction to the various kinds of diagrams in Sec. 2 and to CGA and its pencils in
Sec 3. Sec. 4 then presents a new way to compute the distance function and interfaces of Voronoi, power, multiplicatively weighted Voronoi and multiplicatively weighted power diagrams based on CGA and its pencils.

## 1.1 Notations

Most of the notations in this paper are based on [9] and [13]. In addition, the followings are specified:

<table><tr><td>A*</td><td>dual [9] of A with A* = AI<sup>-1</sup></td></tr><tr><td>∧, ∨, ·</td><td>outer, anti-outer and inner products [13]</td></tr><tr><td>A ≡ B</td><td>A equals B up to a non-zero scalar factor</td></tr><tr><td>Dist(p<sub>1</sub>, p<sub>2</sub>)</td><td>the Euclidean distance between two points p<sub>1</sub> and p<sub>2</sub></td></tr></table>

# 2 Dividing space into cells

This paper presents various **diagrams**, tiling the plane into **cells** using a set of centroids and a given distance function.

**Definition 1.** Let E be a Euclidean space and D: (E, E) → ℝ a distance function. Consider a finite subset A of E. The couple (A, D) is called a **diagram** in the scope of this paper, and defines a tiling of the space into **cells**. Consider one of the centroids p_c ∈ A. The **cell** of p_c is the set of point in the form:

$$ \text{Cell}(p_c) = \{p \in E \mid \forall p'_c \in A \setminus \{p_c\}, D(p_c, p) < D(p'_c, p)\} \quad (1) $$

This paper puts a focus on how to compute the **interface** of two cells of various diagrams.

**Definition 2.** Consider two centroids p_c,1 and p_c,2 of a diagram associated with a distance function D. The **interface** of the cells of p_c,1 and p_c,2, denoted Interface(p_c,1, p_c,2) is the curve of the form:

$$ \text{Interface}(p_{c,1}, p_{c,2}) = \{p \mid D(p_{c,1}, p) = D(p_{c,2}, p)\} \quad (2) $$

The following four distance functions can be encountered, describing four common diagrams.

<table><tr><td>Dist<sub>Voronoi</sub>(p<sub>c</sub>, p) = Dist(p<sub>c</sub>, p)</td><td>Voronoi Diagram</td><td>(3)</td></tr><tr><td>Dist<sub>Power</sub>(p<sub>c</sub>, r, p) = Dist(p<sub>c</sub>, p)<sup>2</sup> - r<sup>2</sup></td><td>Power Diagram</td><td>(4)</td></tr><tr><td>Dist<sub>VorWgt×</sub>(p<sub>c</sub>, w, p) = <div style="display: inline-block; vertical-align: middle; text-align: center;"><div style="border-bottom: 1px solid black; padding: 0 5px;">Dist(p<sub>c</sub>, p)</div><div style="padding: 0 5px;">w</div></div></td><td>Multiplicatively Weighted Voronoi Diagram</td><td>(5)</td></tr><tr><td>Dist<sub>VorWgt+</sub>(p<sub>c</sub>, w, p) = Dist(p<sub>c</sub>, p) - w</td><td>Additively Weighted Voronoi Diagram</td><td>(6)</td></tr></table>
Voronoi diagrams are quite simple, as the distance used is the standard Euclidean distance. It results in polygonal cells whose interfaces are then straight lines.

Power diagrams are very much alike with the difference that the centroids are circles instead of points. The radius of the centroids increases the area of their cells while keeping their interfaces straight.

Multiplicatively Weighted Voronoi diagrams are a bit different. The weights have for effect of curving the interfaces of the cells toward the less important one. The interfaces then become circles.

Additively Weighted Voronoi Diagram, similarly to the multiplicative ones, have their interfaces curved by their weights. However the curvature is different, as they can now be any conic, such as ellipses or hyperbolas, which are not supported by this paper. Additively Weighted Voronoi diagrams are therefore out of this paper's scope.

What interfaces are to be computed and how to split them into segments and arcs to form a mesh is a known problem. An elegant CGA-powered method for Voronoi diagrams only has been proposed by Romero et al. [14]. This paper does not go as far as presenting a full algorithm for diagram construction, but presents a general method for computing interfaces of several kinds of additional diagrams on $\mathbb{R}^2$.

## 3 CGA and its pencils

C2GA (Conformal two-dimensional Geometric Algebra) objects can be understood as pencil of circles (or hyperspheres for CGA of dimension $n$, but this paper is about 2D CGA), i.e. vector spaces of circles. When drawing a pencil, only their intersection appears. For instance a pair of points can be understood as the set of all circles passing through it. This representation has been developed in previous work, such as [4] or [16].

**Definition 3.** Consider $n \in [0, 4]$. The dual blades $P$ of grade $4-n$ are called $n$-pencils, and represents the pencils generated by $n$ linearly independent circles $C_1, \dots, C_n$. The pencils can be computed as the meet product of their circles:

$$P = C_1 \vee \dots \vee C_n \qquad (7)$$

Studying the squared radius of the circles of a 2-pencil $P$ containing at least one non-flat circle (ie at least one circle of finite radius) shows that it is possible to find exactly one circle of infinite radius $\mathrm{Flat}(P) = P \wedge e_\infty$ and exactly one circle of minimal squared radius $\mathrm{Small}(P) = P \wedge \mathrm{Flat}(P)^*$, with $\mathrm{Flat}(P)^*$ the dual of $\mathrm{Flat}(P)$ as introduced in Sec. 1.1. Moreover, if $\mathrm{Small}(P)$ is an imaginary circle (a circle of the form $C = (p + \frac{r^2}{2}e_\infty)^*$, i.e. a circle of imaginary radius $ir$), two circles of null radius $p_1^*$ and $p_2^*$ can also be found.

As an imaginary 2-pencil is a space of dimension 2 containing two dual points $p_1^*$ and $p_1^*$, we can describe its circles under the form $\lambda p_1^* + \mu p_2^*$. Because linearly
<figure><img src="image_1.png" /><figcaption>Fig. 1: An imaginary pencil of circles $P = (p_1 \wedge p_2)^*$ with $p_1$ and $p_2$ two points. $P$ is represented by some sampled circles in (a) and as a trigonometric circle in (b), representing the exploration of $P$ with the formula $C(t) = p_1^* \cos(t) + p_2^* \sin(t)$. The real or imaginary nature of the radii of $C(t)$ is also indicated, outlining the structure of the pencil $P$ and the characteristics of its circles. Each object appears twice as their signs does not matter within this projective framework.</figcaption></figure>
dependent circles represent the same object, it is possible to only consider the unit circle cos(t)p<sub>1</sub><sup>*</sup> + sin(t)p<sub>2</sub><sup>*</sup>.

**Definition 4.** The Flat and Small operator on round pencils are defined by [4] as follows:

$$
\mathrm{Flat}(P) = P \wedge e_{\infty} \qquad (8)
$$

$$
\mathrm{Small}(P) = P \wedge \mathrm{Flat}(P)^* \qquad (9)
$$

With P a round pencil. A normalized version of these operators can also be
defined:

$$
\widehat{\mathrm{Flat}}(P) = \frac{\mathrm{Flat}(P)}{\sqrt{\mathrm{Flat}(P)^2}} \qquad (10)
$$

$$
\widehat{\mathrm{Small}}(P) = \frac{\mathrm{Small}(P)}{\mathrm{Flat}(P)^2} \qquad (11)
$$

**Theorem 1.** Consider an imaginary 2-pencil *P*. *P* contains exactly two circles of radius 0, *p*<sub>1</sub><sup>*</sup> and *p*<sub>2</sub><sup>*</sup>, and the following relationships are verified:

$$
\mathrm{Flat}(P) = -(\widehat{p}_1 - \widehat{p}_2)^* \qquad = \sqrt{-2(\widehat{p}_1 \cdot \widehat{p}_2)} \widehat{\mathrm{Flat}}(P) \quad (12)
$$

$$
\mathrm{Small}(P) = -(\widehat{p}_1 \cdot \widehat{p}_2)(\widehat{p}_1 + \widehat{p}_2)^* = -2(\widehat{p}_1 \cdot \widehat{p}_2) \widehat{\mathrm{Small}}(P) \quad (13)
$$

With $\widehat{p} = \frac{\mathbf{p}}{-\mathbf{p} \cdot e_{\infty}}$ the normalization of points used in this paper.

Proof. *P* is imaginary, hence it is a point pair of finite imaginary radius. The dual of *P* is then a point pair of finite real radius, hence two points *p*₁ and *p*₂ can be found in *P*'. Now that *P* can be written as (*p*₁ ∧ *p*₂)’, the relationships (12) and (13) are proven by simply computing:

$$
P = (\hat{p}_1 \wedge \hat{p}_2)^* \qquad (14)
$$

$$
= \frac{1}{2}((\hat{p}_1 - \hat{p}_2) \wedge (\hat{p}_1 + \hat{p}_2))^* \qquad (15)
$$

$$
\mathrm{Flat}(P) = P \wedge e_{\infty} = (P^* \cdot e_{\infty})^* = (-\hat{p}_1 + \hat{p}_2)^* \quad (16)
$$

$$
\mathrm{Small}(P) = P \wedge \mathrm{Flat}(P)^* \qquad (17)
$$

$$
= \left( \frac{1}{2} \left( (\hat{p}_1 - \hat{p}_2) \wedge (\hat{p}_1 + \hat{p}_2) \right) \cdot (-\hat{p}_1 + \hat{p}_2) \right)^* \quad (18)
$$

$$
= \frac{1}{2}((\hat{p}_1 - \hat{p}_2) \cdot (\hat{p}_1 - \hat{p}_2))(\hat{p}_1 + \hat{p}_2)^* \quad (19)
$$

$$
= -(\hat{p}_1 \cdot \hat{p}_2)(\hat{p}_1 + \hat{p}_2)^* \qquad (20)
$$

$$
\mathrm{Flat}(P)^2 = -2 (\hat{p}_1 \cdot \hat{p}_2) \qquad (21)
$$

□

Th. 1 shows that it is entirely possible to work with dual points to produce easily
various interesting circles of an imaginary 2-pencil. Such a case is illustrated by
Fig. 1. However, this is not true for every 2-pencil. For instance, it is not possible to find the line of a pencil with the formula (12) for a real pencil. Hence the use of the Flat and Small operators to produce representative elements of a pencil is in general more appropriate than trying to find points when working with a non-flat pencil.

# 4 CGA diagrams

This section presents how to compute the interfaces of Voronoi, power, multiplicatively weighted Voronoi and multiplicatively weighted power diagrams using pencils of circles.

## 4.1 Voronoi Diagram

Voronoi diagrams are built with the standard Euclidean distance, and the centroids are points.

**Lemma 1.** Consider a centroid $p_c$ and a point $p$.

$$ \mathrm{Dist}_{\mathrm{Voronoi}}(p_c, p) = \sqrt{-2 \hat{p}_c \cdot \hat{p}} \qquad (22) $$

*Proof.*

$$ \hat{p}_c \cdot \hat{p} = - \frac{(x - x_c)^2 + (y - y_c)^2}{2} \qquad (23) $$

$$ = -\frac{1}{2} \mathrm{Dist}(p_c, p)^2 = -\frac{1}{2} \mathrm{Dist}_{\mathrm{Voronoi}}(p_c, p)^2 \qquad (24) $$

□

**Theorem 2.** Consider two points $p_1$ and $p_2$, that will be used as centroids of two adjacent cells of a Voronoi diagram. The interface of the cells of these centroids is a line $l$.

$$ l = \mathrm{Interface}(p_1, p_2) = \mathrm{Flat}((p_1 \wedge p_2)^*) \qquad (25) $$

*Proof.* The resulting line is perpendicular to $p_1 \wedge p_2$ and passes through the center of that point pair. □

## 4.2 Power Diagram

A power diagram is simply a Voronoi diagram whose centroids can be circles. At this point, it is possible for two circles to intersect each other, which results in a real pencil (case mentioned in Sec. 3).

The distance function is naturally handled by CGA:
**Lemma 2.** Consider a point p and a circle C of center p_c and radius r.

$$ \mathrm{Dist}_{\mathrm{Power}}(p_c, r, p) = -2\hat{C}^* \cdot \hat{p} \qquad (26) $$

*Proof.*

$$ C^* \cdot p = (p_c - \frac{r^2}{2} e_\infty) \cdot p = -\frac{1}{2} \mathrm{Dist}(p_c, p)^2 + \frac{r^2}{2} \qquad (27) $$

□

**Theorem 3.** The interface of the two adjacent power diagram cells whose respective centroids are some circles C_1 and C_2 is a line l of the form:

$$ l = \mathrm{Interface}(C_1, C_2) = \mathrm{Flat}(C_1 \cup C_2) \qquad (28) $$

*Proof.* Consider C_1 and C_2 to be two circles of respective center p_1 and p_2 and radii r_1 and r_2. This proof relies on the fact that we can chose p_1 and p_2 to be e_0 - xe_1 + x_2^2 e_\infty and e_0 + xe_1 + x_2^2 e_\infty, as any other configuration can be derived from these position with rigid transformations, which won't affect distances. We can compute the line l as the straight object of the 2-pencil generated by C_1 and C_2:

$$ l = (C_1 \cup C_2) \wedge e_\infty = e_1 + \frac{r_1^2 - r_2^2}{4x} e_\infty \qquad (29) $$

Let's look at a point p on l. Its coordinates are $(\frac{r_1^2 - r_2^2}{4x}, y)$ with $y \in \mathbb{R}$. One can observe that

$$ \mathrm{Dist}_{\mathrm{Power}}(p_1, r_1, p) = \mathrm{Dist}_{\mathrm{Power}}(p_2, r_2, p) \qquad (30) $$

Hence points on l are equidistant from p_1 and p_2 for Dist<sub>Power</sub>. Therefore l is the interface of the cells of the power diagram of centroids C_1 and C_2. □

## 4.3 Multiplicatively weighted Voronoi diagram

The centroids are points paired with a scalar which contributes multiplicatively to the distance function.

**Lemma 3.** Consider a centroid p_c associated with a weight w ∈ ℝ<sup>+</sup>. Consider a point p.

$$ \mathrm{Dist}_{\mathrm{VorWgt} \times}(p_c, w, p) = \frac{\sqrt{-2 \hat{p}_c \cdot \hat{p}}}{w} \qquad (31) $$

*Proof.*

$$ \frac{\mathrm{Dist}(p_c, p)}{w} = \frac{\sqrt{-2 \hat{p}_c \cdot \hat{p}}}{w} \qquad (32) $$

□
**Theorem 4.** Consider a multiplicatively weighted Voronoi diagram with $p_1$ and $p_2$ two of its centroids of respective weights $w_1$ and $w_2$ in $\mathbb{R}^+$. The interface of the cells of $p_1$ and $p_2$ is a circle C of the form:

$$C = \text{Interface}((p_1, w_1), (p_2, w_2)) = (w_2^2 \widehat{p_1} - w_1^2 \widehat{p_2})^* \quad (33)$$

*Proof.* Consider a multiplicatively weighted Voronoi diagram with $p_1$ and $p_2$ two of its centroids of respective weights $w_1$ and $w_2$ in $\mathbb{R}^+$. The interface C of the cells of $p_1$ and $p_2$ is the set of the points p satisfying

$$\text{Dist}_{\text{VorWgt} \times} (p_1, w_1, p) = \text{Dist}_{\text{VorWgt} \times} (p_2, w_2, p) \quad (34)$$

Which can be directly rewritten

$$\text{Dist}(p_1, p)w_2 - \text{Dist}(p_2, p)w_1 = 0 \quad (35)$$

This implies the sum of two square roots, which is quite unpleasant to manipulate. The keen eye of the reader might have noticed that a similar equation $\text{Dist}(p_1, p)w_2 + \text{Dist}(p_2, p)w_1 = 0$ is only true for some points that are already a solution of Eq. 35. Multiplying both equations then produces a new one that describes the same set of points as Eq. 35.

$$(\text{Dist}(p_1, p)w_2 + \text{Dist}(p_2, p)w_1)(\text{Dist}(p_1, p)w_2 - \text{Dist}(p_2, p)w_1) = 0 \quad (36)$$

$$\iff \text{Dist}(p_1, p)^2 w_2^2 - \text{Dist}(p_2, p)^2 w_1^2 = 0 \quad (37)$$

$$\iff w_2^2 \widehat{p_1} \cdot p - w_1^2 \widehat{p_2} \cdot p = 0 \quad (38)$$

$$\iff (w_2^2 \widehat{p_1} - w_1^2 \widehat{p_2}) \cdot p = 0 \quad (39)$$

$$\iff (w_2^2 \widehat{p_1} - w_1^2 \widehat{p_2})^* \wedge p = 0 \quad (40)$$

Hence the Eq. 33. □

**Theorem 5.** Consider a multiplicatively weighted Voronoi diagram with $p_1$ and $p_2$ two of its centroids of respective weights $w_1$ and $w_2$ in $\mathbb{R}^+$. The interface C of the cells of $p_1$ and $p_2$ is of the form:

$$C = (\widehat{p_1} \cdot \widehat{p_2}) \text{Flat}(P) - \frac{w_1^2 - w_2^2}{w_1^2 + w_2^2} \text{Small}(P) \quad \text{with } P = (\widehat{p_1} \wedge \widehat{p_2})^* \quad (41)$$

$$\equiv \frac{1}{2} \text{Flat}(P) + \frac{w_1^2 - w_2^2}{w_1^2 + w_2^2} \widehat{\text{Small}}(P) \quad (42)$$
Proof.

$$P = (\widehat{p}_1 \wedge \widehat{p}_2)^* \qquad (43)$$

$$\mathrm{Flat}(P) = P \wedge e_{\infty} \qquad (44)$$

$$= -(\widehat{p}_1 - \widehat{p}_2)^* \qquad (45)$$

$$\mathrm{Small}(P) = P \wedge \mathrm{Flat}(P)^* \qquad (46)$$

$$= -(\widehat{p}_1 \cdot \widehat{p}_2)(\widehat{p}_1 + \widehat{p}_2)^* \qquad (47)$$

$$w_2^2 \widehat{p}_1 - w_1^2 \widehat{p}_2 = \frac{1}{2} \left( (w_1^2 + w_2^2)(\widehat{p}_1 - \widehat{p}_2) - (w_1^2 - w_2^2)(\widehat{p}_1 + \widehat{p}_2) \right) \qquad (48)$$

$$= -\frac{1}{2} \left( (w_1^2 + w_2^2) \mathrm{Flat}(P) - \frac{w_1^2 - w_2^2}{\widehat{p}_1 \cdot \widehat{p}_2} \mathrm{Small}(P) \right) \qquad (49)$$

$$\equiv (41) \qquad (50)$$

□

## 4.4 Multiplicatively weighted Power diagram

Sec. 4.2 shows that using circles instead of points as centroids can be used to compute the power diagram interface of two cells. On the other hand Sec. 4.3 shows that it is possible to pitch a Voronoi diagram interface with multiplicative weights to displace it within the pencil and make it rounder. One could then be tempted to combine both approaches: using both circles and weights to both increase the area of a cell and curve the interfaces. This kind of diagram, called multiplicatively weighted power diagram, can be found in some papers dealing with power and weighted Voronoi diagrams [6].

**Definition 5.** Consider a non-flat circle C with a weight $w \in \mathbb{R}^+$ and a point p. In the scope of this paper, the distance function for the weighted power diagram between C and p is the following:

$$\mathrm{Dist}_{\mathrm{PowWgt} \times} (p_c, r, w, p) = -2 \frac{\hat{C}^* \cdot \hat{p}}{w^2} \qquad (51)$$

With $\hat{C} = \frac{C}{-C^* \cdot e_{\infty}}$ the normalization of non-flat circles used in this paper.
**Theorem 6.** Consider a multiplicatively weighted power diagram with $C_1$ and $C_2$ two of its centroids of respective weights $w_1$ and $w_2$ in $\mathbb{R}^+$. The interface $C_i$ of the cells of $C_1$ and $C_2$ is a circle of the form:

$$C_i = \text{Interface}((C_1, w_1), (C_2, w_2)) \qquad (52)$$

$$= w_2^2 \widehat{C}_1 - w_1^2 \widehat{C}_2 \qquad (53)$$

$$= (\widehat{C}_1 \cdot \widehat{C}_2) \text{Flat}(P) - \frac{w_1^2 - w_2^2}{w_1^2 + w_2^2} \text{Small}(P) \quad \text{with } P = \widehat{C}_1 \vee \widehat{C}_2 \qquad (54)$$

$$\equiv \frac{1}{2} \text{Flat}(P) + \frac{w_1^2 - w_2^2}{w_1^2 + w_2^2} \widehat{\text{Small}}(P) \qquad (55)$$

*Proof.* Let $C_1$ and $C_2$ be two circles of respective centers $p_{c,1}$ and $p_{c,2}$ and respective radii $r_1, r_2$. Consider a point $p$ and the pencil $P = \widehat{C}_1 \vee \widehat{C}_2$.

$$\text{Dist}_{\text{PowWgt}\times}(p_{c,1}, r_1, w_1, p) = \text{Dist}_{\text{PowWgt}\times}(p_{c,2}, r_2, w_2, p) \qquad (56)$$

$$\iff -2 \frac{\widehat{C}_1^* \cdot p}{w_1^2} = -2 \frac{\widehat{C}_2^* \cdot p}{w_2^2} \qquad (57)$$

$$\iff (w_2^2 \widehat{C}_1^* - w_1^2 \widehat{C}_2^*) \cdot p = 0 \qquad (58)$$

$$\text{And } w_2^2 \widehat{C}_1 - w_1^2 \widehat{C}_2 = (\widehat{C}_1 \cdot \widehat{C}_2) \text{Flat}(P) - \frac{w_1^2 - w_2^2}{w_1^2 + w_2^2} \text{Small}(P) \qquad (59)$$

□

# 5 Conclusion

This paper presents an elegant way to compute the distances functions and interface of two cells of Voronoi diagrams, power diagrams, multiplicatively weighted Voronoi diagrams and multiplicatively weighted power diagrams. These interfaces are shown to be lines in the case of Voronoi and power diagrams, and circles or lines in the case of the multiplicatively weighted diagrams. The pencils of CGA were shown to be an elegant manner of computing the interfaces of these diagrams, by exploiting the fact that the pencil generated by the centroids of two cells contains their interface. The interface relative to two centroids can be located within their pencil from a convenient basis made from the line of the pencil and its circle of smallest squared radius. It is then possible to consider the interface as a small displacement from the straight line toward the smallest circle within the space of the pencil. This method has been implemented in C++ with Garamon [2] (see https://github.com/technolapin/voronoi-engage24). Fig. 1 shows the (split) interfaces generated by that code. In practice, it is convenient to be able to split the interfaces of two cells into the relevant arc for the diagram. Hence further work is needed to adapt existing algorithms - such as the one proposed by Romero et al. [14] - to construct the actual mesh of the various diagrams. Also, more complex algebras could be used
<figure><img src="image_2.png" /><figcaption>Fig. 2: Comparison of the various kind of diagrams produced by our code. The interfaces have been split into their relevant arc by hand for clarity.</figcaption></figure>

to permit more interfaces shapes, such as GAC/QC2GA [11,5] for additively weighted Voronoi diagrams.

References

1. Aurenhammer, F.: Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing **16**(1), 78–96 (1987). https://doi.org/10.1137/0216006

2. Breuils, S., Nozick, V., Fuchs, L.: Garamon: A Geometric Algebra Library Generator. Advances in Applied Clifford Algebras **29**(4), 69 (Jul 2019)

3. Breuils, S., Nozick, V., Sugimoto, A., Hitzer, E.: Quadric Conformal Geometric Algebra of $\mathbb{R}^{9,6}$. Advances in Applied Clifford Algebras **28**(2), 35 (Mar 2018)
4. Chomicki, C., Breuils, S., Biri, V., Nozick, V.: Pencils and set operators in 3D CGA (May 2024), https://hal.science/hal-04569529,

5. Chomicki, C., Breuils, S., Biri, V., Nozick, V.: Intersection of Conic Sections Using Geometric Algebra. In: Advances in Computer Graphics. pp. 175–187. Lecture Notes in Computer Science, Springer Nature Switzerland, Cham (Aug 2023). https://doi.org/10.1007/978-3-031-50078-7_14

6. Devillers, O., Meiser, S., Teillaud, M.: The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. report, INRIA (1992), https://inria.hal.science/inria-00074941

7. Dobrin, A.: A review of properties and variations of voronoi diagrams. Whitman College 10(1.453), 9156 (2005)

8. Dorst, L.: 3D Oriented Projective Geometry Through Versors of $\mathbb{R}^{3,3}$. Advances in Applied Clifford Algebras 26(4), 1137–1172 (2016), publisher: Springer

9. Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry. Elsevier (Jul 2010), google-Books-ID: Sg_uR57ZktoC

10. Gunn, C.G.: Projective geometric algebra: A new framework for doing euclidean geometry (2020), https://arxiv.org/pdf/1901.05873

11. Hrdina, J., Návrat, A., Vašík, P.: Geometric Algebra for Conics. Advances in Applied Clifford Algebras 28(3), 66 (Jun 2018). https://doi.org/10.1007/s00006-018-0879-2

12. Jones, T.R., Carpenter, A., Golland, P.: Voronoi-based segmentation of cells on image manifolds. In: Liu, Y., Jiang, T., Zhang, C. (eds.) Computer Vision for Biomedical Image Applications. pp. 535–543. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)

13. Perwass, C.: Geometric Algebra with Applications in Engineering, Geometry and Computing, vol. 4. Springer, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-540-89068-3, ISSN: 1866-6795

14. Romero, N., Barrón-Fernández, R., Godoy-Calderón, S.: Constructing Voronoi Diagrams from Hollow Spheres Using Conformal Geometric Algebra. Advances in Applied Clifford Algebras 27(3), 1997–2017 (Sep 2017). https://doi.org/10.1007/s00006-017-0787-x

15. Sommer, G. (ed.): Geometric Computing with Clifford Algebras. Springer, Berlin, Heidelberg (2001). https://doi.org/10.1007/978-3-662-04621-0

16. Vincent, H.: Using geometric algebra to interactively model the geometry of Euclidean and non-Euclidean spaces. phd, Middlesex University (Feb 2007), https://eprints.mdx.ac.uk/6750/

17. Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik (Crelles Journal) 1908(134), 198–287 (Jul 1908). https://doi.org/10.1515/crl1.1908.134.198

18. Worley, S.: A cellular texture basis function. Proceedings of the 23rd annual conference on Computer graphics and interactive techniques pp. 291–294 (Aug 1996). https://doi.org/10.1145/237170.237267