# Arc Spline Approximation of Envelopes of Evolving Planar Domains

Jana Vráblíková, Bert Jüttler

<figure><img src="image_1.png" /></figure>

► To cite this version:

Jana Vráblíková, Bert Jüttler. Arc Spline Approximation of Envelopes of Evolving Planar Domains. 2026. hal-05441841

HAL Id: hal-05441841

https://hal.science/hal-05441841v1

Preprint submitted on 5 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Arc Spline Approximation of Envelopes of Evolving Planar Domains

Jana Vráblíková*, Bert Jüttler

Institute of Applied Geometry, Johannes Kepler University, Linz/Austria

## Abstract

Computing the envelope of deforming planar domains is a significant and challenging problem with a wide range of potential applications. We approximate the envelope using circular arc splines, curves that balance geometric flexibility and computational simplicity. Our approach combines two concepts to achieve these benefits.

First, we represent a planar domain by its medial axis transform (MAT), which is a geometric graph in Minkowski space $R^{2,1}$ (possibly with degenerate branches). We observe that circular arcs in the Minkowski space correspond to MATs of arc spline domains. Furthermore, as a planar domain evolves over time, each branch of its MAT evolves and forms a surface in the Minkowski space. This allows us to reformulate the problem of envelope computation as a problem of computing cyclographic images of finite sets of curves on these surfaces. We propose and compare two pairs of methods for approximating the curves and boundaries of their cyclographic images. All of these methods result in an arc spline approximation of the envelope of the evolving domain.

Second, we exploit the geometric flexibility of circular arcs in both the plane and Minkowski space to achieve a high approximation rate. The computational simplicity ensures the efficient trimming of redundant branches of the generated envelope using a sweep line algorithm with optimal computational complexity.

**Keywords:** Envelope, Evolving planar domains, Minkowski space, Circular arcs

## 1. Introduction

Sweeping a planar domain along a predefined trajectory is a powerful tool for e.g. constructing more complex domains and the main challenge is to approximate the envelope of the resulting volume or area. The case where the domain moves under a rigid body motion has been well studied, see e.g. [35] and the references therein.

<footnote>*Corresponding author</footnote>

<footnote>Email addresses: jana.vrablikova@jku.at (Jana Vráblíková*), bert.juettler@jku.at (Bert Jüttler)</footnote>
Swept volumes can be generalized if we allow the domain to change its size or shape as it moves. We call such domains *evolving domains*. In the literature, the process is sometimes called general sweep.

## 1.1. Related work

Some of the existing methods build upon the techniques for computation of the envelope of a domain undergoing a rigid body motion. For example, Sweep Differential Equation (SDE) and Sweep Envelope Differential Equation (SEDE) were proposed [12, 13]. They identify the sweeps with first-order linear ordinary equations. The methods were later generalized to general sweeps [11, 46].

Other methods develop the theory for evolving domains separately. Kim and Elber formulate the problem as a polynomial equation in three variables [26]. Despite considering exact geometries, the technique generates a polyhedral approximation of the surface of the evolving domain.

In the case of planar evolving domains, a method for obtaining the exact envelope was proposed in [25] for domains that move along a parametric curve trajectory while they evolve, i.e., change their shape parametrically. The algorithm generates curve segments from which the envelope is extracted by a plane sweep algorithm. The plane sweep algorithm proposed by Bentley and Ottmann [8] was designed to compute and report intersections in a set of line segments and can be generalized to other primitives. However, for segments of algebraic curves of high degree, the plane sweep algorithm is highly inefficient.

To overcome the time difficulties, a polygonal approximation of the envelope of an evolving domain was proposed [1]. The envelope is again extracted by the plane sweep algorithm from a set of lines generated by the method. The polygonal boundaries are then fitted by cubic splines.

An incremental algorithm was proposed by [33]. At each instance of the time parameter, the domain is approximated by a polygonal boundary and the envelope is generated using boolean operations on simple polygons, which can be implemented robustly. The incremental nature of the algorithm produces the envelope at each step, such that no additional removal of redundant parts is necessary, making it useful for interactive shape design.

Our method is based on the interpolation of the medial axis transform. Medial axis (MA) was introduced by Blum [15] as a tool for shape recognition. It describes a planar domain by the centres of medial disks, i.e., maximum disks that are inscribed in the domain and are tangent to its boundary at at least two points. The medial axis transform (MAT) is defined by the medial axis and the radius function of the medial disks. Besides shape recognition, the medial axis transform has a wide range of applications, for example in domain decomposition, where it can be then used for $G^1$-smooth parameterization of complex domains [40].

The medial axis transform can be computed exactly for domains with piecewise linear or piecewise circular boundaries [4, 18, 22, 32]. For free-form shapes, the MAT can be approximated using a variety of techniques, including tracing methods [16, 21, 43], divide-
and-conquer methods [3, 20], and computing the Voronoi diagrams of sampled points [6, 23, 49].

In [48] it is shown that the medial axis of a compact set $\Omega$ with a piecewise $C^2$ smooth boundary $\delta\Omega$ is path-connected. If $\delta\Omega$ consists of finitely many real analytic curves, in [19] it is shown that $\text{MA}(\Omega)$ and $\text{MAT}(\Omega)$ are connected geometric graphs with finitely many branches (edges) and vertices.

The branches of the medial axis transform can be seen as curves in Minkowski space $\mathbb{R}^{2,1}$ [21, 41]. Minkowski space is a model of Laguerre geometry, the Euclidean geometry of oriented spheres and hyperplanes. Laguerre geometry was first introduced by Blaschke [14] and reexamined in a modern manner by Cecil [17]. Minkowski space (also called the cyclographic model) of Laguerre geometry was described in [41]. The model establishes a one-to-one correspondence between oriented spheres and points in Minkowski space. The mapping that assigns an oriented circle to a point in Minkowski space is called the cyclographic mapping. A cyclographic image of a point of the MAT of a planar domain is a medial disc and the domain can be recreated as the envelope of the medial discs.

The particular class of Minkowski Pythagorean-hodograph (MPH) curves [39], which are rationally parameterized curves that represent branches of the MAT, corresponds to domains that possess rationally parameterizable domain boundaries. It has been generalized to the broader class of RE curves [10], which share the rational envelope property with MPH curves.

Our results are also related to earlier work on methods for circle skinning, see [31] and the references therein. Given a sequence of circles in a defined admissible position, these methods find two $G^1$ continuous curves (skins) that touch each circle at a point. The method of Kunkli and Hoffmann [31] identifies points of contact with associated tangents, which are then interpolated by cubic curves, resulting in two $G^1$ continuous skins. While this construction is rather general, in some cases, the skins can intersect each other or the input circles. The problem of self-intersections has been addressed in [29].

Alternatively, the skins can be obtained with the help of envelope curves. In two recent papers [28, 30], the authors use RE curves to obtain rational skins without self-intersections. Skinning can be generalized to branched sets of circles, allowing more complicated shapes to be considered. Bastl et al. [7] consider unions of skins of subsets of circles, and Kruppa et al. [29] analyze branching in more detail, ensuring smooth transitions.

We present methods for generating supersets of the envelopes of one-parameter families of circles. These supersets are either $C^0$ or $C^1$ continuous curves, which may contain self-intersections. However, this approach allows us to impose fewer restrictions on the admissible positions of the circles, and self-intersections can be easily handled using the line-sweep algorithm. Furthermore, our approach generalizes process of skinning circles defined by a curve in $\mathbb{R}^{2,1}$ to skinning of a two-parameter system of circles, i.e., an evolving domain represented by a surface in $\mathbb{R}^{2,1}$. From this surface, we extract the relevant one-parameter subsets, that form the superset of the envelope of the evolving domain.

We approximate the envelopes of evolving domains by circular arcs. Circular arcs are well-established primitives for approximating boundaries of planar domains and they
approximate a smooth curve segment with approximation order 3 [38]. Biarc construction provides a $G^1$ smooth interpolation of a given curve and there are various techniques for biarc approximation of smooth curves [37, 38] or interpolation of discrete data [9, 36]. In [45], the approximation properties of the different techniques were examined.

Moreover, circular arcs provide many computational advantages [5]. The construction of Voronoi diagrams with circular arcs as sites [2] and of medial axis for planar shapes with arc spline boundaries [3, 4] is efficient and robust. For an arc spline domain, i.e., a domain represented by its boundary which consists of circular arcs, it was shown that the arc fibration kernel has again a piecewise circular boundary and a geometric algorithm that computes the arc fibration kernel was proposed [47]. Self-intersections in offsets were detected and trimmed using biarc approximations of planar curves [27]. In [24], an effective algorithm for the Minkowski sum computation of two planar objects with an arc spline boundary was proposed, using interior disc culling. Last but not least, the line sweep algorithm [8] can be adapted for computing intersections of circular arcs with the same time complexity as for intersections of line segments.

## 1.2. *Outline of the method*

We propose an algorithm for arc spline approximation of envelopes of evolving domains. We assume the evolving domains are represented by evolving MATs. The method is based on the following key observations.

1. The envelopes of *evolving worms* can be approximated by arc splines. A planar domain whose MAT is a curve in $R^{2,1}$ is called a *worm*. More generally, a worm is any planar domain which is the cyclographic image of a single curve segment in $R^{2,1}$. When these domains move and evolve in time, they are called evolving worms. We characterize the envelope of the evolving worms and present methods for approximating them by arc splines.

2. At every instance of a time parameter, an evolving free-form domain is a union of worms. The envelope of the evolving free-form domain is a subset of the union of the envelopes of evolving worms.

3. The outer envelope can be extracted by trimming the arc splines. This can be done efficiently by the line sweep algorithm [8].

In this paper, we focus mostly on the first observation. In Section 2, we recall Minkowski space $R^{2,1}$, Minkowski circles and arcs and we review the medial axis transform. In Section 3 we introduce worms and evolving worms and characterize their envelopes. The computation of the envelope relies on interpolation of certain curves in the Minkowski space. We present and compare two pairs of methods for interpolating the curves in the Minkowski space in Section 4. In all four cases, the worms defined by the interpolants have arc spline boundaries. Section 5 describes the computation of the envelope of an evolving worm. In Section 6 we apply computation of envelopes of evolving worms to envelopes of evolving free-form domains and present several examples.
## 2. Preliminaries

In this section, we recall Minkowski space $\mathbb{R}^{2,1}$ and the medial axis transform. We interpret the branches of the medial axis transform as curves in the Minkowski space.

