# Interpolation by polygon rolling motions for approximate sweep computation

Jana Vráblíková, Vanessa Ortler, Bert Jüttler, Zbyněk Šír

► To cite this version:

Jana Vráblíková, Vanessa Ortler, Bert Jüttler, Zbyněk Šír. Interpolation by polygon rolling motions for approximate sweep computation. Journal of Computational and Applied Mathematics, 2024, 447, pp.13. 10.1016/j.cam.2024.115891. hal-05441783

HAL Id: hal-05441783

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

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_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

# Interpolation by polygon rolling motions for approximate sweep computation

Jana Vráblíkováª, Vanessa Ortlerª, Bert Jüttlerª,*, Zbyněk Šírᵇ

## ARTICLE INFO

**Keywords:**

Arc spline

Planar motion

Motion approximation

Hausdorff distance

Quadratic convergence

## ABSTRACT

We interpolate planar rigid body motions by piecewise rotational and translational motions. The trajectories of all points are then arc splines, i.e., curves composed of circular arcs or line segments. For objects with arc spline boundaries, the boundary of the volume swept by the object and the motion is then again an arc spline. We prove that the distance between the original motion and its approximation as between curves in a suitable kinematic image space converges quadratically to zero. This implies the same rate of convergence between point trajectories under the two motions.

## 1. Introduction

Computational Geometry algorithms based on circular arcs combine *geometric flexibility* with *computational simplicity*.

On the one hand, the *geometric flexibility* of circular arcs means that many shapes can be represented exactly, while others can be approximated with a high degree of accuracy. Arc spline curves, which consist of circular arcs and line segments, are a well-established representation of planar shapes, and several techniques are available for constructing them. These include biarc interpolation methods for discrete data [1,2] and for the approximation of smooth curves [3,4]. The approximation properties of the different variants were analyzed in [5], and methods for generating arc spline curves with the minimum number of segments that represent a given shape with a pre-defined accuracy have also been studied [6,7].

On the other hand, the *computational simplicity* of circular arcs ensures efficiency and robustness [8]. For instance, it was noted that the medial axis of planar domains can be found efficiently with the help of a randomized divide-and-conquer-type algorithm [9], and this approach has later been extended to the Voronoi diagrams of curved sites in the plane [10]. Biarc approximations of planar curves were used to detect and to trim the self-intersections in the offsets [11]. Triangulations with circular arcs were studied in [12]. An efficient algorithm for Minkowski sum computation of two planar object with arc spline boundary via interior disk culling was established in [13]. The investigation of polar parameterizations based on circular arcs [14], which generalize the classical notion of starshapedness, led to the notion of the arc fibration kernel (AFK). In a recent paper it was shown that the AFKs of arc spline domains are again arc spline domains [15], and this result confirms the suitability of circular arcs for this class of problems.

This paper is the first of a two-part series about the computation of arc spline domains that approximate sweeps of arc spline domains. Given a planar object with an arc spline boundary, which is subject to a planar rigid body motion, our aim is to compute the planar domain that is swept out by the object, again in an arc spline boundary representation. The method is based on a suitable approximation of the planar motion.

<footnote>ªInstitute of Applied Geometry, Johannes Kepler University, Linz, Austria</footnote>

<footnote>ᵇFaculty of Mathematics and Physics, Charles University, Prague, Czech Republic</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: jana.vrablikova@jku.at (J. Vráblíková), vanessa.ortler@jku.at (V. Ortler), bert.juettler@jku.at (B. Jüttler), zbynek.sir@mff.cuni.cz (Z. Šír).</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 1. A polygon-rolling planar motion is defined by a fixed (black) and a moving central polygon (blue). The latter one is depicted at two different positions.</figcaption></figure>

Motion approximation and design is a well-studied problem, due to its wide range of applications in robotics and computer animation. One of the first contributions to this topic [16] proposed to use techniques of Computer Aided Geometric Design to represent motions as Bézier curves on a suitable kinematic image space. The resulting trajectories of points are general curves that are difficult to deal with. The survey article of Röschel [17] described methods for rational motion design, i.e., motions where all point trajectories are rational curves. While polynomials of degree $n$ in the dual quaternion model of rigid body displacements give rational motions with point trajectories of degree $2n$ in general, certain algebraic conditions have been identified [18] that lead to trajectories of lower degrees. Geometric interpolation schemes were investigated in order to obtain low degree interpolants [19–21] and also methods for $C^2$ rational spline motion were presented [22]. In the context of Pythagorean hodograph curves, various methods for designing the motion of the Euler–Rodrigues frame – which is an adapted frame of these curves – have been proposed, see e.g. [23,24].

For the special case of planar motions, control structures and interpolation schemes yielding rational trajectories have been studied [25]. More recently, a geometric algebra approach was explored for fitting planar motions [26].

This paper series is devoted to the application of arc splines to envelope computation for moving planar objects. Consequently, we are interested in approximating motions that possess piecewise circular trajectories. These either have a constant rotational component (studied in [13] in the context of Minkowski sum computation) or they are composed of rotational and translational motions. It is well known that any planar motion (excluding translations, which, however, can be seen as a limit case) is generated by two curves, which are called the centroids, rolling on each other. For the motions we consider, these centroids are two polygons with matching segment lengths, called the central polygons [27]. In order to reflect this fact, we call them the *polygon rolling motions*, see Fig. 1.

The remainder of the paper is organized as follows. In Section 2 we introduce a kinematic image space for the group of planar rigid body motions. It is shown how the distance of two motions in the kinematic space provides an upper bound for the distance of all trajectories. In Section 3 we study the approximation of curves in the kinematic space by piecewise defined curves composed of special helices and horizontal line segments. Section 4 then presents the procedure for motion approximation by a piecewise rotational and translational motions and Section 5 discusses the consequences for the approximation of swept volumes. Finally we conclude the paper.

## 2. Preliminaries

We represent a rigid body displacement $D \in SE(2)$ as a triplet

$$ (v_x, v_y, \varphi), \qquad (1) $$

where the angle $\varphi$ is only determined up to an integer multiple of $2\pi$.

More precisely we consider the triplets as elements of the space $\mathbb{R}^3$, where we identify points according to

$$ (v_x, v_y, \varphi)^T \sim (\hat{v}_x, \hat{v}_y, \hat{\varphi})^T \quad \text{iff} \quad v_x = \hat{v}_x, v_y = \hat{v}_y, \varphi - \hat{\varphi} \in 2\pi\mathbb{Z}. $$

Thus, each displacement is represented by an equivalence class $D = (v_x, v_y, \varphi)_{\sim}$, and we use

$$ D_{\star} = (v_x, v_y, \varphi_{\star}) \qquad (2) $$

to denote the unique representative of the displacement $D$ with angle $\varphi_{\star} \in (-\pi, \pi]$. The manifold $\mathbb{R}^3_{\sim}$ serves as our kinematic image space.
The displacement $D$ acts on a point $\mathbf{p} = (p_x, p_y)^T \in \mathbb{R}^2$ according to

$$D(\mathbf{p}) = \begin{pmatrix} v_x \\ v_y \end{pmatrix} + \begin{pmatrix} \cos \varphi & -\sin \varphi \\ \sin \varphi & \cos \varphi \end{pmatrix} \begin{pmatrix} p_x \\ p_y \end{pmatrix}. \quad (3)$$

A point $\mathbf{p} \in \mathbb{R}^2$ satisfying