### 2.1. Minkowski space $\mathbb{R}^{2,1}$

The Minkowski space $\mathbb{R}^{2,1}$ is a real 3-dimensional vector space equipped with the Minkowski inner product, defined for two vectors

$$ \mathbf{v}_1 = (x_1, y_1, r_1)^T, \mathbf{v}_2 = (x_2, y_2, r_2)^T \in \mathbb{R}^{2,1}, \qquad (1) $$

by

$$ \langle \mathbf{v}_1, \mathbf{v}_2 \rangle_M = \mathbf{v}_1^T G \mathbf{v}_2 = x_1 x_2 + y_1 y_2 - r_1 r_2, \qquad (2) $$

where $G = \text{diag}(1, 1, -1)$. For a vector $\mathbf{v} \in \mathbb{R}^{2,1}$, we denote

$$ \|\mathbf{v}\|_M = \langle \mathbf{v}, \mathbf{v} \rangle_M . \qquad (3) $$

The Minkowski inner product defines three types of vectors in $\mathbb{R}^{2,1}$:

**Definition 1.** A vector $\mathbf{v} \in \mathbb{R}^{2,1}$ is called

* space-like, if $\|\mathbf{v}\|_M > 0$,

* light-like, if $\|\mathbf{v}\|_M = 0$, or

* time-like, if $\|\mathbf{v}\|_M < 0$.

Similarly, we distinguish three types of planes in the Minkowski space:

**Definition 2.** A plane in $\mathbb{R}^{2,1}$ is called space-like, light-like or time-like, if the restriction of the quadratic form defined by $G$ on the plane is positive definite, indefinite degenerate or indefinite non-degenerate, respectively.

There is a one-to-one correspondence between planar oriented circles and points in Minkowski space $\mathbb{R}^{2,1}$. An oriented circle $\mathbf{c}$ centered at the point $(x, y)^T \in \mathbb{R}^2$ with a radius $r \in \mathbb{R}$ is represented by the pair $\mathbf{c} = ((x, y)^T, r)$.

The mapping

$$ \zeta : \mathbb{R}^{2,1} \to \mathbb{R}^2 \\ C = (x, y, r)^T \mapsto c = ((x, y)^T, r), $$

that assigns an oriented circle to a point in Minkowski space $\mathbb{R}^{2,1}$ is called the *cyclographic mapping*. The image of point $(x, y, 0)^T \in \mathbb{R}^{2,1}$ is the point $(x, y)^T \in \mathbb{R}^2$, which is considered to be a circle with zero radius.
A curve $C(u) = (x(u), y(u), r(u))^T$, $u \in I \subset \mathbb{R}$, in the Minkowski space defines a one-parameter family of oriented circles in $\mathbb{R}^2$. The cyclographic image of each point $C(u_0)$, $u_0 \in I$, is an oriented circle $c(u_0)$,

$$ \zeta(C(u_0)) = c(u_0) = ((x(u_0), y(u_0))^T, r(u_0)) . $$

The cyclographic image of the curve $C(u)$, $u \in I$, is then defined as

$$ \zeta(C(u)) = \bigcup_{u \in I} c(u) . $$

Depending on the tangent vectors of the curve $C(u)$, the one-parameter family of circles $c(u)$ may have a real envelope. If every tangent vector of $C(u)$ is time-like, the one-parameter family $c(u)$ does not possess a real envelope. The envelope has a single component if all of tangent vectors of $C(u)$ are light-like. In the case when $C(u)$ has only space-like and isolated light-like tangents, the one-parameter family possesses a real envelope with two branches $e_C^+(u)$ and $e_C^-(u)$, $u \in I$, that can be parameterized by

$$ e_C^{\pm}(u) = \begin{pmatrix} x \\ y \end{pmatrix} - r \frac{r' \begin{pmatrix} x' \\ y' \end{pmatrix} \pm \sqrt{x'^2 + y'^2 - r'^2} \begin{pmatrix} y' \\ -x' \end{pmatrix}}{x'^2 + y'^2}, \quad (4) $$

where $x, y$ and $r$ are functions of the parameter $u \in I$, see [19].

A point $e_C^\pm(u_0)$ for some $u_0 \in I$ is a singular point of the envelope curve $e_C^\pm(u)$, if

$$ \left. \frac{\partial e_C^{\pm}(u)}{\partial u} \right|_{u=u_0} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} . $$

*Remark.* If the radius function $r(u)$, $u \in I$, is constant, the singular points are the points $e_C^\pm(u_0)$ that satisfy

$$ |\kappa(u_0)| = \frac{1}{|r|}, $$

where $\kappa(u)$, $u \in I$, is the signed curvature of the spine curve $(x(u), y(u))^T$, $u \in I$, and $r = r(u)$, $u \in I$, is the constant radius. In particular, if

$$ \operatorname{sign}(\kappa(u_0)) \cdot \operatorname{sign}(r) = 1, $$

the singular point is the point $e_C^+(u_0)$, otherwise it is the point $e_C^-(u_0)$.

The cyclographic image of a curve segment $C(u) \subset \mathbb{R}^{2,1}$ parameterized over a closed interval $[a, b] \subset \mathbb{R}$ defines a domain $\Omega \subset \mathbb{R}^2$,

$$ \Omega = \zeta(C(u)) = \bigcup_{u \in [a, b]} c(u) . $$

The envelope curves $e_C^\pm(u)$, $u \in [a, b]$, (if they exist) and the cyclographic images of the endpoints $C(a)$ and $C(b)$ form a *pre-boundary* of the domain $\Omega$. Its boundary $\delta\Omega$ is then a subset of the pre-boundary, obtained by trimming the self-intersections, see Figure 1.
<figure><img src="image_3.png" /><figcaption>Figure 1: The cyclographic image of a curve segment in $\mathbb{R}^{2,1}$ is a planar domain (left). Its pre-boundary consists of the envelope curves (green and dark green) and cyclographic images of the endpoints of the curve segment (blue). The boundary of the domain is a subset of the pre-boundary (right).</figcaption></figure>

## 2.2. Minkowski circles and arcs

Two planar oriented circles $c_1, c_2$ are in oriented contact if they have a common point and share a tangent vector at this point. The corresponding points $C_1, C_2 \in \mathbb{R}^{2,1}$ have zero Minkowski distance, i.e., $\|C_1 - C_2\|_M = 0$.

A one parameter family of planar oriented circles that are all in oriented contact with two given oriented circles, defines a curve in the Minkowski space called a *Minkowski circle*. We extend this definition to more general situations. Furthermore, we review the rational parameterization for arcs of the Minkowski circles.

We consider the complex projective extension of Minkowski space $\mathbb{R}^{2,1}$. For a point $C = (x, y, r)^T \in \mathbb{R}^{2,1}$, we introduce its homogeneous coordinates $\tilde{C} = (\tilde{w} : \tilde{x} : \tilde{y} : \tilde{r})$.

The *absolute conic* is defined as the set of points at infinity, i.e., points that satisfy the equations

$$ \begin{aligned} \tilde{x}^2 + \tilde{y}^2 - \tilde{r}^2 &= 0, \\ \tilde{w} &= 0. \end{aligned} $$

A Minkowski circle $C$ is a non-degenerate conic that shares two points (with multiplicity) with the absolute conic. The plane in which the Minkowski circle $C$ lies determines its affine type. If the plane is

* space-like, $C$ is an ellipse (a),

* time-like, $C$ is a hyperbola with only space-like (b), or only time-like tangents (c),

* light-like, $C$ is a parabola (d).

The envelope of the one parameter family of oriented circles given by the Minkowski circle $C$ is composed of two oriented circles in the case (a) and (b), of an oriented circle and an oriented line, in the case (d), or, in the case (c), the family does not have a real envelope. Conversely, two oriented circles define a Minkowski circle of type (a) or (b). An oriented circle and an oriented line defines a Minkowski circle of type (d).
<figure><img src="image_4.png" /><figcaption>Figure 2: Affine types of Minkowski arcs and circles (red) and envelopes of the corresponding one parameter families of oriented circles (green).</figcaption></figure>

A Minkowski circle is uniquely determined by three distinct points $C_1, C_2, C_3 \in \mathbb{R}^{2,1}$, which define an arc on the Minkowski circle. We propose a quadratic parameterization of the Minkowski arc in the case when the difference vectors between the three points are not light-like.

**Proposition 1.** Let $C_1, C_2, C_3 \in \mathbb{R}^{2,1}$ be three points in the Minkowski space whose difference vectors are not light-like. Then

$$A(u) = \frac{w_1 C_1(u-1)(u-\frac{1}{2}) + w_2 C_2 u(u-1) + w_3 C_3 u(u-\frac{1}{2})}{w_1(u-1)(u-\frac{1}{2}) + w_2 u(u-1) + w_3 u(u-\frac{1}{2})}, \quad u \in [0,1], \quad (5)$$

where

$$w_1 = 2\|C_2 - C_3\|_M, \quad w_2 = -\|C_1 - C_3\|_M, \quad w_3 = 2\|C_1 - C_2\|_M, \quad (6)$$

is the Minkowski arc interpolating $C_1, C_2$ and $C_3$.

*Proof.* We embed the points $C_1, C_2, C_3$ into the projective extension of Minkowski space $\mathbb{R}^{2,1}$ by

$$C_i = (x_i, y_i, r_i)^T \mapsto \tilde{C}_i = (1: x_i: y_i: r_i), \quad i = 1, 2, 3,$$

and interpolate the points $\tilde{C}_i, i = 1, 2, 3$, by a Lagrange polynomial of degree 2 with the help of weights $a, b \in \mathbb{R}$, $a, b \neq 0$,

$$\tilde{A}(u) = \tilde{C}_1(u-1)(u-\frac{1}{2}) + a\tilde{C}_2u(u-1) + b\tilde{C}_3u(u-\frac{1}{2}) \\ = (\tilde{a}_w(u) : \tilde{a}_x(u) : \tilde{a}_y(u) : \tilde{a}_r(u)), \quad u \in [0,1].$$
Let $\mathbb{P}\mathbb{R}$ denote the projectively extended real line. The curve $\tilde{A}(u)$, $u \in [0, 1]$, is a Minkowski arc if there are two points $\tilde{A}(u_1)$, $\tilde{A}(u_2)$ on the curve $\tilde{A}(u)$, $u \in \mathbb{P}\mathbb{R}$, that lie on the absolute conic, i.e., the parameters $u_1, u_2$ satisfy the equations

$$ \begin{aligned} \tilde{a}_x^2(u) + \tilde{a}_y^2(u) - \tilde{a}_r^2(u) &= 0, \\ \tilde{a}_w(u) &= 0, \end{aligned} $$

where the first one is of degree 4 and the second one of degree 2 in $u$. Hence there exist some $q_0, q_1, q_2 \in \mathbb{R}$ such that

$$ \tilde{a}_x^2(u) + \tilde{a}_y^2(u) - \tilde{a}_r^2(u) - (q_0 + q_1 u + q_2 u^2) \tilde{a}_w(u) = 0 $$

Collecting the coefficients at $u^i$, $i = 0, 1, \dots, 4$, produces a system of 5 equations, from which we eliminate the parameters $q_0, q_1, q_2$. From the resulting equations we compute the weights $a$ and $b$, where the only possible combination where both of them are non-zero is

$$ a = - \frac{\|\mathbf{C}_1 - \mathbf{C}_3\|_M}{2\|\mathbf{C}_2 - \mathbf{C}_3\|_M} = \frac{w_2}{w_1}, \quad b = \frac{\|\mathbf{C}_1 - \mathbf{C}_2\|_M}{\|\mathbf{C}_2 - \mathbf{C}_3\|_M} = \frac{w_3}{w_1}, $$

which concludes the proof. $\square$

In [41] a quadratic rational Bézier parameterization of the Minkowski arc with three control points $P_1, P_2, P_3$ was suggested for the cases (a) and (b), when the Minkowski arcs have only space-like tangents. We propose an equivalent formulation.

**Proposition 2.** Let $\mathbf{P}_1, \mathbf{P}_2, \mathbf{P}_3 \in \mathbb{R}^{2,1}$ be three points in the Minkowski space such that $\|P_1 - P_3\|_M > 0$ and $\|P_1 - P_2\|_M > 0$ and $\|P_2 - P_1\|_M = \|P_3 - P_2\|_M$. Then

$$ A(u) = \frac{P_1(1-u)^2 + wP_22u(1-u) + P_3u^2}{(1-u)^2 + w2u(1-u) + u^2}, $$

where

$$ w = \frac{\sqrt{\|P_1 - P_3\|_M}}{2\sqrt{\|P_1 - P_2\|_M}}, $$

is the Minkowski arc satisfying

$$ A(0) = P_1, \quad A(1) = P_3, \tag{7} $$

and

$$ \frac{A'(0)}{\|A'(0)\|} = \frac{P_2 - P_1}{\|P_2 - P_1\|_M}, \quad \frac{A'(1)}{\|A'(1)\|} = \frac{P_3 - P_2}{\|P_3 - P_2\|_M}. \tag{8} $$

*Proof.* Following the same procedure as in the previous proof, we obtain the weight $w$. The weight is real and non-zero only if $\|P_1 - P_3\|_M > 0$ and $\|P_1 - P_2\|_M > 0$. The equations (7) and (8) follow from the properties of quadratic rational Bézier curves. $\square$
Next we consider biarcs in the Minkowski space. Given two points $P_1, P_2 \in \mathbb{R}^{2,1}$ and two unit space-like vectors $\mathbf{t}_1, \mathbf{t}_2$,

$$ \|\mathbf{t}_1\|_M = \|\mathbf{t}_2\|_M = 1, $$

we can construct a Minkowski biarc interpolating the data $(P_1, \mathbf{t}_1)$ and $(P_2, \mathbf{t}_2)$. The biarc consists of two Minkowski arcs $A_j^1(u)$ and $A_j^2(u)$, $u \in [0, 1]$, that satisfies

$$ \begin{gathered} A^1(0) = P_1, \quad A^2(1) = P_2, \\ \frac{A^{1'}(0)}{\|A^{1'}(0)\|_M} = \mathbf{t}_1, \quad \frac{A^{2'}(1)}{\|A^{2'}(1)\|_M} = \mathbf{t}_2, \end{gathered} $$

and are joined continuously with continuous tangents,

$$ A^1(1) = A^2(0) \quad \text{and} \quad \frac{A^{1'}(1)}{\|A^{1'}(1)\|_M} = \frac{A^{2'}(0)}{\|A^{2'}(0)\|_M}. $$

We compute the Minkowski biarc following the construction from [41]. The biarc is given by 5 Bézier control points

$$ (P_1, B_1, J, B_2, P_2), \qquad (9) $$

where

$$ B_1 = P_1 + \lambda_1 \mathbf{t}_1, \quad B_2 = P_2 - \lambda_2 \mathbf{t}_2, \quad \lambda_1, \lambda_2 \in \mathbb{R}, \quad \lambda_1 + \lambda_2 \neq 0, $$

such that

$$ \langle B_2 - B_1, B_2 - B_1 \rangle_M = (\lambda_1 + \lambda_2)^2, \qquad (10) $$

i.e., the points $P_1, B_1, J$ and $J, B_2, P_2$ form isosceles triangles (with respect to the Minkowski inner product). The joint point $J$ of the two Minkowski arcs is given by

$$ J = \frac{\lambda_2 B_1 + \lambda_1 B_2}{\lambda_1 + \lambda_2}. $$

Choosing the parameter $\lambda_1$, equation (10) gives a unique parameter $\lambda_2$. If $\lambda_1, \lambda_2 > 0$, the joint point $J$ lies between $B_1$ and $B_2$ and the Minkowski arcs lie inside of the triangles $P_1, B_1, J$ and $J, B_2, P_2$.

Furthermore, equation (10) ensures that the difference vectors $J - B_1$ and $B_2 - J$ are space-like for any $\lambda_1 \neq 0$:

$$ J - B_1 = \frac{\lambda_1(B_2 - B_1)}{\lambda_1 + \lambda_2}, $$

and hence

$$ \|J - B_1\|_M = \frac{\lambda_1^2 \|B_2 - B_1\|_M}{(\lambda_1 + \lambda_2)^2} = \lambda_1^2, $$

and similarly, $\|B_2 - J\|_M = \lambda_2^2$. Therefore, we can use Proposition 2 to parameterize the Minkowski biarc and its cyclographic image has a real envelope.
In this paper, we chose $\lambda_1 > 0$ such that

$$ \|P_1 - J\|_M = \|P_2 - J\|_M, $$

following the ‘equal chord’ biarc interpolation scheme for planar data [38].

Minkowski arc splines are defined to be curves in Minkowski space $\mathbb{R}^{2,1}$ composed of arcs of Minkowski circles.

Let $C(u) = (x(u), y(u), r(u))^T$, $u \in [0, 1]$, be a Minkowski arc with only space-like (or isolated light-like) tangents. We note that the envelope of the one parameter family of circles defined by $C(u)$ is formed by circular arcs or line segments. Two arcs are parts of the cyclographic images of the endpoints of the Minkowski arc. The other two arcs can be constructed as follows:

1. Let $\tau(u)$ be unit tangent vector at $C(u)$,

$$ \tau(u) = \frac{C'(u)}{\sqrt{\|C'(u)\|_M}}. $$

2. For $u^* \in \{0, 1\}$, we find the two light-like planes $\rho_{u^*}^{\pm}$ such that

* $C(u^*) \in \rho_{u^*}^{\pm}$, and

* $\tau(u^*) \in \rho_{u^*}^{\pm}$.

3. For $u^* \in \{0, 1\}$, we find the lines $\ell_{u^*}^{\pm}$ as the intersection of the planes $\rho_{u^*}^{\pm}$ and the plane $r = 0$,

$$ \ell_{u^*}^{\pm}(v) = \mathbf{q}_{u^*}^{\pm} + \mathbf{t}_{u^*}^{\pm}v, \quad v \in \mathbb{R}, \qquad (11) $$

such that $\mathbf{q}_{u^*}^{\pm} \in \mathbb{R}$, $\|\mathbf{t}_{u^*}^{\pm}\| = 1$, and the lines $\ell_{u^*}^{\pm}(v)$ are in oriented contact with the circle $\zeta(C(u^*))$, i.e., their unit tangent vectors coincide at the common points.

4. For $u^* \in \{0, 1\}$, we compute the points

$$ \mathbf{p}_{u^*}^{\pm} = (x(u^*), y(u^*))^T + r(u^*)(\mathbf{t}_{u^*}^{\pm})^{\perp}, \qquad (12) $$

where $(\mathbf{t}_{u^*}^{\pm})^{\perp}$ denotes the vector $(\mathbf{t}_{u^*}^{\pm})$ rotated by $\frac{\pi}{2}$ counterclockwise. Those are exactly the envelope points $e_C^{\pm}(u^*)$ from equation (4).

5. The rotations mapping the pairs $(\mathbf{p}_0^{\pm}, \mathbf{t}_0^{\pm})$ to the pairs $(\mathbf{p}_1^{\pm}, \mathbf{t}_1^{\pm})$ define the envelope arcs.

### 2.3. Medial axis transform

We recall the medial axis and the medial axis transform of an open set $\Omega \subset \mathbb{R}^2$.

**Definition 3.** Let $\Omega$ be an open set in $\mathbb{R}^2$ and $\delta\Omega$ its boundary. A closed disk $D \subset \mathbb{R}^2$ (possibly with a zero radius) is a maximal disk inscribed in $\Omega$, if

* $D \subseteq \Omega$, and if

* for any disk $D'$ satisfying $D \subseteq D'$ and $D' \subseteq \Omega$ it holds $D' = D$.
The boundary $\delta D$ of a maximal disk is called a maximal circle.

In $\mathbb{R}^2$ with the Euclidean metric, every maximal disk intersects $\delta\Omega$ in at least two points or it has a third order contact at points with stationary curvature.

**Definition 4.** Let $\Omega$ be an open set in $\mathbb{R}^2$. The *medial axis* of $\Omega$ is the union of the centres of all maximal disks inscribed in $\Omega$,

$$ \mathrm{MA}(\Omega) = \bigcup_{\substack{D \\ \text{maximal disk}}} \{(x_0, y_0)^T : \delta D \text{ has the equation } (x - x_0)^2 + (y - y_0)^2 = r_0^2\}. $$

The *medial axis transform* $\mathrm{MAT}(\Omega)$ of the set $\Omega$ also contains the information about radii of the maximal disks.

**Definition 5.** Let $\Omega$ be an open set in $\mathbb{R}^2$. The *medial axis transform* of $\Omega$ is defined as

$$ \mathrm{MAT}(\Omega) = \bigcup_{\substack{D \\ \text{maximal disk}}} \{(x_0, y_0, r_0)^T : \delta D \text{ has the equation } (x - x_0)^2 + (y - y_0)^2 = r_0^2\}. $$