$$D(\mathbf{p}) = \mathbf{p} \quad (4)$$

is called the fixed point of $D$.

For any displacement $D = (v_x, v_y, \varphi)$ there exists its inverse $D^{-1}$ defined by

$$D^{-1} = (-v_x \cos \varphi - v_y \sin \varphi, v_x \sin \varphi - v_y \cos \varphi, -\varphi).$$

The composition of two displacements $D = (v_x, v_y, \varphi)$ and $\hat{D} = (\hat{v}_x, \hat{v}_y, \hat{\varphi})$ evaluates to

$$\hat{D} \circ D = (\hat{v}_x + v_x \cos \hat{\varphi} - v_y \sin \hat{\varphi}, \hat{v}_y + v_y \cos \hat{\varphi} + v_x \sin \hat{\varphi}, \varphi + \hat{\varphi}). \quad (5)$$

A planar motion $M(u), u \in \mathbb{R}$, is a one-parameter family of rigid body displacements,

$$M(u) = (v_x(u), v_y(u), \varphi(u)).$$

We recall two one-parameter subgroups of $SE(2)$:

* For any non-zero real constant $c$, the displacements $T_c(u) = (cu, 0, 0)$, $u \in \mathbb{R}$, form the group of translations in the direction of the x-axis.

* For any non-zero real constant $c$, the displacements $R_c(u) = (0, 0, cu)$ $u \in \mathbb{R}$, form the group of rotations around the origin.

They are used to introduce two fundamental classes of motions:

* Any motion of the form

$$T(u) = D \circ T_c(u) \circ \hat{D},$$

where $D, \hat{D} \in SE(2)$ are two fixed displacements and $c$ is a constant, is called a translational motion. Using the composition formula (5), we can express any translational motion as

$$T(u) = ((1-u)t_x^{(\ell)} + ut_x^{(r)}, (1-u)t_y^{(\ell)} + ut_y^{(r)}, \tau), \quad (6)$$

with real constants $t_x^{(\ell)}, t_x^{(r)}, t_y^{(\ell)}, t_y^{(r)}, \tau$:

$$t_x^{(\ell)} = v_x + \hat{v}_x \cos \varphi - \hat{v}_y \sin \hat{\varphi},$$

$$t_x^{(r)} = v_x + c \cos \varphi + \hat{v}_x \cos \varphi - \hat{v}_y \sin \hat{\varphi},$$

$$t_y^{(\ell)} = v_y + \hat{v}_y \cos \varphi + \hat{v}_x \sin \varphi,$$

$$t_y^{(r)} = v_y + \hat{v}_y \cos \varphi + c \sin \varphi + \hat{v}_x \sin \varphi,$$

$$\tau = \varphi + \hat{\varphi}.$$

To emphasize the parameters of the translational motion we denote it by

$$\mathrm{TM}[t_x^{(\ell)}, t_x^{(r)}, t_y^{(\ell)}, t_y^{(r)}, \tau](u) = T(u). \quad (7)$$

* Any motion of the form

$$R(u) = D \circ R_c(u) \circ \hat{D},$$

where $D, \hat{D} \in SE(2)$ are two fixed displacements and $c$ is a constant, is called a rotational motion and any such motion can be expressed as

$$R(u) = (r_x^{(\ell)}, r_y^{(\ell)}, 0) \circ (0, 0, (1-u)\varphi^{(\ell)} + u\varphi^{(r)}) \circ (r_x^{(r)}, r_y^{(r)}, 0), \quad (8)$$

with real parameters $r_x^{(\ell)}, r_x^{(r)}, r_y^{(\ell)}, r_y^{(r)}, \varphi^{(\ell)}, \varphi^{(r)}$:

$$r_x^{(\ell)} = v_x,$$

$$r_y^{(\ell)} = v_y,$$

$$r_x^{(r)} = \hat{v}_x \cos \hat{\varphi} + \hat{v}_y \sin \hat{\varphi},$$

$$r_y^{(r)} = \hat{v}_y \cos \hat{\varphi} - \hat{v}_x \sin \hat{\varphi},$$

$$\varphi^{(\ell)} = \varphi + \hat{\varphi},$$

$$\varphi^{(r)} = \varphi + \hat{\varphi} + c.$$
The point $(r_x^\ell, r_y^\ell)^T \in \mathbb{R}^2$ is the fixed point of the rotational motion $M(u)$, i.e. for any $u \in \mathbb{R}$ it holds

$$M(u)((r_x^\ell, r_y^\ell)^T) = (r_x^\ell, r_y^\ell)^T.$$

To emphasize the parameters of the rotational motion we denote it by

$$\mathrm{RM}[r_x^{(\ell)}, r_x^{(r)}, r_y^{(\ell)}, r_y^{(r)}, \vartheta^{(\ell)}, \vartheta^{(r)}](u) = R(u). \qquad (9)$$

The rotational and translational motions correspond to particular classes of curves in the kinematic image space. On the one hand, translational motions correspond to horizontal lines (i.e., lines that are parallel to the xy-plane). On the other hand, we need to introduce a special class of helices in order to characterize rotational motions:

**Definition.** Any helix in $\mathbb{R}^3$ with pitch $2\pi$ and axis parallel to the $\varphi$-axis of $\mathbb{R}^3$ is called an R-helix.

We then have the following simple observation:

**Lemma 1.** There is a one-to-one correspondence between rotational motions $R(u)$ and R-helices.

**Proof.** The right-hand side of (8) can be expressed as

$$\begin{pmatrix} r_x \\ r_y \\ 0 \end{pmatrix} + \begin{pmatrix} \cos \alpha & -\sin \alpha & 0 \\ \sin \alpha & \cos \alpha & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} \hat{r}_x \\ \hat{r}_y \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ \alpha \end{pmatrix}$$

where $\alpha = (1 - u)\vartheta_0 + u\vartheta_1$. It is clearly an R-helix. Conversely, any such R-helix can be expressed in this form. Note that also the lines that are parallel to the $\varphi$-axis are included as a special case for $\hat{r}_x = \hat{r}_y = 0$. $\square$

**Lemma 2.** There is a one-to-one correspondence between translational motions $T(u)$ and straight lines in $\mathbb{R}^3$ that are parallel to the xy-plane.

**Proof.** The image of a (6) is a straight line segment in $\mathbb{R}^3$ that is parallel to the xy-plane and any such segment can be expressed in this form. $\square$

We recall the one-sided Hausdorff distance of two parametric curve segments $c(u) : [a, b] \to \mathbb{R}^n$ and $\hat{c}(\hat{u}) : [\hat{a}, \hat{b}] \to \mathbb{R}^n$, which is given by

$$\delta^*(c(u), \hat{c}(\hat{u})) = \max_{u \in [a, b]} \min_{\hat{u} \in [\hat{a}, \hat{b}]} \|c(u) - \hat{c}(\hat{u})\|,$$

where $\| \cdot \|$ denotes the Euclidean norm in $\mathbb{R}^n$. The Hausdorff distance is obtained by symmetrizing this expression,

$$\delta(c(u), \hat{c}(\hat{u})) = \max\{\delta^*(\hat{c}(\hat{u}), c(u)), \delta^*(c(u), \hat{c}(\hat{u}))\}. \qquad (10)$$

In order to keep the notation simple, we always refer implicitly to the domains of the two curves.