We interpret the branches of $\mathrm{MAT}(\Omega)$ as curves $B_1(u), \dots, B_n(u)$, $n \in \mathbb{N}$, in Minkowski space $\mathbb{R}^{2,1}$ parameterized over a closed interval $I \subset \mathbb{R}$. The domain $\Omega$ is the union of the cyclographic images of the curves $B_i(u)$,

$$ \Omega = \bigcup_{i=1}^{n} \zeta(B_i(u)), $$

and its boundary is a subset of the boundaries of the domains $\zeta(B_i(u))$,

$$ \delta\Omega \subseteq \bigcup_{i=1}^{n} \delta\zeta(B_i(u)). $$

Note that if the branches $B_1(u), \dots, B_n(u)$ of the MAT are Minkowski arcs, then $\Omega$ is an arc spline domain, i.e., a domain whose boundary is composed of circular arcs and line segments.

### 3. Envelopes of evolving worms

In this section, we introduce worms and evolving worms. We characterize the supersets of the envelopes of the evolving worms as the boundaries of cyclographic images of certain curves in the Minkowski space.
<figure><img src="image_5.png" /><figcaption>Figure 3: A worm is a cyclographic image of a curve segment in Minkowski space $\mathbb{R}^{2,1}$.</figcaption></figure>

### 3.1. Evolving worms

First, we define worms with the help of the cyclographic mapping:

**Definition 6.** A planar domain $\Omega \subset \mathbb{R}^2$ is called a *worm* if it is the cyclographic image of a curve segment $B(u) : I \to \mathbb{R}^{2,1}$, where $I \subset \mathbb{R}$ is a closed interval,

$$ \Omega = \zeta(B(u)) . $$

The boundary $\delta\Omega$ is the boundary of the cyclographic image of the curve $B(u)$. If $I = [a, b]$, then it is composed of (parts of) the curves $e_B^{\pm}(u)$, $u \in [a, b]$, and of arcs of the cyclographic images of points $B(a)$ and $B(b)$, see Figure 3.

*Remark.* By Definition 6, any planar domain $\Omega$ can be considered as a worm. We can define $\Omega$ to be a *strong worm* if it holds

$$ \mathrm{MAT}(\Omega) = B(u), \quad u \in I, $$

where $B(u) : I \to \mathbb{R}^{2,1}$ and $I \subset \mathbb{R}$ is a closed interval.

When a worm $\Omega$ evolves over time $t$ and for each value of the time parameter its MAT is a single curve in $\mathbb{R}^{2,1}$, we call it an evolving worm.

**Definition 7.** An *evolving worm* is a one-parameter family of planar domains $\Omega(t)$, $t \in I_t$, such that for every $t_0 \in I_t$ the domain $\Omega(t_0)$ is a worm, i.e.,

$$ \Omega(t_0) = \zeta(B_{t_0}(u)) = \zeta(B(u, t_0)), $$

where $I_u, I_t \subset \mathbb{R}$ are closed intervals.

The union of the preimages $B_t(u)$ of the evolving worms $\Omega(t)$ over the time parameters $t \in I_t$ is a surface in Minkowski space $\mathbb{R}^{2,1}$,

$$ \bigcup_{t \in I_t} B_t(u) = \{B(u, t), u \in I_u, t \in I_t\}. $$
Remark. We can define a strong evolving worm to be a one-parameter family of planar domains $\Omega(t)$, $t \in I_t$, such that for every $t_0 \in I_t$ the domain $\Omega(t_0)$ is a strong worm, i.e.,

$$ \mathrm{MAT}(\Omega(t_0)) = \{B_{t_0}(u), u \in I_u\} = \{B(u, t_0), u \in I_u\}. $$

The union of the medial axis transforms of the strong evolving worms is again a surface in Minkowski space $\mathbb{R}^{2,1}$,

$$ \bigcup_{t \in I_t} \mathrm{MAT}(\Omega(t)) = \{B(u, t), u \in I_u, t \in I_t\}. $$

The envelope of the evolving worm $\Omega(t)$, $t \in [0, 1]$, is the envelope of a two-parameter family of oriented planar circles. If

$$ B(u, t) = (x(u, t), y(u, t), r(u, t))^T, \quad u, t \in [0, 1], $$

the circles are centred at $(x(u, t), y(u, t))^T$ and their radii are given by the function $r(u, t)$.

### 3.2. Envelope characterization

We characterize the envelope of an evolving worm. Let $\Omega(t)$, $t \in [0, 1]$, be an evolving worm represented by a smooth surface $B(u, t)$ in Minkowski space $\mathbb{R}^{2,1}$.

$$ B(u, t) = (x(u, t), y(u, t), r(u, t))^T, \quad u, t \in [0, 1]. $$

We identify singular curves on the surface $B(u, t)$. The cyclographic images of the singular curves contribute to the envelope of the evolving worm.

**Definition 8.** Let $B(u, t)$, $u, t \in [0, 1]$, be a surface in Minkowski space $\mathbb{R}^{2,1}$. A point $B(u_0, t_0)$, $u_0, t_0 \in [0, 1]$, is a singular point of $B(u, t)$, if the vectors

$$ \mathbf{v}_u(u_0, t_0) = \left. \frac{\partial B(u, t)}{\partial u} \right|_{u=u_0, t=t_0} \quad \text{and} \quad \mathbf{v}_t(u_0, t_0) = \left. \frac{\partial B(u, t)}{\partial t} \right|_{u=u_0, t=t_0} $$

are either linearly dependent or if they span a light-like plane.

Let $u_0, t_0 \in [0, 1]$. The restriction of the quadratic form defined by $G = \mathrm{diag}(1, 1, -1)$ on the tangent plane to $B(u, t)$ at the point $B(u_0, t_0)$ is defined by the 2 × 2 matrix

$$ M(u_0, t_0) = (\mathbf{v}_u, \mathbf{v}_t)^T G (\mathbf{v}_u, \mathbf{v}_t), $$

where $\mathbf{v}_u = \mathbf{v}_u(u_0, t_0)$ and $\mathbf{v}_t = \mathbf{v}_t(u_0, t_0)$.

The tangent plane is light-like if the quadratic form $M(u_0, t_0)$ is indefinite degenerate, that is,

$$ \det(M(u_0, t_0)) = 0. \qquad (13) $$

Equation (13) identifies the points of the surface $B(u, t)$ with light-like tangent planes as well as the second type of the singular points from Definition 8, i.e., the points where the tangent plane is not defined.
<figure><img src="image_6.png" /><figcaption>Figure 4: The singular (red) and the boundary (dark and light green) curves on a surface in the Minkowski space (left) and their cyclographic images (right).</figcaption></figure>

If $B(u, t)$ is piecewise rational surface, Equation (13) defines an algebraic curve in the parameter domain. Points $B(u_0, t_0)$ for $u_0, t_0 \in [0, 1]$, that satisfy Equation (13) then form the singular curves on the surface $B(u, t)$.

The envelope of the evolving worm $\Omega(t)$ then consists of boundaries of the cyclographic images of the singular curves and the boundary curves of the surface $B(u, t)$. This fact was noted in [42]. Here we present a formal proof.

**Theorem 3.** The envelope of an evolving worm $\Omega(t)$, $t \in [0, 1]$, given by the surface

$$B(u, t) : [0, 1]^2 \to \mathbb{R}^{2,1},$$

is a subset of the cyclographic images of the boundary curves

$$B(u, 0), B(u, 1), \quad u \in [0, 1],$$

$$B(0, t), B(1, t), \quad t \in [0, 1],$$

and of the cyclographic images of the singular curves.

*Proof.* We denote $B(u, t) = (x(u, t), y(u, t), r(u, t))$, $u, t \in [0, 1]$. The surface defines a two parameter family of planar circles $p$, which can be parameterized with the help of three parameters $u, t \in [0, 1]$ and $\varphi \in [0, 2\pi)$,

$$p(u, t, \varphi) = \begin{pmatrix} x(u, t) \\ y(u, t) \end{pmatrix} + r(u, t) \begin{pmatrix} \cos \varphi \\ \sin \varphi \end{pmatrix}.$$

The boundary curves correspond to the families of circles

$$p(u, 0, \varphi), p(u, 1, \varphi), \quad u \in [0, 1], \varphi \in [0, 2\pi),$$

$$p(0, t, \varphi), p(1, t, \varphi), \quad t \in [0, 1], \varphi \in [0, 2\pi),$$
and the cyclographic images of the boundary curves are envelopes of these families of circles, that clearly correspond to the envelope of $\Omega(t)$.

Let $u, t \in (0, 1)$. Any point of the envelope of the two parameter family of circles $p(u, t, \varphi)$ satisfies the envelope condition (see e.g. [42]):

$$ \mathrm{rank} \left( \frac{\partial p}{\partial u}, \frac{\partial p}{\partial t}, \frac{\partial p}{\partial \varphi} \right) < 2 . $$

The Jacobian matrix is rank deficient iff

$$ \det \left( \frac{\partial p}{\partial u}, \frac{\partial p}{\partial \varphi} \right) = 0 \quad \text{and} \quad \det \left( \frac{\partial p}{\partial t}, \frac{\partial p}{\partial \varphi} \right) = 0 , $$

i.e., if the following equations hold

$$ r x_u \cos \varphi + r r_u \cos^2 \varphi + r y_u \sin \varphi + r r_u \sin^2 \varphi = 0 , $$

$$ r x_t \cos \varphi + r r_t \cos^2 \varphi + r y_t \sin \varphi + r r_t \sin^2 \varphi = 0 , $$

where $r = r(u, t)$ and

$$ x_u = \frac{\partial x(u, t)}{\partial u}, \quad y_u = \frac{\partial y(u, t)}{\partial u}, \quad r_u = \frac{\partial r(u, t)}{\partial u} , $$

$$ x_t = \frac{\partial x(u, t)}{\partial t}, \quad y_t = \frac{\partial y(u, t)}{\partial t}, \quad r_t = \frac{\partial r(u, t)}{\partial t} . $$

Eliminating the parameter $\varphi$ from the equations above yields the equation

$$ -r \left( (x_u y_t - x_t y_u)^2 - (x_u r_t - x_t r_u)^2 - (y_u r_t - y_t r_u)^2 \right) \quad (14) $$

which is exactly the equation (13) multiplied by $-r$. Hence we see that the points that satisfy the envelope condition are the points of the cyclographic images of the singular points and the circles of the two parameter family which have zero radii. $\square$

## 4. Minkowski arc interpolation of curves in $\mathbb{R}^{2,1}$

The envelope of an evolving worm consists of boundaries of cyclographic images of certain curves in $\mathbb{R}^{2,1}$. We present and compare two pairs of methods for curve interpolation in the Minkowski space by Minkowski arcs either *directly*, or *indirectly*, by interpolating the boundaries of the cyclographic images of the original curves. In both cases, we interpolate the curve or the boundary of its cyclographic image either by (Minkowski) arcs or (Minkowski) biarcs. The resulting envelope of the evolving worm is then an arc spline.

We consider curves with space-like tangents only. Light-like tangents may be present at endpoints. The four schemes described below need to be modified to deal with these points. This is described in the appendix of the paper.
### 4.1. First pair: direct methods

Let $\Omega \subset \mathbb{R}^2$ be a worm and let $C(v), v \in [0, 1]$, be a curve in Minkowski space $\mathbb{R}^{2,1}$ such that

$$ \Omega = \zeta(C(v)) . $$

The direct methods interpolate the curve $C(v)$ by Minkowski (bi)arcs. The boundaries of the cyclographic images of interpolants are composed of circular arcs and approximate the boundary $\delta\Omega$. The MAT of the approximated worm is an Minkowski arc spline.

We assume that the curve $C(v)$ has only space-like or isolated light-like tangents, i.e., the worm $\Omega$ is the cyclographic image of the whole curve $C(v)$.

We choose $N \in \mathbb{N}$ and sample points on the curve $C(v), v \in [0, 1]$, at $N + 1$ parameter values

$$ 0 = v_0 < v_1 < \cdots < v_N = 1 , $$

and denote the samples

$$ C_j = C(v_j), \quad j = 1, \dots, N . $$

We interpolate segments of the curve $C(v)$ by Minkowski arcs (direct arc interpolation, **DAI**), or by Minkowski biarcs (direct biarc interpolation, **DBI**). Then we compute the boundaries of the cyclographic images of the Minkowski (bi)arcs exactly. These curves are composed of circular arcs and approximate the boundary of the worm $\Omega$.

#### Direct arc interpolation

We interpolate segments of the curve $C(v), v \in [0, 1]$, in Minkowski space $\mathbb{R}^{2,1}$ by Minkowski arcs and approximate the boundary of the worm $\Omega$ by the boundaries of the cyclographic images of the Minkowski arcs.

#### Method DAI[$C(v), N$]

**Input:** Curve $C(v), v \in [0, 1]$, in $\mathbb{R}^{2,1}$ with only space-like or isolated light-like tangents, $N \in \mathbb{N}$ even.

**Output:** Superset of the boundary of the domain $\tilde{\Omega}$ that approximates the worm $\Omega$, $\mathrm{MAT}(\Omega) = \{C(v), v \in [0, 1]\}$.

1. Sample the curve $C(v), v \in [0, 1]$, at $N + 1$ parameter values

$$ 0 = v_0 < v_1 < \cdots < v_N = 1 . $$

2. Compute points $C_j = C(v_j), j = 1, \dots, N$.

3. For each $k = 0, 1, \dots, \frac{N}{2} - 1$, interpolate the three consecutive points

$$ C_{2k}, C_{2k+1}, C_{2k+2}, $$

by a Minkowski arc $\tilde{C}_k(v), v \in [0, 1]$, according to Proposition 1.

4. For each $k = 0, 1, \dots, \frac{N}{2} - 1$, compute the cyclographic image $\zeta(\tilde{C}_k(v)), v \in [0, 1]$.
5. The boundary of the domain $\tilde{\Omega}$ is a subset of the boundaries of the cyclographic images,

$$ \delta\tilde{\Omega} \subseteq \bigcup_{k=0}^{\frac{N}{2}-1} \{\delta\zeta(\tilde{C}_k(v)), v \in [0, 1]\}. $$

The approximated worm $\tilde{\Omega}$ is then a cyclographic image of the Minkowski arc spline

$$ \tilde{C}(v) = \tilde{C}_k \left( \frac{N}{2}v - \frac{2k}{N} \right), \quad v \in \left[ \frac{2k}{N}, \frac{2k+2}{N} \right], $$

where $k = 0, 1, \dots, \frac{N}{2} - 1$. The Minkowski arc spline $\tilde{C}(v)$, $v \in [0, 1]$, is $C^0$ continuous at the points $C_{2k}$ for $k = 1, \dots, \frac{N}{2} - 1$. However, the endpoints of the envelope curves of two consecutive segments $\tilde{C}_k(v)$ and $\tilde{C}_{k+1}(v)$ do not generally coincide. Therefore we need to include also the cyclographic images of the endpoints $C_k(0)$ and $C_k(1)$ of the Minkowski arc spline segments $\tilde{C}_k(v)$, $v \in [0, 1]$, for $k = 1, \dots, \frac{N-1}{2}$, to approximate the whole boundary of the worm $\Omega$.

### Direct biarc interpolation

We interpolate segments of the curve $C(v)$, $v \in [0, 1]$, in Minkowski space $\mathbb{R}^{2,1}$ by Minkowski biarcs and approximate the boundary of the worm $\Omega$ by the boundaries of the cyclographic images of the Minkowski biarcs.

### Method DBI[$C(v), N$]

**Input:** Curve $C(v)$, $v \in [0, 1]$, in $\mathbb{R}^{2,1}$ with only space-like or isolated light-like tangents, $N \in \mathbb{N}$.

**Output:** Superset of the boundary of the domain $\tilde{\Omega}$ that approximates the worm $\Omega$, $MAT(\Omega) = \{C(v), v \in [0, 1]\}$.

1. Sample the curve $C(v)$, $v \in [0, 1]$, at $N + 1$ parameter values

$$ 0 = v_0 < v_1 < \dots < v_N = 1. $$

2. Compute points $C_j = C(v_j)$, $j = 1, \dots, N$.

3. At each point $C_j$, $j = 0, 1, \dots, N$, compute the normalized tangent vector $t_j$ of the curve $C(v)$,

$$ t_j = \frac{C'(v_j)}{\sqrt{\|C'(v_j)\|_M}}. $$

4. For each $j = 0, 1, \dots, N - 1$, we compute the control points of a Minkowski biarc that interpolates the consecutive pairs of data

$$ (C_j, t_j) \quad \text{and} \quad (C_{j+1}, t_{j+1}) $$

and parameterize the arcs of the biarc $\tilde{C}_j(v)$, $v \in [0, 1]$, according to Proposition 2.
5. For each $j = 0, 1, \dots, N-1$ we compute the envelope curve

$$e_{\tilde{C}_j}^{\pm}(v), v \in [0, 1].$$

6. The boundary of the domain $\tilde{\Omega}$ is a subset of the envelope curves and arcs of the cyclographic images of $C_0$ and $C_N$,

$$\delta\tilde{\Omega} \subseteq \bigcup_{j=0}^{N-1} \left\{ e_{\tilde{C}_j}^{\pm}(v), v \in [0, 1] \right\} \cup \zeta(C_0) \cup \zeta(C_N).$$

Note that as we assume all the tangents of the curve $C(v)$, $v \in [0, 1]$, to be space-like, we can always normalize them.

The approximated worm $\tilde{\Omega}$ is then a cyclographic image of the Minkowski arc spline

$$\tilde{C}(v) = \tilde{C}_j \left( Nv - \frac{j}{N} \right), \quad v \in \left[ \frac{j}{N}, \frac{j+1}{N} \right],$$

where $j = 0, 1, \dots, N-1$. The Minkowski arc spline is $G^1$ continuous and the envelope curves $e_{\tilde{C}}^{\pm}(v)$, $v \in [0, 1]$, are planar circular arc splines and are $C^1$ continuous at the points $C_j$ for $j = 2, \dots, N-1$.

## 4.2. Second pair: indirect methods

Let $\Omega \subset \mathbb{R}^2$ be a worm and let $C(v)$, $v \in [0, 1]$, be a curve in Minkowski space $\mathbb{R}^{2,1}$ such that

$$\Omega = \zeta(C(v)).$$

The indirect methods interpolate the boundary $\delta\Omega$, more specifically the envelope curves $e_{\tilde{C}}^{\pm}$, by planar circular (bi)arcs. The approximated worm is then a cyclographic image of a geometric graph in $\mathbb{R}^{2,1}$, which has Minkowski arcs as its branches.

We assume that the curve $C(v)$ has only space-like or isolated light-like tangents. Furthermore, we assume that the envelope curves $e_{\tilde{C}}^{\pm}(v)$, $v \in [0, 1]$, do not have any singular points.

We choose $N \in \mathbb{N}$ and sample the curve $C(v)$, $v \in [0, 1]$, at $N+1$ parameter values

$$0 = v_0 < v_1 < \dots < v_N = 1,$$

and we compute the corresponding envelope points

$$e_j^{\pm} = e^{\pm}(v_j), \quad j = 0, \dots, N.$$

We interpolate the envelope points by planar circular arcs (indirect arc interpolation, **IAI**), or planar biarcs (indirect biarc interpolation, **IBI**). These curves form the boundary $\delta\tilde{\Omega}$ of the domain $\tilde{\Omega}$ which approximates the worm $\Omega$.

The arc spline $\delta\tilde{\Omega}$ approximates the boundary $\delta\Omega$ with approximation order 3, see [38].
### Indirect arc interpolation

We interpolate segments of the envelope curves $e_C^±(v)$ of the curve $C(v)$, $v \in [0, 1]$, by planar circular arcs.

### Method IAI[$C(v), N$]

**Input:** Curve $C(v)$, $v \in [0, 1]$, in $\mathbb{R}^{2,1}$ with only space-like or isolated light-like tangents, such that $e_C^±(v)$, $v \in [0, 1]$, has no singular points, $N \in \mathbb{N}$ even.

**Output:** Superset of the boundary of the domain $\tilde{\Omega}$ that approximates the worm $\Omega$, $MAT(\Omega) = \{C(v), v \in [0, 1]\}$.

1. Sample the curve $C(v)$, $v \in [0, 1]$, at $N + 1$ parameter values

$$0 = v_0 < v_1 < \dots < v_N = 1.$$

2. For each $j = 0, 1, \dots, N$, compute the envelope points

$$e_j^± = e^±(v_j), \quad j = 0, \dots, N.$$