Similarly we define the one-sided Hausdorff distance of two kinematic image curves $M(u) : [a, b] \to \mathbb{R}^3$ and $\hat{M}(\hat{u}) : [\hat{a}, \hat{b}] \to \mathbb{R}^3$ as

$$\Delta^*(M(u), \hat{M}(\hat{u})) := \max_{u \in [a, b]} \min_{\hat{u} \in [\hat{a}, b]} \|M(u) - \hat{M}(\hat{u})\|_{\sim},$$

where

$$\|(v_x, v_y, \varphi)\|_{\sim} = \min_{s \in \mathbb{Z}} \|(v_x, v_y, \varphi + 2s\pi)\|$$

is the geodesic distance in $\mathbb{R}^3$. The Hausdorff distance is again obtained by symmetrizing this expression,

$$\Delta(M(u), \hat{M}(\hat{u})) = \max\{\Delta^*(\hat{M}(\hat{u}), M(u)), \Delta^*(M(u), \hat{M}(\hat{u}))\}. \qquad (11)$$

For future reference we note that the Hausdorff distance satisfies

$$\delta(c(u), \hat{c}(\hat{u})) \le \max_{u \in [a, b]} \|c(u) - \hat{c}(u)\| \qquad (12)$$

if $c(u)$ and $\hat{c}(\hat{u})$ are parameterized on the same interval $[a, b]$, and analogously for $\Delta$.

The following lemma bounds the distance of trajectories of a point under two different motions by the distance of the images of the motions in the kinematic image space.

**Lemma 3.** Let $M(u)$, $\hat{M}(\hat{u})$, $u, \hat{u} \in [a, b]$, be two planar motions. The Hausdorff distance of the trajectories of a point $\mathbf{p} \in \mathbb{R}^2$ under $M(u)$ and $\hat{M}(\hat{u})$ satisfy

$$\delta(M(u)(\mathbf{p}), \hat{M}(\hat{u})(\mathbf{p})) \le (1 + \|\mathbf{p}\|) \Delta(M(u), \hat{M}(\hat{u})).$$
**Proof.** Let $M(u) = (v_x(u), v_y(u), \varphi(u))$ and $\hat{M}_2(\hat{u}) = (\hat{v}_x(\hat{u}), \hat{v}_y(\hat{u}), \hat{\varphi}(\hat{u}))$, $u, \hat{u} \in [a, b]$ and $\mathbf{p} = (p_x, p_y)^T$.

The trajectories $M(u)(\mathbf{p})$ and $\hat{M}(\hat{u})(\mathbf{p})$ of $\mathbf{p}$ are given by (3), hence

$$M(u)(\mathbf{p}) - \hat{M}(\hat{u})(\mathbf{p}) = \begin{pmatrix} v_x(u) - \hat{v}_x(\hat{u}) \\ v_y(u) - \hat{v}_y(\hat{u}) \end{pmatrix} + A\mathbf{p}$$

where

$$A = \begin{pmatrix} \cos \varphi(u) - \cos \hat{\varphi}(\hat{u}) & -\sin \varphi(u) + \sin \hat{\varphi}(\hat{u}) \\ \sin \varphi(u) - \sin \hat{\varphi}(\hat{u}) & \cos \varphi(u) - \cos \hat{\varphi}(\hat{u}) \end{pmatrix}.$$

Thus

$$\begin{align*}
\| M(u)(\mathbf{p}) - \hat{M}(\hat{u})(\mathbf{p}) \| &\le \left\| \begin{pmatrix} v_x(u) - \hat{v}_x(\hat{u}) \\ v_y(u) - \hat{v}_y(\hat{u}) \end{pmatrix} \right\| + \|A\|_2 \|\mathbf{p}\| \\
&\le \left\| \begin{pmatrix} v_x(u) - \hat{v}_x(\hat{u}) \\ v_y(u) - \hat{v}_y(\hat{u}) \end{pmatrix} \right\|_{\sim} + \sqrt{2 - 2 \cos(\varphi(u) - \hat{\varphi}(\hat{u}))} \|\mathbf{p}\| \\
&\le \left\| \begin{pmatrix} v_x(u) - \hat{v}_x(\hat{u}) \\ v_y(u) - \hat{v}_y(\hat{u}) \end{pmatrix} \right\|_{\sim} + |\varphi(u) - \hat{\varphi}(\hat{u})| \|\mathbf{p}\| \\
&\le \|M(u) - \hat{M}(\hat{u})\|_{\sim} + \|M(u) - \hat{M}(\hat{u})\|_{\sim} \|\mathbf{p}\| \\
&= (1 + \|\mathbf{p}\|) \|M(u) - \hat{M}(\hat{u})\|_{\sim},
\end{align*}$$

for any $u, \hat{u} \in [a, b]$. We bound the one-sided Hausdorff distance of the trajectories by

$$\begin{align*}
\delta^*(M(u)(\mathbf{p}), \hat{M}(\hat{u})(\mathbf{p})) &= \max_{u \in [a,b]} \min_{\hat{u} \in [a,b]} \|M(u)(\mathbf{p}) - \hat{M}(\hat{u})(\mathbf{p})\| \\
&\le (1 + \|\mathbf{p}\|) \Delta^*(M(u), \hat{M}(\hat{u}))
\end{align*}$$

and similarly for $\delta^*(\hat{M}(\hat{u})(\mathbf{p}), M(u)(\mathbf{p}))$. Finally, by (10) we obtain

$$\delta(M(u)(\mathbf{p}), \hat{M}(\hat{u})(\mathbf{p})) \le (1 + \|\mathbf{p}\|) \Delta(M(u), \hat{M}(\hat{u})). \quad \square$$

### 3. Approximation of curves in $\mathbb{R}^3$

We adapt the classical result about the piecewise linear approximation of $C^2$-smooth curves to $\mathbb{R}^3$. Consider a one-parameter planar motion represented by a $C^2$-smooth curve $M(u) : [a, b] \to \mathbb{R}^3$ and a partition

$$a = u_0 < u_1 < \dots < u_k = b \qquad (13)$$

of the parameter interval. We denote by

$$h = \max_{i=1,\dots,k} \int_{u_{i-1}}^{u_i} \|M'(u)\| du$$

the maximum length of a curve segment and assume $h < \pi$.

When considering linear $C^0$ interpolation in $\mathbb{R}^3$ we must handle the ambiguity of the representatives (i.e., the $2\pi$-periodicity). More precisely, given a motion $M(u)$ and a partition of its parameter domain as above, we consider the piecewise linear approximation $L(\hat{u})$, $\hat{u} \in [a, b]$ with the segments

$$L(\hat{u}) = \left( (1 - \bar{u}^{(i)}(\hat{u})) M_{\star}(u_{i-1}) + \bar{u}^{(i)}(\hat{u}) (M_{\star}(u_i) + (0, 0, 2s_i\pi)) \right)_{\sim} \quad \text{for } \hat{u} \in [u_{i-1}, u_i], \qquad (14)$$

where $i = 1, \dots, k$ is the number of the segment. These are defined with the help of the local parameters

$$\bar{u}^{(i)}(\hat{u}) = \frac{\hat{u} - u_{i-1}}{u_i - u_{i-1}}.$$

In each segment we select the representative of the end point with the help of the integer shift

$$s_i = \operatorname{argmin}_{s \in \mathbb{Z}} \| M_{\star}(u_i) + (0, 0, 2s\pi) - M_{\star}(u_{i-1}) \|.$$

Fig. 2 visualizes the effect of the integer shift. In the case when