3. For each $k = 0, 1, \dots, \frac{N}{2} - 1$, interpolate the three consecutive points

$$e_{2k}^+, e_{2k+1}^+, e_{2k+2}^+,$$

by a planar circular arc $\tilde{e}_k^±(v)$, $v \in [0, 1]$.

4. The boundary of the domain $\tilde{\Omega}$ is a subset of the envelope curves $\tilde{e}_k^±(v)$, $v \in [0, 1]$, and arcs of the cyclographic images of $C_0 = C(0)$ and $C_N = C(1)$,

$$\delta \tilde{\Omega} \subseteq \bigcup_{k=0}^{\frac{N}{2}-1} \{\tilde{e}_k^±(v), v \in [0, 1]\} \cup \zeta(C_0) \cup \zeta(C_N).$$

The arc splines

$$\tilde{e}^±(v) = \tilde{e}_k^±(v) \left( \frac{N}{2}v - \frac{2k}{N} \right), \quad v \in \left[ \frac{2k}{N}, \frac{2k+2}{N} \right],$$

where $k = 0, 1, \dots, \frac{N}{2} - 1$, are $C^0$ continuous at the points $e_{2k+1}^±$, $k = 1, \dots, \frac{N-3}{2}$.

The MAT of the domain $\tilde{\Omega}$ is a geometric graph whose branches are Minkowski arcs.

### Indirect biarc interpolation

We interpolate segments of the envelope curves $e^±(v)$ of the curve $C(v)$, $v \in [0, 1]$, by planar biarcs.

### Method IBI[$C(v), N$]

**Input:** Curve $C(v)$, $v \in [0, 1]$, in $\mathbb{R}^{2,1}$ with only space-like or isolated light-like tangents, such that $e_C^±(v)$, $v \in [0, 1]$ has no singular points, $N \in \mathbb{N}$ even.

**Output:** Superset of the boundary of the domain $\tilde{\Omega}$ that approximates the worm $\Omega$, $MAT(\Omega) = \{C(v), v \in [0, 1]\}$.
1. Sample the curve $C(v)$, $v \in [0, 1]$, at $N + 1$ parameter values

$$0 = v_0 < v_1 < \dots < v_N = 1.$$

2. For each $j = 0, 1, \dots, N$, compute the envelope points

$$e_j^{\pm} = e^{\pm}(v_j), \quad j = 0, \dots, N.$$

3. For each $j = 0, 1, \dots, N$, compute the unit tangent vectors $\mathbf{t}_j^{\pm}$ of the envelope curves $e_C^{\pm}(v)$ at the points $e_j^{\pm}$.

4. For every $j = 0, 1, \dots, N$, compute biarcs $\tilde{e}_j^{\pm}(v)$, $v \in [0, 1]$, interpolating the pairs

$$(e_j^{\pm}, \mathbf{t}_j^{\pm}) \quad \text{and} \quad (e_{j+1}^{\pm}, \mathbf{t}_{j+1}^{\pm}).$$

5. The boundary of the domain $\tilde{\Omega}$ is a subset of the envelope curves $\tilde{e}_j^{\pm}(v)$, $v \in [0, 1]$, and arcs of the cyclographic images of $C_0 = C(0)$ and $C_N = C(1)$,

$$\delta \tilde{\Omega} \subseteq \bigcup_{j=0}^{N-1} \{\tilde{e}_j^{\pm}(v), v \in [0, 1]\} \cup \zeta(C_0) \cup \zeta(C_N).$$

The arc splines

$$\tilde{e}^{\pm}(v) = \tilde{e}_j^{\pm}(v) \left( \frac{N}{2}v - \frac{j}{N} \right), \quad v \in \left[ \frac{j}{N}, \frac{j+1}{N} \right],$$

where $k = 0, 1, \dots, N - 1$, are $G^1$ continuous

In general, the MAT of the domain $\tilde{\Omega}$ is a geometric graph with Minkowski arcs as branches.

### 4.3. Comparison of the methods

We compare the four methods **DAI**, **DBI**, **IAI**, and **IBI** for the approximation of the boundary of the worm $\Omega$ whose MAT is represented by a curve $C(v)$, $v \in [0, 1]$, with respect to the number of arcs, approximation power and continuity. The results are summarized in Table 1.

Let $N \in \mathbb{N}$ be an even number. We sample the interval $[0, 1]$ uniformly and $N + 1$ parameter values and denote $h = \frac{1}{N}$.

#### Number of arcs

The methods described above return the superset of the arcs that approximate the boundary of worm $\Omega$. These arcs are the input for the sweep line algorithm that extracts the real envelope. We compare the cardinality of the supersets, which gives an upper bound of the number of arc in the approximated boundary.
<figure><img src="image_7.png" /><figcaption>Figure 5: Comparison of methods for approximation of curves in $\mathbb{R}^{2,1}$ by Minkowski arcs for $N = 4$.</figcaption></figure>

**DAI:** We interpolate the curve $C(v)$ by $\frac{N}{2}$ Minkowski arcs. The boundaries of the cyclographic images of the Minkowski arcs are not continuous, hence we need to include $N - 1$ arcs of the circles

$$ \zeta(C(ih)) \quad \text{for } i = 1, 2, \dots, \frac{N}{2} - 1, $$

and the two arcs of the circles $\zeta(C(0))$ and $\zeta(C(1))$. In total the number of arcs in the boundary $\delta\tilde{\Omega}$ is bounded by

$$ 2\left(\frac{N}{2}\right) + 2\left(\frac{N}{2} - 1\right) + 2 = 2N. $$

**DBI:** We interpolate the curve $C(v)$ by $N$ Minkowski biarcs, whose envelopes are composed of $4N$ arcs. Adding the two arcs of the cyclographic images $\zeta(C(0))$ and $\zeta(C(1))$ of the endpoints of the curve, we obtain $4N + 2$ circular arcs in total.

**IAI:** We interpolate each of the envelope curves $e_C^{\pm}(v)$ by $\frac{N}{2}$ arcs. Adding the two arcs of the circles $\zeta(C(0))$ and $\zeta(C(1))$ yields $N + 2$ arcs.

**IBI:** We interpolate each of the envelope curves $e_C^{\pm}(v)$ by $N$ biarcs. Together with the two arcs of the circles $\zeta(C(0))$ and $\zeta(C(1))$ we obtain $4N + 2$ arcs.

## Approximation power

The indirect methods **IAI** and **IBI** approximate the boundary of the worm $\Omega$ with approximation order 3. The direct methods **DAI** and **DBI** approximate the boundary
<figure><img src="image_8.png" /><figcaption>Figure 6: The indirect methods **IAI** and **IBI** approximate the boundary of a worm with approximation order 3. The direct methods **DAI** and **DBI** approximate the boundary with approximation order 2.</figcaption></figure>

only with approximation order 2. We consider the error with respect to the number of segments, or number of arcs (Figure 6, right). Among the methods considered, the **IAI** method generates the lowest number of arcs for a given accuracy.

Continuity of $\delta\tilde{\Omega}$

Regarding the continuity, the boundary $\delta\tilde{\Omega}$ is $C^0$ continuous for the methods **DAI** and **IAI** and $C^1$ continuous in the case of the methods **DBI** and **IBI**.

<table><caption>Table 1: Comparison of the methods for interpolating curves in $\mathbb{R}^{2,1}$.</caption><thead><tr><th></th><th>DAI</th><th>DBI</th><th>IAI</th><th>IBI</th></tr></thead><tbody><tr><td># of arcs</td><td>2N</td><td>4N + 2</td><td>N + 2</td><td>4N + 2</td></tr><tr><td>continuity</td><td>C<sup>0</sup></td><td>C<sup>1</sup></td><td>C<sup>0</sup></td><td>C<sup>1</sup></td></tr><tr><td>approximation power</td><td>2</td><td>2</td><td>3</td><td>3</td></tr></tbody></table>

In summary, when deciding which method to use, we can follow the guidelines outlined here:

* **IBI** offers the best option when $C^1$ smoothness is desired.

* **IAI** produces the lowest number of arcs for a given precision.
<figure><img src="image_9.png" /><figcaption>Figure 7: The adaptive approach for the **IAI** method results in lower errors for the same number of arcs.</figcaption></figure>

• **DAI** is the simplest method, which does not require additional effort in the case when tangent vectors of the curve $C(v) \in \mathbb{R}^{2,1}$ are close to light-like vectors (see Appendix for more details).

### 4.4. Adaptive sampling

In practice, better results are obtained by sampling the curve $C(v)$, $v \in [0, 1]$, adaptively rather than uniformly. For the sake of brevity, we focus on the **IAI** method, which was found to produce the lowest number of arcs for a given accuracy when uniform sampling was used. We present a simple adaptive procedure based on a user-defined parameter $\delta$. The adaptive procedure could be formulated similarly for the other three methods.

1. Sample the curve $C(v)$, $v \in [v_0, v_1]$, at the parameter values $v_0, \frac{v_0+v_1}{2}, v_1$.

2. Compute the envelope points $e_j^{\pm} = e^{\pm}(v_j)$, $j = 0, \frac{1}{2}, 1$.

3. Interpolate the three envelope points by a planar circular arcs $\tilde{e}^{\pm}(v)$, $v \in [0, 1]$.

4. Compute the maximal distances $d^{\pm}$ between the envelope curves $e^{\pm}$ and their approximations $\tilde{e}^{\pm}$.

5. If $d^{\pm} > \delta$, divide the interval in half and repeat the procedure on both intervals $[v_0, \frac{v_0+v_1}{2}]$ and $[\frac{v_0+v_1}{2}, v_1]$ on the branch $e^+(v)$ or $e^-(v)$ of the envelope curves.

We can obtain lower errors for the same number of arcs using the adaptive sampling method. Figure 7 shows an example of a worm approximated by the uniform **IAI** method (left, top) and the adaptive **IAI** method (left, bottom). To achieve the same error, the adaptive method needs less arcs. In the example, the error is 0.05, and the envelope obtained by sampling uniformly uses 36 circular arcs, while the adaptive approach needs only 24 arcs. A similar behavior was observed previously in [44] for a different application of arc splines, where the approximation of envelopes of envelopes of planar swept volumes can be improved by a constant factor when adaptive sampling is used. However, this does not affect the overall rate of convergence.
<figure><img src="image_10.png" /><figcaption>Figure 8: Curves in the parameter domain define the boundary (green) and the singular (red) curves (left). The approximation of the evolving worm using the method **IBI** and $N = 4$ (centre). The boundaries of the cyclographic images of the boundary curves $B(u, 0)$, $B(u, 1)$, the boundary curves $B(0, t)$, $B(1, t)$ and the singular curves are depicted in blue, their approximations in light green, dark green and red, respectively. The envelope of the evolving domain is a subset of the boundaries of the cyclographic images (right).</figcaption></figure>

## 5. Envelope computation

In this section we describe the computation of the envelope of an evolving worm using one of the four method presented above.

Let $\Omega(u, t)$, $u, t \in [0, 1]$, be an evolving worm defined by a piecewise smooth rational surface $B(u, t)$, $u, t \in [0, 1]$, in Minkowski space $\mathbb{R}^{2,1}$. By Theorem 3 we know that the envelope of $\Omega(u, t)$ is a subset of the boundaries of the cyclographic images of the boundary and the singular curves on the surface $B(u, t)$. To approximate the boundary curves, can we simply use one of the methods **DAI**, **DBI**, **IAI** or **IBI** for the curves

$$ \begin{aligned} B(u, 0), B(u, 1), \quad &u \in [0, 1], \\ B(0, t), B(1, t), \quad &t \in [0, 1]. \end{aligned} $$

The singular curves are defined by Equation (13). The equation defines an algebraic curve in the parameter domain. Adapting a method for tracing algebraic curves from [34], we trace points $(u_i, t_i)^T$ on the curve in the parameter domain and tangent vectors $v^i = (v_u^i, v_t^i)^T$ at those points. From this data, we recover the singular points $\mathbf{p}^i = B(u_i, t_i)^T$ on the surface $B(u, t)$ and tangent vectors

$$ \tau^i = v_u^i \cdot \left( \frac{\partial B}{\partial u} \right)^\perp \Big|_{u=u_i, t=t_i} + v_t^i \cdot \left( \frac{\partial B}{\partial t} \right)^\perp \Big|_{u=u_i, t=t_i} . $$

We divide the singular curves into segments with space-like, light-like and time-like tangents and only consider those with space-like tangents and possibly light-like tangents at the endpoints. The segments with time-like tangents do not correspond to a real envelope and hence we do not need to consider them further.

To approximate the singular curve using the method **DAI**, we only need the points $\mathbf{p}^i$. For the other methods, we also need the tangent vectors $\tau^i$. For the method **IBI**, the
tangent vectors $t^i$ of the envelope points are also necessary, see Equations (11) and (12) for the construction of the tangent vectors and the envelope points.

Figure 8 (left) shows the singular and the boundary curves on the surface $B(u, t)$ depicted in Figure 4 in the parameter domain. We sampled 5 points on the curves and computed the Hermite data on the envelope curves to approximate the envelope of the envelope of the evolving worm using the method **IBI**. The outer envelope can be extracted after computing intersections of the biarcs using a line sweep algorithm, see Figure 8 (right).

# 6. Envelopes of evolving free-form domains

We apply the developed method for computation of envelopes of evolving worm to evolving free-form domains.

<figure><img src="image_11.png" /><figcaption>Figure 9: Evolving planar domain which is composed of 9 evolving worms.</figcaption></figure>

## 6.1. Free-form domains

We interpret a free-form domain $\Omega \subset \mathbb{R}^2$ as a union of worms, e.g., the cyclographic images of the branches of the MAT($\Omega$). Let $B_1(u), \dots, B_n(u)$ for some $n \in \mathbb{N}$ and $u \in [0, 1]$ be curves in Minkowski space $\mathbb{R}^{2,1}$,

$$B_i(u) : [0, 1] \to \mathbb{R}^{2,1}.$$

Each curve $B_i(u)$ defines a worm $\Omega_i$,

$$\Omega_i = \zeta(B_i(u)),$$

and the domain $\Omega$ is the union of the worms

$$\Omega = \bigcup_{i=1}^{n} \zeta(B_i(u)) = \bigcup_{i=1}^{n} \Omega_i.$$

A free-form domain $\Omega(t)$ evolving in time $t \in [0, 1]$, is then represented as a union of evolving worms. Each of the evolving worms

$$B_1(u, t), \dots, B_n(u, t),$$
<figure><img src="image_12.png" /><figcaption>(10a) The singular curves in the parameter domain corresponding to three different evolving worms.</figcaption></figure>

defines a surface in the Minkowski space,

$$B_i(u, t) : [0, 1]^2 \to \mathbb{R}^{2,1}, \quad i = 1, \dots, n.$$

We assume that for any $i = 1, \dots, n$, there exists an interval $\bar{I}_i \subset [0, 1]$ such that for each $t_0 \in \bar{I}_i$, the curve $B_i(u, t_0)$, $u \in [0, 1]$, has non-zero length.

## 6.2. Envelope computation

To compute the envelope of an evolving free-form domain $\Omega(t)$, $t \in [0, 1]$, we consider each of the evolving worms separately. The procedure consists of the following two steps:

1. For every $i = 1, \dots, n$, we approximate the envelope of the evolving worm $\Omega_i$ separately. That is, on each surface

$$B_i(u, t), \quad u, t \in [0, 1],$$

we identify the boundary and the singular curves and approximate them (and their cyclographic images) using one of the methods **DAI**, **DBI**, **IAI** or **IBI**.

2. The envelope of the evolving domain $\Omega(t)$ is a subset of the envelopes of the evolving worms $\Omega_i(t)$. We extract the envelope of the evolving planar domain $\Omega(t)$. Using a variant of the sweep-line algorithm for circular arcs, see [8], we compute intersections of the envelope curves and extract the outer envelope of the evolving domain.

## 6.3. Examples

The method for calculating the envelopes of evolving free-form domains is illustrated by the following three examples.

**Example 1.** Consider the evolving domain from Figure 9. At each time parameter, the domain is a union of 9 worms. The evolving worms form surfaces

$$B_i(u, t) : [0, 1]^2 \to \mathbb{R}^{2,1}, \quad i = 1, \dots, 9.$$

Several worms evolve from a point into a curve of non-zero length.
<figure><img src="image_13.png" /><figcaption>(10b) Superset of the envelope of the evolving domain consists of boundaries of cyclographic images of the singular (thick) and the boundary curves. The outer envelope is shown in black.</figcaption></figure>

<caption>Figure 10: Example 1.</caption>

We approximate each evolving branch separately, by approximating the worms corresponding to the boundary and the singular curves of each of the surfaces

$$B_i(u, t), \quad i = 1, \dots, 9.$$

In this example, the only evolving worms with singular curves are those shown in dark green, light green and yellow (see Figure 10a and 10b). We approximate the boundaries of the cyclographic images of the singular curves and of the boundary curves using the method **IBI**. In this case, the cyclographic images of the singular curves do not contribute to the envelope of the evolving domain and are trimmed away. The envelope of the evolving domain is then extracted from the interpolations of the cyclographic images of the boundary curves.

*Example 2.* Let $\Omega(t)$, $t \in [0, 1]$ be the evolving domain shown in Figure 11a. At each time instance, the domain is a union of three worms. In this case, the MAT of each worm has a non-zero length at each time parameter.

We approximate every evolving branch separately. For each $i = 1, 2, 3$, we identify the

<figure><img src="image_14.png" /><figcaption>(11a) Evolving planar domain $\Omega(t)$. At every $t \in [0, 1]$ it consists of three worms.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(11b) The outer envelope of $\Omega(t)$.</figcaption></figure>
<figure><img src="image_16.png" /><figcaption>(11c) The superset of the envelope consists of boundaries of cyclographic images of both the singular (thick) and the boundary curves.</figcaption></figure>

<caption>Figure 11: Example 2.</caption>

boundary and the singular curves on the surface

$$B_i(u, t), \quad (u, t) \in [0, 1]^2.$$

and approximate the corresponding worms using the method **IBI**. The cyclographic images of the singular curves are necessary to approximate the envelope of the evolving domain, approximately 32 % of the envelope arcs are contributed by the singular curves. Figure 11c shows the superset of the envelope with highlighted cyclographic images of the singular curves and Figure 11b depicts the extracted outer envelope, where the arcs contributed by the singular curves are highlighted.

*Example 3.* The presented method allows us to compute envelopes of evolving domains, where the number of components changes. The domain in Figure 12a is composed of two worms at each instance of the time parameter. At the beginning, the worms are connected, and as the domain evolves, they separate, creating two components. We identify the boundary and the singular curves on both surfaces in the Minkowski space and again use the method **IBI** to approximate the envelope. Figure 12b shows the boundaries of the cyclographic images of the boundary curves of the both worms. To obtain the whole envelope, we also need to consider the singular curves. Figure 12c shows the extracted envelope of the evolving domain, where the boundaries of the cyclographic images of the singular curves of both worms are highlighted. In this example, approximately 14 % of the envelope arcs are contributed by the singular curves.

## 7. Conclusion

We presented a procedure for approximating the envelope of planar domains that evolve in time. First, we considered worms, which are cyclographic images of single curve seg-
<figure><img src="image_17.png" /><figcaption>(12a) Evolving domain composed of two worms. At five instances of the time parameter, the worms and their MA are depicted.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(12b) Boundaries of the cyclographic images of the boundary curves.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>(12c) Extracted outer envelope (black) and the boundaries of the cyclographic images of the singular curves.</figcaption></figure>

<caption>Figure 12: Example 3.</caption>

ments in $R^{2,1}$. We characterized the envelopes of evolving worms as subsets of cyclographic images of finitely many curves in Minkowski space. We then proposed two pairs of methods to approximate these curves and their cyclographic images by arc splines. The methods exploit geometric flexibility and computational simplicity of circular arcs to efficiently and precisely approximate the envelopes. We considered free-form domains to be unions of worms. Finally, the envelope of an evolving (free-form) domain was obtained by trimming the redundant curves efficiently using a line sweep algorithm that again utilized the properties of circular arcs.

## Appendix: Points with light-like tangents

In Section 4, we presented four methods for approximation curves in the Minkowski space $R^{2,1}$ and their cyclographic images. We only considered curves with space-like tangents, however, light-like tangents may be present at endpoints. Figure 13 shows such a situation.

We discuss the effect of these points for the four methods:

* **DAI:** The method can be applied without any problems. The arcs of the circles that correspond to the endpoints must be added to the envelope.
<figure><img src="image_20.png" /><figcaption>Figure 13: Minkowski curve segment with a light-like tangent at an endpoint.</figcaption></figure>