$$\| M_{\star}(u_i) - M_{\star}(u_{i-1}) \| = \pi,$$

$s_i$ is not unique, and we pick the smaller value.

The error is analyzed in the following Lemma:
<figure><img src="image_4.png" /><figcaption>Fig. 2. Piecewise linear approximation $L(\hat{u})$ (solid black) of a motion $M(u)$ (blue) using the integer shift.</figcaption></figure>

**Lemma 4.** The piecewise linear approximation $L(\hat{u})$ of the given motion satisfies

$$ \Delta(M(u), L(\hat{u})) \leq Kh^2, $$

where the constant $K \in \mathbb{R}$ is the maximum curvature of $M(t)$.<fnref n="1" />

**Proof.** Without loss of generality, we assume that $M(u)$ is parameterized by arc length, hence

$$ K = \max_{u \in [a, b]} \|M''(u)\|. \qquad (15) $$

Considering a particular value of $u \in [u_{i-1}, u_i] \subseteq [a, b]$ for some segment number $i$, we choose the system of world coordinates such that the third coordinate of $M_*(u)$ fulfills $\varphi_*(u_{i-1}) = 0$. The particular choice of the world coordinates implies that the integer shift for the linear interpolation is equal to zero. It also guarantees the smoothness of $M_*(u)$ – hence the applicability of Taylor’s theorem – for $u \in [u_{i-1}, u_i]$.

By Eq. (12) it suffices to bound the length $\|M(u) - L(u)\|_{\sim}$ of the difference vectors for all $u \in [a, b]$. It is bounded by the Euclidean norm of the difference vectors of the unique representatives with angles in $(-\pi, \pi]$. The triangle inequality gives

$$ \|M(u) - L(u)\|_{\sim} \le \|M_{*}(u) - L_{*}(u)\| \le \|M_{*}(u) - Q(u)\| + \|L_{*}(u) - Q(u)\|, \qquad (16) $$

where

$$ Q(u) = M_{*}(u_{i-1}) + M'_{*}(u_{i-1}) (u - u_{i-1}) $$

is a parameterization of the tangent of $M_*(u)$ at $u = u_{i-1}$. The last term in (16) can be estimated by

$$ \|L_{*}(u) - Q(u)\| \le \|L_{*}(u_{i}) - Q(u_{i})\| = \|M_{*}(u_{i}) - Q(u_{i})\| $$

if $u \in [u_{i-1}, u_i]$, because $L_*(u)$ and $Q(u)$ are line segments with the common starting point $M_*(u_{i-1})$ and their distance increases for $u > u_{i-1}$ (see Fig. 3), hence

$$ \|M(u) - L(u)\|_{\sim} \le \|\frac{1}{2} M''_{*}(\tilde{u})(u - u_{i-1})^2\| + \|\frac{1}{2} M''_{*}(u^{**})(u_i - u_{i-1})^2\| $$

for some $\tilde{u} \in [u_{i-1}, u]$ and $u^{**} \in [u_{i-1}, u_i]$ according to Taylor’s theorem (used twice) and the Lagrange form of the reminder. The result then follows from (15). □

We will now evaluate the distance between linear segments and R-helices in $\mathbb{R}^3$.

**Lemma 5.** The approximation of a non-horizontal line segment $L(\hat{u}) : [u_{i-1}, u_i] \to \mathbb{R}^3$ with length $\Lambda = \|L(u_{i-1}) - L(u_i)\|_{\sim}$ by the R-helix segment $R(\tilde{u})$, $\tilde{u} \in [u_{i-1}, u_i]$, that fulfills $L(u_{i-1}) = R(u_{i-1})$ and $L(u_i) = R(u_i)$ satisfies

$$ \Delta(L(\hat{u}), R(\tilde{u})) \le \frac{1}{4\pi} \Lambda^2, $$

provided that $\Lambda \le \pi$.

<footnote n="1">¹ Here we consider it simply as a curve in $\mathbb{R}^3$.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 3. The maximum distance of the chord $L_*(u)$ of a helix segment $M_*(u)$ and the tangent $Q(u)$ of the helix is attained at the end points of the chord and the tangent.</figcaption></figure>

**Proof.** Since each point in $\mathbb{R}^3_\sim$ corresponds to an Euclidean displacement, by Lemma 1 it follows that there exists a unique R-helix interpolating the two end points of the linear segment.

By suitably choosing the coordinates, the segment of the R-helix can be represented as

$$R(\tilde{u}) = (\rho \cos \tilde{u}, \rho \sin \tilde{u}, \tilde{u})_\sim, \qquad (17)$$

where the real parameter $\rho$ specifies the radius. Additionally, the coordinate system can be chosen so that

$$u_{l-1} = -u_l$$

holds. Moreover, the bound on the length $\Lambda$ implies that $0 < u_l < \frac{\pi}{2}$, hence $R_*(\tilde{u}) = (\rho \cos \tilde{u}, \rho \sin \tilde{u}, \tilde{u})$. The line segment $L_*(\tilde{u}), \tilde{u} \in [u_{l-1}, u_l]$, is then the chord of the helix segment $R_*(\tilde{u}), \tilde{u} \in [u_{l-1}, u_l]$.

By symmetry, the maximum distance of $L(\tilde{u})$ and $R(\tilde{u})$ is attained at the midpoint

$$\tilde{u} = \tilde{u} = \frac{u_{l-1} + u_l}{2} = 0$$

of the knot span, hence

$$\Delta(L(\tilde{u}), R(\tilde{u}))^2 \le \|L(0) - R(0)\|_{\sim}^2 = \|L_*(0) - R_*(0)\|^2 = \rho^2(\cos u_l - 1)^2,$$

where the last equality follows from a straightforward computations from (14) and (17). In addition we get

$$\Lambda^2 = 4\rho^2 \sin^2 u_l + 4u_l^2,$$

therefore

$$\frac{\Delta(L(\tilde{u}), R(\tilde{u}))^2}{\Lambda^4} \le \frac{\rho^2(\cos u_l - 1)^2}{(4\rho^2 \sin^2 u_l + 4u_l^2)^2} = f(u_l, \rho),$$

where we introduce the auxiliary function $f(u_l, \rho)$. For any fixed value of $u_l$, this function reaches its maximum value for $\rho(u_l) = \frac{u_l}{\sin u_l}$, thus

$$\frac{\delta(L(\tilde{u}), R(\tilde{u}))^2}{\Lambda^4} \le f\left(u_l, \frac{u_l}{\sin u_l}\right) = \frac{1 - \cos u_l}{64u_l^2(\cos u_l + 1)} = \frac{\tan^2 \frac{u_l}{2}}{64u_l^2}.$$

Finally we note that the right-hand side of this inequality is increasing as $u_l$ varies in $(0, \frac{\pi}{2})$, and we use this fact to derive the upper bound of $\frac{1}{(4\pi)^2}$. $\square$

Note that if we choose a lower bound on $\Lambda$, we get a constant lower than $\frac{1}{(4\pi)^2}$. On the other hand, no similar result can be derived without the bound on $\Lambda$.

Given the partition (13) of the interval $[a, b]$, we can approximate a $C^2$-smooth motion $M(u) : [a, b] \to \mathbb{R}^3_\sim$ on each subinterval $[u_{l-1}, u_l]$ by a motion $W(\tilde{u}), \tilde{u} \in [a, b]$ satisfying

$$W(u_l) = M(u_l), \ i \in \{0, 1, \dots, k\}.$$

On each interval $[u_{l-1}, u_l]$ we set $W(\tilde{u})$ to be the horizontal line segment connecting $M(u_{l-1})$ and $M(u_l)$, if the third coordinate of those points are equal, or a R-helix otherwise.
**Proposition 6.** Let $M(u) : [a, b] \to \mathbb{R}^3$ be a $C^2$-smooth curve, $W(\tilde{u}) : [a, b] \to \mathbb{R}^3$ its piecewise approximation by R-helices and line segments derived from a partition (13), K the maximum curvature of $M(u)$, and $h \le \pi$ the maximum length of the curve segments $M(u)$ for $u \in [u_i, u_{i+1}]$. The Hausdorff distance of $M(u)$ and $W(\tilde{u})$ satisfies

$$ \Delta(M(u), W(\tilde{u})) \le \left(K + \frac{1}{4\pi}\right) h^2. $$

**Proof.** Consider the piecewise chord $L(\tilde{u})$, $\tilde{u} \in [a, b]$ of $M(u)$, which is a piecewise linear curve satisfying

$$ L(u_i) = M(u_i), \quad \forall i \in \{0, 1, \dots, k\}, $$

i.e., $L(\tilde{u})$ is the chord of $M(u)$ on each interval $[u_i, u_{i+1}]$. By Lemma 4,

$$ \Delta(M(u), L(\tilde{u})) \le Kh^2. \qquad (18) $$

Moreover, $L(\tilde{u})$ is also a piecewise chord of $W(\tilde{u})$, the curve formed by piecewise R-helices and horizontal line segments. On the linear parts of $W(\tilde{u})$, $L(\tilde{u})$ and $W(\tilde{u})$ coincide. By $\Lambda$ we denote the maximum length of $L(\tilde{u})$, $\tilde{u} \in [u_{i-1}, u_i]$. Since $h \le \pi$, we also have $\Lambda \le \pi$. Hence, by Lemma 5,

$$ \Delta(W(\tilde{u}), L(\tilde{u})) \le \frac{1}{4\pi}\Lambda^2 \le \frac{1}{4\pi}h^2. \qquad (19) $$

Combining (18) and (19), we obtain

$$ \Delta(M(u), W(\tilde{u})) \le \Delta(M(u), L(\tilde{u})) + \Delta(L(\tilde{u}), W(\tilde{u})) \le \left(K + \frac{1}{4\pi}\right) h^2. \quad \square $$

## 4. Approximation procedure

Let $M(u) = (v_x(u), v_y(u), \varphi(u))$, $u \in [a, b]$, be a planar motion. We approximate $M(u)$ by a motion $W(\tilde{u})$, $\tilde{u} \in [a, b]$, consisting of piecewise rotational and translational motions.

The approximation procedure consists of the following steps:

1. We choose a positive integer $k \in \mathbb{N}$ and select a (not necessarily uniform) partition

$$ a = u_0 < u_1 < \dots < u_k = b $$

of the interval $[a, b]$.

2. We sample the motion at the parameter values $u_i$ for $i = 0, 1, \dots, k$. Each sample is a displacement

$$ M(u_i) = (v_x^{(i)}, v_y^{(i)}, \varphi^{(i)}). $$

We assume that the representatives of any two consecutive samples $M(u_{i-1})$ and $M(u_i)$ satisfy

$$ -\pi < \varphi^{(i-1)} - \varphi^{(i)} \le \pi. $$

3. For any two consecutive samples $M(u_{i-1})$ and $M(u_i)$, there exists a unique rotational motion or translational motion $W^{(i)}(\tilde{u})$ satisfying

$$ W^{(i)}(u_{i-1}) = M(u_{i-1}) \quad \text{and} \quad W^{(i)}(u_i) = M(u_i). $$

This motion is represented by a R-helix or by a horizontal line segment in $\mathbb{R}^3$, in both cases using a parameterization with constant parametric speed. Algorithm 1 returns the motion $W^{(i)}(\tilde{u})$ interpolating two given displacements using a (local) parameter $\tilde{u} \in [0, 1]$:

$$ W^{(i)}(\tilde{u}) = \text{interpolate}((v_x^{(i-1)}, v_y^{(i-1)}, \varphi^{(i-1)}), (v_x^{(i)}, v_y^{(i)}, \varphi^{(i)}), \tilde{u}, \varepsilon). $$

It is conceptually simple but relies on a fixed point computation, which may become unstable if the algorithm is implemented using floating point numbers. An alternative method is presented in the Appendix.

**Algorithm 1** interpolate $((v_x^{(\ell)}, v_y^{(\ell)}, \varphi^{(\ell)}), (v_x^{(r)}, v_y^{(r)}, \varphi^{(r)}), \tilde{u})$

1: if $\varphi^{(\ell)} = \varphi^{(r)}$ then

2: return TM[$v_x^{(\ell)}, v_x^{(r)}, v_y^{(\ell)}, v_y^{(r)}, \varphi^{(\ell)}$]($\tilde{u}$)

3: else

4: $\quad (r_x, r_y)^T \leftarrow$ fixed point of $(v_x^{(r)}, v_y^{(r)}, \varphi^{(r)}) \circ (v_x^{(\ell)}, v_y^{(\ell)}, \varphi^{(\ell)})^{-1}$

5: $\quad (\hat{r}_x, \hat{r}_y)^T \leftarrow (v_x^{(\ell)} - r_x, v_y^{(\ell)} - r_y)^T$

6: return RM[$r_x, r_y, \hat{r}_x, \hat{r}_y, \varphi^{(\ell)}, \varphi^{(r)}$]($\tilde{u}$)

7: end if
4. We define the piecewise motion $W(\tilde{u})$, $\tilde{u} \in [a, b]$, approximating $M(u)$ by collecting the motion segments $W^{(i)}(\tilde{u})$:

$$W(\tilde{u}) = W^{(i)}(\tilde{u}), \quad \text{if } \tilde{u} \in [u_{i-1}, u_i]. \qquad (20)$$

In many applications of algorithms in numerical analysis, a continuous dependency of the generated output from the given input values is desirable, and this is clearly true for the problem considered in this paper. Algorithm 1, however, contains an if-then statement and therefore does not directly guarantee continuity of the resulting motion. In the rest of this section we show that the piecewise motion $W(\tilde{u})$ of the form (20) nevertheless depends continuously on the data.

We consider two planar motions $M(u)$ and $\tilde{M}(u)$ with the same parameter domain $[a, b]$. For some $k \in \mathbb{N}$, let $a = u_0 < u_1 < \dots < u_k = b$ be a partition of $[a, b]$. Let $M(u_{i-1})$, $M(u_i)$ and $\tilde{M}(u_{i-1})$, $\tilde{M}(u_i)$ be two pairs of consecutive samples of the two motions and $W(\tilde{u})$, $\tilde{W}(\tilde{u})$ be the rotational or translational motions that approximate $M(u)$ and $\tilde{M}(u)$ on the interval $[a, b]$.

For given parameter values $u_0, \tilde{u}_0 \in [a, b]$ we write

$$\tilde{M}(\tilde{u}_0) \to M(u_0) \quad \text{if} \quad \|\tilde{M}(\tilde{u}_0) - M(u_0)\|_{\sim} \to 0.$$