* **DBI:** The method cannot be used if one of the segment end points has a light-like tangent. Let $v_N = 1$ be the last parameter value, such that the tangent at the point $C_N = C(v_N)$ is light-like, i.e., $\|C(v_N)\'|_M = 0$. We sample one additional point on the curve $C(v)$,

$$C_{N-\frac{1}{2}} = C(\frac{v_{N-1} + v_N}{2}),$$

and we use a single Minkowski arc that interpolates the points $C_{N-1}$, $C_{N-\frac{1}{2}}$, $C_N$ to represent the last segment. See Figure 14 for an illsutration.

* **IAI:** The method can be used, however a reparameterization of the boundary curve is needed since the parametric speed tends to infinity as we approach the point with a light-like tangent, which corresponds to a vertex of the boundary curve.

* **IBI:** The method can also be used, again after performing a reparameterization of the boundary.

<figure><img src="image_21.png" /><figcaption>Figure 14: Handling time-like tangents in the **DBI** method. The last segment is represented by a single Minkowski arc. We sample one additional point on the curve to compute the Minkowski arc (red dashed circle).</figcaption></figure>

## Acknowledgment

This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/15270.
## References

[1] J. W. Ahn, M.-S. Kim, and S. B. Lim. Approximate general sweep boundary of a 2D curved object. *CVGIP: Graphical Models and Image Processing*, 55(2):98-128, 1993.

[2] O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, E. Pilgerstorfer, and M. Rabl. Divide-and-conquer for Voronoi diagrams revisited. *Computational Geometry*, 43(8):688-699, 2010. Special Issue on the 25th Annual Symposium on Computational Geometry (SoCG'09).

[3] O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, and M. Rabl. Medial axis computation for planar free-form shapes. *Computer-Aided Design*, 41(5):339-349, 2009. Voronoi Diagrams and their Applications.

[4] O. Aichholzer, W. Aigner, T. Hackl, and N. Wolpert. Exact medial axis computation for circular arc boundaries. In *Curves and Surfaces*, pages 28-42. Springer Berlin Heidelberg, 2012.

[5] O. Aichholzer, F. Aurenhammer, T. Hackl, B. Jüttler, M. Oberneder, and Z. Šír. Computational and structural advantages of circular boundary representation. *Int. J. Computational Geometry and Applications*, 21(1):47-69, 2011.

[6] D. Attali and A. Montanvert. Computing and simplifying 2D and 3D continuous skeletons. *Computer Vision and Image Understanding*, 67(3):261-273, 1997.

[7] B. Bastl, J. Kosinka, and M. Lávička. Simple and branched skins of systems of circles and convex shapes. *Graphical Models*, 78:1-9, 2015.

[8] J. L. Bentley and T. Ottmann. Algorithms for reporting and counting geometric intersections. *IEEE Transactions on Computers*, C-28:643-647, 1979.

[9] E. Bertolazzi, M. Frego, and F. Biral. Interpolating splines of biarcs from a sequence of planar points. *Computer-Aided Design and Applications*, 18(1):66-85, 2020.

[10] M. Bizzarri, M. Lávička, and J. Kosinka. Medial axis transforms yielding rational envelopes. *Computer Aided Geometric Design*, 46:92-102, 2016.

[11] D. Blackmore, M. C. Leu, and F. Shih. Analysis and modelling of deformed swept volumes. *Computer-Aided Design*, 26(4):315-326, 1994. Special Issue: Mathematical methods for CAD.

[12] D. Blackmore, M. C. Leu, and L. P. Wang. The sweep-envelope differential equation algorithm and its application to NC machining verification. *CAD Computer Aided Design*, 29(9):629-637, 1997.

[13] D. Blackmore and M.C. Leu. A differential equation approach to swept volumes. In *Proceedings. Rensselaer's Second International Conference on Computer Integrated Manufacturing*, pages 143-149, 1990.
[14] W. Blaschke. *Vorlesungen über Differentialgeometrie und geometrische Grundlagen von Einsteins Relativitätstheorie. III: Differentialgeometrie der Kreise und Kugeln.* J. Springer, Berlin, 1929.

[15] H. Blum. A transformation for extracting new descriptors of shape. In Weiant Wathen-Dunn, editor, *Models for the Perception of Speech and Visual Form*, pages 362–380. MIT Press, Cambridge, 1967.

[16] L. Cao and J. Liu. Computation of medial axis and offset curves of curved boundaries in planar domain. *Computer-Aided Design*, 40(4):465–475, 2008.

[17] T. E. Cecil. *Lie Sphere Geometry*. Universitext. Springer New York, NY, 1992.

[18] F. Y. L. Chin, J. Snoeyink, and C. A. Wang. Finding the medial axis of a simple polygon in linear time. *Discrete & Computational Geometry*, 21:405–420, 1995.

[19] H. I. Choi, S. W. Choi, and H. P. Moon. Mathematical theory of medial axis transform. *Pacific J Math*, 181, 12 1997.

[20] H. I. Choi, S. W. Choi, H. P. Moon, and N.-S. Wee. New algorithm for medial axis transform of plane domain. *Graphical Models and Image Processing*, 59(6):463–483, 1997.

[21] W.L.F. Degen. Exploiting curvatures to compute the medial axis for domains with smooth boundary. *Computer Aided Geometric Design*, 21(7):641–660, 2004.

[22] G. Evans, A. Middleditch, and N. Miles. Stable computation of the 2D medial axis transform. *International Journal of Computational Geometry & Applications*, 08(05n06):577–598, 1998.

[23] R. Fabbri, L.F. Estrozi, and Luciano da F. Costa. On Voronoi diagrams and medial axes. *Journal of Mathematical Imaging and Vision*, 17:27–40, 07 2002.

[24] S. Han, S. H. Yoon, M. S. Kim, and G. Elber. Minkowski sum computation for planar freeform geometric models using $G^1$-biarc approximation and interior disk culling. *The Visual Computer*, 35, 05 2019.

[25] M.-S. Kim, J.-W. Ahn, and S.-B. Lim. An algebraic algorithm to compute the exact general sweep boundary of a 2D curved object. *Information Processing Letters*, 47(5):221–229, 1993.

[26] M.-S. Kim and G. Elber. Problem reduction to parameter space. In *The Mathematics of Surfaces IX*, pages 82–98. Springer London, 2000.

[27] Y. J. Kim, J. Lee, M. S. Kim, and G. Elber. Efficient offset trimming for planar rational curves using biarc trees. *Computer Aided Geometric Design*, 29(7):555–564, 2012. Geometric Modeling and Processing 2012.
[28] K. Kruppa. Applying rational envelope curves for skinning purposes. *Frontiers of Information Technology & Electronic Engineering*, 22:202–209, 2020.

[29] K. Kruppa, R. Kunkli, and M. Hoffmann. An improved skinning algorithm for circles and spheres providing smooth transitions. *Graphical Models*, 101:27–37, 2019.

[30] K. Kruppa, R. Kunkli, and M. Hoffmann. Possibilities and advantages of rational envelope and Minkowski Pythagorean hodograph curves for circle skinning. *Mathematics*, 9(8):843, 2021.

[31] R. Kunkli and M. Hoffmann. Skinning of circles and spheres. *Computer Aided Geometric Design*, 27:611–621, 2010. Advances in Applied Geometry.

[32] D. T. Lee. Medial axis transformation of a planar shape. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, PAMI-4(4):363–369, 1982.

[33] J.-H. Lee, S. Hong, and M.-S. Kim. Polygonal boundary approximation for a 2D general sweep based on envelope and boolean operations. *The Visual Computer*, 16:208–240, 05 2000.

[34] K. Lee. *Principles of CAD/CAM/CAE Systems*. Addison-Wesley, 1999.

[35] J. Machchhar. A unified algebraic framework for fast and precise planar swept volumes and Minkowski sums. *Computer Aided Geometric Design*, 96:102107, 2022.

[36] D. S. Meek and D. J. Walton. Approximation of discrete data by $G^1$ arc splines. *Computer-Aided Design*, 24(6):301–306, 1992.

[37] D. S. Meek and D. J. Walton. Planar osculating arc splines. *Computer Aided Geometric Design*, 13(7):653–671, 1996.

[38] D.S. Meek and D.J. Walton. Approximating smooth planar curves by arc splines. *Journal of Computational and Applied Mathematics*, 59(2):221–231, 1995.

[39] H. P. Moon. Minkowski Pythagorean hodographs. *Computer Aided Geometric Design*, 16(8):739–753, 1999.

[40] M. Pan, R. Zou, W. Tong, Y. Guo, and F. Chen. $G_1$-smooth planar parameterization of complex domains for isogeometric analysis. *Computer Methods in Applied Mechanics and Engineering*, 417:116330, 2023.

[41] H. Pottmann and M. Peternell. Applications of Laguerre geometry in CAGD. *Computer Aided Geometric Design*, 15(2):165–186, 1998.

[42] H. Pottmann and M. Peternell. Envelopes – Computational theory and applications. In B. Falcidieno, editor, *Spring Conference on Computer Graphics*, pages 3–23, Bratislava, 2000. Comenius University.
[43] M. Ramanathan and B. Gurumoorthy. Constructing medial axis transform of planar domains with curved boundaries. *Computer-Aided Design*, 35(7):619–632, 2003.

[44] J. Vráblíková, V. Ortler, B. Jüttler, and Z. Šír. Interpolation by polygon rolling motions for approximate sweep computation. *Journal of Computational and Applied Mathematics*, 447:115891, 2024.

[45] Z. Šír, Feichtinger R., and B. Jüttler. Approximating curves and their offsets using biarcs and Pythagorean hodograph quintics. *Computer-Aided Design*, 38(6):608–618, 2006.

[46] G. Wang, J.-G. Sun, and H. Xuanji. Sweep-envelope differential equation algorithm for general deformed swept volumes. *Computer Aided Geometric Design*, 17:399–418, 05 2000.

[47] B. Weiß, B. Jüttler, and F. Aurenhammer. Arc fibration kernels of arc spline domains. Technical Report No. 95, Johannes Kepler University, Institute of Applied Geometry, Linz, 2021.

[48] F.-E. Wolter. Cut locus and medial axis in global shape interrogation and representation. *MIT Design Laboratory Memorandum 92-2 and MIT Sea Grant Report*, 11 1992.

[49] Y. Zhu, Sun F., Y.-K. Choi, B. Jüttler, and W. Wang. Computing a compact spline representation of the medial axis transform of a 2D shape. *Graphical Models*, 76(5):252–262, 2014. Geometric Modeling and Processing 2014.