**Proposition 7.** Let $M(u)$ and $\tilde{M}(u)$, $u \in [a, b]$, be two planar motions and $M(u_{i-1})$, $M(u_i)$ and $\tilde{M}(u_{i-1})$, $\tilde{M}(u_i)$ be two pairs of consecutive samples of the two motions such that

$$\tilde{M}(u_{i-1}) \to M(u_{i-1}) \quad \text{and} \quad \tilde{M}(u_i) \to M(u_i). \qquad (21)$$

Let $W(\tilde{u}), \tilde{W}(\tilde{u})$ be the rotational or translational motions approximating $M(u)$ and $\tilde{M}(u)$ on the interval $[u_{i-1}, u_i]$. Then

$$\Delta(W(\tilde{u}), \tilde{W}(\tilde{u})) \to 0.$$

We prepare the proof by considering a special case:

**Lemma 8.** If $M(u_{i-1}) = \tilde{M}(u_{i-1})$ and $\tilde{M}(u_i) \to M(u_i)$, then

$$\Delta(W(\tilde{u}), \tilde{W}(\tilde{u})) \to 0 \quad \tilde{u}, \tilde{u} \in [u_{i-1}, u_i].$$

**Proof.** By suitably choosing the coordinate system, we can assume that

$$M(u_{i-1}) = \tilde{M}(u_{i-1}) = (0, 0, 0), \quad M(u_i) = (v_x, 0, \varphi), \quad \tilde{M}(u_i) = (\tilde{v}_x, \tilde{v}_y, \tilde{\varphi}), \qquad (22)$$

where $-\pi < \varphi, \tilde{\varphi} \le \pi$.

Case 1: $\varphi = \tilde{\varphi} = 0$. Both $W(\tilde{u})$ and $W(\tilde{u})$, $\tilde{u}, \tilde{u} \in [u_{i-1}, u_i]$, are translational motions and from the assumptions (22) it follows

$$\Delta(W(\tilde{u}), \tilde{W}(\tilde{u})) \le \|W(u_i) - \tilde{W}(u_i)\|_{\sim} = \|W(u_i) - \tilde{W}(u_i)\| = \sqrt{(v_x - \tilde{v}_x)^2 + (\tilde{v}_y)^2}. \qquad (23)$$

Case 2: $\varphi = 0$ and $\tilde{\varphi} \ne 0$. Then $W(\tilde{u})$ is a translational motion and $\tilde{W}(\tilde{u})$ is a rotational motion. Let

$$L(\tilde{u}) = (1 - \tilde{u})\tilde{M}(u_{i-1}) + \tilde{u}\tilde{M}(u_i), \quad \tilde{u} \in [0, 1]$$

be a chord of $\tilde{W}(\tilde{u})$. Then we can bound the distance of $W(\tilde{u})$ and $\tilde{W}(\tilde{u})$ by the sum

$$\begin{aligned} \Delta(W(\tilde{u}), \tilde{W}(\tilde{u})) &\le \Delta(W(\tilde{u}), L(\tilde{u})) + \Delta(L(\tilde{u}), \tilde{W}(\tilde{u})) \\ &\le \|W(u_i) - L(1)\|_{\sim} + \|\tilde{W}(\frac{u_{i-1} + u_i}{2}) - L(\frac{1}{2})\|_{\sim} \\ &\le \sqrt{(v_x - \tilde{v}_x)^2 + \tilde{v}_x^2 + \tilde{\varphi}^2 + \frac{1}{2}\sqrt{(\tilde{v}_x^2 + \tilde{v}_y^2)\tan^2(\frac{\varphi}{4})}}. \end{aligned} \qquad (24)$$

The first term in each line on the right-hand side is the Hausdorff distance of two lines with a common starting point (thus is attained at their end points). The second term is the Hausdorff distance of an R-helix and its chord, which is attained at their midpoints.

Case 3: $\varphi, \tilde{\varphi} \ne 0$. Both $W(\tilde{u})$ and $\tilde{W}(\tilde{u})$ are rotational motions and

$$\Delta(W(\tilde{u}), \tilde{W}(\tilde{u})) \le \|W(u_i) - \tilde{W}(u_i)\| = \sqrt{(v_x - \tilde{v}_x)^2 + (v_y - \tilde{v}_y)^2 + (\varphi - \tilde{\varphi})^2}. \qquad (25)$$

We complete the proof by noting that $\Delta(W(\tilde{u}), \tilde{W}(\tilde{u})) \to 0$ as

$$\tilde{v}_x \to v_x, \quad \tilde{v}_y \to 0 \quad \text{and} \quad \tilde{\varphi} \to \varphi,$$

since all the right-hand sides of (23), (24) and (25) converge to 0. $\square$

To prove the general case, we also need the following lemma:

**Lemma 9.** We consider a planar motion $M(u)$ and a displacement $\hat{D} \in \mathbb{R}^3$. Then

$$\|\hat{D} \circ M(u) - M(u)\|_{\sim} \to 0$$

$$\text{as } \|\hat{D}\|_{\sim} \to 0.$$
**Proof.** Clearly, $||\hat{D}||_\sim \to 0$ implies $\hat{D} \to (0, 0, 0)_\sim$. Consequently, the right-hand side of (5) tends to $M(u)$ as $||\hat{D}||_\sim \to 0$. □

Now we proceed with the proof:

**Proof of Proposition 7.** We denote $\hat{D} = M(u_{l-1}) \circ \tilde{M}^{-1}(u_{l-1})$. The triangle inequality implies

$$ \Delta(W(\tilde{u}), \tilde{W}(\tilde{u})) \le \Delta(W(\tilde{u}), \hat{D} \circ \tilde{W}(u^+)) + \Delta(\hat{D} \circ \tilde{W}(u^+), \tilde{W}(\tilde{u})) \quad (26) $$

for any parameter $u^+ \in [a, b]$. First we note

$$ W(u_{l-1}) = \hat{D} \circ \tilde{W}(u_{l-1}) = M(u_{l-1}). $$

Second we use (21) to confirm that

$$ \hat{D} \circ \tilde{W}(u_i) \to W(u_i). $$

Consequently, the first term on the right-hand side of (26) converges to zero according to Lemma 8. The other term also converges to zero, since it is bounded by

$$ \max_{\tilde{u} \in [u_{l-1}, u_l]} ||\hat{D} \circ \tilde{W}(u^+), \tilde{W}(\tilde{u})||_\sim, $$

see (12), and

$$ ||\hat{D}||_\sim = ||M(u_{l-1}) \circ \tilde{M}^{-1}(u_{l-1})||_\sim \to 0 $$

as $\tilde{M}(u_{l-1}) \to M(u_{l-1})$, cf. Lemma 9. This concludes the proof. □

## 5. Swept volume approximation

Let $M(u), u \in [a, b]$ be a planar motion corresponding to a $C^2$-smooth curve in $\mathbb{R}^3$, and let $W(\tilde{u}), \tilde{u} \in [a, b]$, be the piecewise motion approximating $M(u)$ of the form (20). For a point $\mathbf{p} \in \mathbb{R}^2$, we denote by

$$ M(u)(\mathbf{p}), u \in [a, b] $$

its trajectory under the motion $M(u)$, and by

$$ W(\tilde{u})(\mathbf{p}), \tilde{u} \in [a, b] $$

its trajectory under $W(\tilde{u})$, which is a curve formed by circular arcs and line segments.

**Corollary 10.** For a motion $M(u)$, its piecewise approximation $W(\tilde{u})$ of the form (20) and any point $\mathbf{p} \in \mathbb{R}^2$ it holds that

$$ \delta(M(u)(\mathbf{p}), W(\tilde{u})(\mathbf{p})) \le \left(K + \frac{1}{4\pi}\right) (1 + \|\mathbf{p}\|)h^2, $$

where the constants $K$ and $h$ are defined as in Proposition 6.

**Proof.** By Proposition 6, the distance of $M(u)$ and $W(\tilde{u})$ in the kinematic image space is

$$ \Delta(M(u), W(\tilde{u})) \le \left(K + \frac{1}{4\pi}\right) h^2. $$

Hence, by Lemma 3, it follows

$$ \delta(M(u)(\mathbf{p}), W(\tilde{u})(\mathbf{p})) \le \left(K + \frac{1}{4\pi}\right) (1 + \|\mathbf{p}\|)h^2. \quad \square $$

We consider a compact planar set $\Omega \subset \mathbb{R}^2$. At each instance of the time parameters $u, \tilde{u} \in [a, b]$, the object $\Omega$ is transformed by $M(u)$ and $W(\tilde{u})$ according to

$$ M(u)(\Omega) = \{M(u)(\mathbf{p}) | \mathbf{p} \in \Omega\}, $$

$$ W(\tilde{u})(\Omega) = \{W(\tilde{u})(\mathbf{p}) | \mathbf{p} \in \Omega\}. $$

We are mainly interested in the swept volumes

$$ \Omega_M = \bigcup_{u \in [a, b]} M(u)(\Omega), \quad (27) $$

$$ \Omega_W = \bigcup_{\tilde{u} \in [a, b]} W(\tilde{u})(\Omega). \quad (28) $$

We recall the Hausdorff distance of two compact sets, which is defined similarly to (10). Let $A, B \subset \mathbb{R}^2$ be two compact planar sets. We define the Hausdorff distance of the two sets to be

$$ \delta(A, B) = \max\{\delta^*(A, B), \delta^*(B, A)\}. $$
<figure><img src="image_6.png" /><figcaption>Fig. 4. A planar compact set undergoing a motion defines a planar swept volume (left). The maximal error of the point trajectories converges quadratically to zero (right).</figcaption></figure>

where

$$ \delta^*(A, B) = \max_{\mathbf{p} \in A} \min_{\hat{\mathbf{p}} \in B} \|\mathbf{p} - \hat{\mathbf{p}}\|. $$

The following corollary gives us a bound on the Hausdorff distance of a swept volume of an object under a motion $M(u)$ and the swept volume of the object under the motion $W(\tilde{u})$ approximating $M(u)$.

**Corollary 11.** Given a motion $M(u)$, $u \in [a, b]$, its piecewise approximation $W(\tilde{u})$, $\tilde{u} \in [a, b]$, of the form (20) and a compact planar set $\Omega$, there exists a constant $C_{\Omega} \in \mathbb{R}$ depending on $\Omega$, such that

$$ \delta(\Omega_M, \Omega_W) \le C_{\Omega} \left( K + \frac{1}{4\pi} \right) h^2, $$

where the constants $K$ and $h$ are defined as in **Proposition 6**.

**Proof.** By Corollary 10, for any point $\mathbf{p} \in \Omega$,

$$ \delta(M(u)(\mathbf{p}), W(\tilde{u})(\mathbf{p})) \le \left( K + \frac{1}{4\pi} \right) (1 + \|\mathbf{p}\|)h^2. $$

Hence, by Eqs. (27), (28),

$$ \begin{aligned} \delta(\Omega_M, \Omega_W) &\le \max_{\mathbf{p} \in \Omega} \delta(M(u)(\mathbf{p}), W(\tilde{u})(\mathbf{p})) \\ &\le \left( K + \frac{1}{4\pi} \right) h^2 \max_{\mathbf{p} \in \Omega} (1 + \|\mathbf{p}\|), \end{aligned} $$

and let

$$ C_{\Omega} = 1 + \max_{\mathbf{p} \in \Omega} \|\mathbf{p}\|. $$

Since $\Omega$ is compact, $C_{\Omega} \in \mathbb{R}$. $\square$

The trajectory of each point $\mathbf{p} \in \Omega$ under the motion $W(\tilde{u})$ is a curve composed of circular arcs and line segments. Hence, for an arc spline domain, which is a compact planar domain with the circular/linear boundary, the volume swept by the domain and the motion $W(\tilde{u})$ is again an arc spline domain.

We conclude this section by presenting several computed examples, in order to confirm the theoretical results.

**Example 1.** We consider a planar compact set $\Omega$ transformed by a motion $M(u)$. The planar swept volume $\Omega_M$ is shown in Fig. 4 (left). We compute Hausdorff distances between trajectories of points of $\Omega$ under $M(u)$ and its piecewise approximation $W(\tilde{u})$ for increasing number of subintervals. Fig. 4 (right) confirms the quadratic convergence of the maximal trajectory error (scaled by the diameter of the bounding box of the swept volume).

**Example 2.** We consider three planar compact sets and a motion $M(u)$. The motion transforms the sets and creates three different swept volumes shown in Fig. 5 (left). The darker regions of the swept volume are covered multiple times by the moving object. For each of the sets we compute the maximal trajectory error for increasing number of subintervals. According to Corollary 10, this error depends on the norm of each point and on the Hausdorff distance of the curve $M(u)$ and the piecewise curve $W(\tilde{u})$ in the kinematic image space. The three sets have different distances to the origin, and this leads to different trajectory errors, in particular for a small number of segments.
<figure><img src="image_7.png" /><figcaption>Fig. 5. A planar motion transforming three different planar sets (left). The trajectory errors depend on the norms of the points, the distance of the motion and its approximation in the kinematic image space depends only on the motion (right).</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 6. A swept volume of a planar set under a motion $M(u)$, the highlighted values of the parameter $u$ correspond to the shown positions of the set (left). Using the adaptive sampling method we can obtain lower errors for the same number of segments (right).</figcaption></figure>

**Example 3.** A possible way to improve the distance of point trajectories is to subdivide the parameter interval adaptively rather than uniformly. We consider a planar motion $M(u)$, $u \in [u_{\min}, u_{\max}]$, and a planar compact set $\Omega$, see Fig. 6 (left). We choose a tolerance $\varepsilon$ and use an adaptive sampling method for approximation of the motion, e.g. the following:

1. Compute the rotational or translational motion $W(\tilde{u})$ interpolating $M(u)$ on the interval $[u_{\min}, u_{\max}]$.

2. Compute the maximal distance $d$ between trajectories of points of $\Omega$ under $M(u)$ and $W(\tilde{u})$.

3. If $d > \varepsilon$, divide the interval in half and repeat the procedure on both intervals $[u_{\min}, \frac{u_{\min}+u_{\max}}{2}]$ and $[\frac{u_{\min}+u_{\max}}{2}, u_{\max}]$.

We compare the convergences of the error in the point trajectories for the adaptive and uniform sampling methods with respect to number of subintervals in Fig. 6 (right). The distribution of the sampled parameter values for 32 subintervals is also shown in Fig. 6 (left).

## 6. Conclusion

We presented an algorithm for approximating planar motions by motions with piecewise circular/linear trajectories. We analyzed the approximation error and demonstrated that we obtain quadratic approximation order both for point trajectories and for the swept volumes. Moreover we showed that the resulting approximating motion depends continuously on the input data of the interpolation procedure.

In the second part of this paper series will apply these results to efficiently compute swept volumes, by creating an arc spline representation thereof. This demonstrates once more the suitability of circular arc splines for computational geometry, due to their ability to combine simplicity of fundamental operations with high geometric flexibility and substantial approximation power.

## Data availability

Data will be made available on request.
Acknowledgment

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

Appendix. An alternative to fixed point computation

Algorithm 1 depends on the computation of the fixed point of a displacement. Numerically, the computation via definition (4) is highly ill-conditioned for angles close to zero. We present a more stable method for computing the fixed point via approximate null space computation.

We consider the level sets (also called contour curves) of the bivariate quadratic polynomial

$$f(x, y) = a(x^2 + y^2) + bx + cy,$$

with some coefficients a, b, c ∈ ℝ, which are assumed to fulfill a² + b² + c² = 1. If a ≠ 0, its level sets are concentric circles, and parallel straight lines otherwise. Consequently, a rotational or translational motion corresponds to a unique pair of polynomials ±f(x, y) where the point trajectories appear as level sets.

We consider a number of non-collinear points p_j = (p_{jx}, p_{jy})^T, j = 1, ..., n, in the moving space, sampled from the moving object. Two consecutive displacements M(u_{i-1}), M(u_i) sampled from a motion M(u) transform them into points

$$\mathbf{q}_{j}^{(i-1)} = (q_{jx}^{(i-1)}, q_{jy}^{(i-1)})^{T} = M(u_{i-1})(\mathbf{p}_{j}),$$

$$\mathbf{q}_{j}^{(i)} = (q_{jx}^{(i)}, q_{jy}^{(i)})^{T} = M(u_{i})(\mathbf{p}_{j}).$$

Considering the polynomial f that corresponds to the interpolating rotational or translational motion, we arrive at a homogeneous system of linear equations

$$f(q_{jx}^{(i-1)}, q_{jy}^{(i-1)}) - f(q_{jx}^{(i)}, q_{jy}^{(i)}) = 0, \quad j = 1, \dots, n,$$

for the three coefficients a, b, c ∈ ℝ. The solution thus belongs to the null space of the associated n×3-matrix and can be numerically computed, e.g., by using singular value decomposition. We choose a solution that satisfies a² + b² + c² = 1, which is unique (except for the sign ambiguity) if n ≥ 4 points are chosen. One may now proceed by generating the point trajectories directly from their implicit representation as level sets, thereby bypassing the computation of the fixed point. By suitably choosing the sampled points one may adapt the numerical performance to the geometry of the moving object.

References

[1] E. Bertolazzi, M. Frego, F. Biral, Interpolating splines of biarcs from a sequence of planar points, Comput.-Aided Des. Appl. 18 (1) (2020) 66–85.

[2] D.S. Meek, D.J. Walton, Approximation of discrete data by G¹ arc splines, Comput. Aided Des. 24 (6) (1992) 301–306.

[3] D.S. Meek, D.J. Walton, Approximating smooth planar curves by arc splines, J. Comput. Appl. Math. 59 (2) (1995) 221–231.

[4] D.S. Meek, D.J. Walton, Planar osculating arc splines, Comput. Aided Geom. Design 13 (7) (1996) 653–671.

[5] Z. Šír, R. Feichtinger, B. Jüttler, Approximating curves and their offsets using biarcs and Pythagorean hodograph quintics, Comput. Aided Des. 38 (6) (2006) 608–618.

[6] S. Brummer, G. Maier, T. Sauer, Numerically robust computation of circular visibility, Comput. Aided Geom. Design 59 (2018) 17–31.

[7] G. Maier, G. Pisinger, Approximation of a closed polygon with a minimum number of circular arcs and line segments, Computat. Geometry 46 (3) (2013) 263–275.

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

[9] O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, M. Rabl, Medial axis computation for planar free-form shapes, Comput.-Aided Des. 41 (5) (2009) 339–349.

[10] O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, M. Rabl, E. Pilgerstorfer, Divide-and-conquer for Voronoi diagrams revisited, Comput. Geometry: Theory Appl. 43 (8) (2010) 688–699.

[11] Y.J. Kim, J. Lee, M.S. Kim, G. Elber, Efficient offset trimming for planar rational curves using biarc trees, Comput. Aided Geom. Design 29 (7) (2012) 555–564, Geometric Modeling and Processing 2012.

[12] O. Aichholzer, W. Aigner, F. Aurenhammer, K. Čech Dobiášova, B. Jüttler, G. Rote, Triangulations with circular arcs, J. Graph Algorithms Appl. 19 (1) (2015) 43–65.

[13] S. Han, S.H. Yoon, M.S. Kim, G. Elber, Minkowski sum computation for planar freeform geometric models using G¹-biarcs approximation and interior disk culling, Vis. Comput. 35 (2019).

[14] B. Jüttler, S. Maroscheck, M.S. Kim, Q. Youn Hong, Arc fibrations of planar domains, Comput. Aided Geom. Design 71 (2019) 105–118.

[15] B. Weiß, B. Jüttler, F. Aurenhammer, Arc Fibration Kernels of Arc Spline Domains, Technical Report (95), Johannes Kepler University, Institute of Applied Geometry, Linz, 2021.

[16] K. Shoemake, Animating rotation with quaternion curves, in: International Conference on Computer Graphics and Interactive Techniques, 1985.

[17] O. Röschel, Rational motion design – a survey, Comput. Aided Des. 30 (3) (1998) 169–178, Motion Design and Kinematics.

[18] J. Siegele, D.F. Scharler, H.P. Schröcker, Rational motions with generic trajectories of low degree, Comput. Aided Geom. Design 76 (2020) 101793.

[19] K. Ferjančič, M. Krajnc, V. Vitrih, Construction of G³ rational motion of degree eight, Appl. Math. Comput. 272 (2016) 127–138, Subdivision, Geometric and Algebraic Methods, Isogeometric Analysis and Refinability.

[20] G. Jaklič, B. Jüttler, M. Krajnc, V. Vitrih, E. Žagar, Hermite interpolation by rational G⁸ motions of low degree, J. Comput. Appl. Math. 240 (2013) 20–30.

[21] B. Jüttler, M. Krajnc, E. Žagar, Geometric interpolation by quartic rational spline motions, in: Advances in Robot Kinematics: Motion in Man and Machine, Springer Netherlands, Dordrecht, 2010, pp. 377–384.

[22] K. Ferjančič, M. Knez, V. Vitrih, On C² rational motions of degree six, J. Comput. Appl. Math. 388 (2021).

[23] M. Knez, G¹ motion interpolation using cubic ph biarcs with prescribed length, Comput. Aided Geom. Design 67 (2018) 21–33.

[24] R.T. Farouki, C. Giannelli, A. Sestini, Rational minimal-twist motions on curves with rotation-minimizing Euler-Rodrigues frames, J. Comput. Appl. Math. 352 (2019) 240–254.

[25] M.G. Wagner, Planar rational B-spline motions, Comput. Aided Des. 27 (2) (1995) 129–137, NURBS: theory and practice.

[26] G. Mullineux, R. Cripps, B. Cross, Fitting a planar quadratic slerp motion, Comput. Aided Geom. Design 81 (2020) 101911.

[27] F. Reuleaux, A.B.W. Kennedy, The Kinematics of Machinery: Outlines of a Theory of Machines, Macmillan, 1876.