# Improving Angular Speed Uniformity
by Piecewise Radical Reparameterization

Hoon Hong Department of Mathematics
North Carolina State University
Box 8205, Raleigh, NC 27695, USA<EMAIL_ADDRESS>LMIB – IAI – School of
Mathematical Sciences
Beihang University
Beijing 100191, ChinaSMS – HCIC – School of Mathematics and Physics
Center for Applied Mathematics of Guangxi
Guangxi Minzu University
Nanning 530006, China Dongming Wang LMIB – IAI – School of Mathematical
Sciences
Beihang University
Beijing 100191, China<EMAIL_ADDRESS>SMS – HCIC – School of Mathematics
and Physics
Center for Applied Mathematics of Guangxi
Guangxi Minzu University
Nanning 530006, China Jing Yang Corresponding author.SMS – HCIC – School of
Mathematics and Physics
Center for Applied Mathematics of Guangxi
Guangxi Minzu University
Nanning 530006, China<EMAIL_ADDRESS>
###### Abstract

For a rational parameterization of a curve, it is desirable that its angular
speed is as uniform as possible. Hence, given a rational parameterization, one
wants to find re-parameterization with better uniformity. One natural way is
to use piecewise rational reparameterization. However, it turns out that the
piecewise rational reparameterization does not help when the angular speed of
the given rational parameterization is zero at some points on the curve. In
this paper, we show how to overcome the challenge by using piecewise radical
reparameterization.

##  1 Introduction

Parametric curves and surfaces are fundamental objects that are most
frequently used in computer aided geometric design. A given curve or surface
may have many different parameterizations, of which some may possess better
properties and thus are more suitable for certain applications than the
others. Thus, one often needs to convert one parameterization into another,
i.e., to re-parameterize the given parameterization (see, e.g., [2, 3, 4, 6,
7, 8, 9, 10, 11]). In this paper, we focus our investigation on an important
class of parameterizations, called uniform (angular-speed) parameterizations,
where the distribution of points are determined by the local curvature and
show how to construct such reparameterizations for a specific class of curves.

Uniform parameterization has been studied in a series of papers (see [5, 7, 9,
12, 15, 14, 13] and references therein). The authors have defined a function
of angular speed uniformity to measure the quality of any given
parameterization of a plane curve and proposed a method to compute its uniform
reparameterization. However, the computed reparameterization is irrational in
most cases (with straight lines as exceptions). For the sake of efficiency, a
framework has been proposed for the computation of rational approximations of
uniform parameterizations [5]. Four different methods of reparameterization
(i.e., optimal reparameterization with fixed degree, $C^{0}$ and $C^{1}$
optimal piecewise reparameterization, and nearly optimal $C^{1}$ piecewise
reparameterization) have been integrated into this framework. They have also
been generalized to compute uniform quasi-speed reparameterizations of
parametric curves in $n$-dimensional space.

However, there is still a major challenge: all the above-mentioned methods do
not work well when the angular speed of the given rational parameterization is
zero at some points on the curve. This is due to an intrinsic property of the
angular speed function [14]:

> _Let $\omega_{p}$ be an angular speed function of a curve $p$ and $r$ be a
> proper transformation. Then_
>
> $\omega_{p\circ r}=(\omega_{p}\circ r)\cdot r^{\prime}.$ (1)

Uniformizing the angular speed can be seen as modifying the angular speed
value at each point under the constraint (1) iteratively until all the values
are equal to the average. However, the constraint indicates that
$\omega_{p\circ r}$ will never reach the average value for any rational
$r^{\prime}$ when $\omega_{p}(t)=0$ for some $t$.

In this paper, we propose to overcome the challenge by using radical
transformations instead of rational ones. We show that radical transformations
allow one to increase the angular speed toward the average value at the points
where the angular speed is zero. Then we adapt the idea of piecewise Möbius
transformation from [12] and the strategies in [13] to optimally improve the
uniformity of angular speed.

Experiments show that the proposed approach can improve the angular speed
uniformity significantly when the angular speed of the given parameterization
vanishes at some point on the curve.

The rest of the paper is structured as follows. In Section 2, we formulate the
problem precisely. For this, we also introduce all the needed notations and
notions. In Section 3, we develop mathematical theory to tackle the problem.
In particular, we show how to use piecewise radical transformation to
transform an angular speed function with zeros into one without zero in such a
way that the parameters involved are also optimized. In Section 4, we
summarize the theoretical results into an algorithm and illustrate its
performance on an example. In Section 5, we briefly discuss implementational
issues/suggestions when floating point arithmetic is used.

##  2 Problem

Consider a regular parametric curve

$p=(x_{1}(t),\ldots,x_{n}(t)):\,\mathbb{R}\mapsto\mathbb{R}^{n}.$

Its _angular speed_ $\omega_{p}$ is given by the following expression (see
[5]):111The concept of angular speed is defined in the same manner as the one
in physics but for $p^{\prime}(t)$. The reason is to make the angular speed
independent of the origin.

$\omega_{p}=\dfrac{\sqrt{\sum\limits_{1\leq i<j\leq
n}\left|\begin{array}[c]{cc}x_{i}^{\prime\prime}&x_{j}^{\prime\prime}\\\
x_{i}^{\prime}&x_{j}^{\prime}\end{array}\right|^{2}}}{\sum\limits_{i=1}^{n}x_{i}^{\prime}{}^{2}}.$
(2)

Recall that the mean $\mu_{p}$ and the variation $\sigma_{p}^{2}$ of
$\omega_{p}$ are given by

$\mu_{p}=\int_{0}^{1}{\omega_{p}(t)}\,dt,\quad\mbox{and}\quad\sigma_{p}^{2}=\int_{0}^{1}{(\omega_{p}(t)-\mu_{p})^{2}}\,dt.$

###### Definition 1

The _angular speed uniformity_ $u_{p}$ of a parameterization $p$ is defined as

$u_{p}=\left\\{\begin{array}[c]{ll}\dfrac{1}{1+\sigma_{p}^{2}/\mu_{p}^{2}}&\quad\text{if
}\mu_{p}\neq 0,\\\ 1&\quad\text{otherwise.}\end{array}\right.$ (3)

######  Example 2 (Running)

Consider the parametric curve $p=(t,t^{3})$. Then

$\omega_{p}=\dfrac{6\,t}{9\,t^{4}+1},$

$\mu_{p}\doteq 1.249$ and $u_{p}\doteq 0.846$. The goal is to find a proper
parameter transformation $r$ over $[0,1]$ in order to increase the uniformity.

Recall the following results from [5]. For any proper parameter transformation
$r$ over $[0,1]$, we have

$\omega_{p\circ r}(s)=(\omega_{p}\circ r)(s)\cdot r^{\prime}(s)$ (4)

and

$u_{p\circ
r}=\dfrac{\mu_{p}^{2}}{\eta_{p,r}},\quad\mbox{where}\quad\eta_{p,r}=\int_{0}^{1}\dfrac{\omega_{p}^{2}}{(r^{-1})^{\prime}}(t)\,dt.$
(5)

By [14, Theorem 2], one can construct a uniform reparameterization from $p$,
but such a reparameterization is irrational in most cases. Therefore, we
proposed several methods in [5] to improve the angular speed uniformity by
computing piecewise rational reparameterizations. However, those methods are
not applicable to curves whose angular speed may vanish over $[0,1]$.
Intuitively speaking, uniformizing the angular speed over $[0,1]$ can be
viewed as getting all the values of $\omega_{p}(t)$ (for all $t\in[0,1]$) as
close to $\mu_{p}$ as possible.

If $r$ is a continuous rational function over $[0,1]$, then $r^{\prime}$ is
bounded. Suppose that $\omega_{p}(t_{0})=0$ for some $t_{0}\in[0,1]$ and
$\mu_{p}\neq 0$. Then by (4), there must exist some $s_{0}\in[0,1]$ such that
$\omega_{p\circ r}(s_{0})=0$, which is not close to $\mu_{p}$ at all. This
makes rational proper parameter transformations invalid. In what follows, we
resort to radical transformations and develop a new approach to uniformize the
angular speed of parametric curves which has zeros over $[0,1]$.

Let $p$ be a parametric curve. Without loss of generality, we assume that

$p^{\prime}(t)=(x_{1}^{\prime}(t),\ldots,x_{n}^{\prime}(t))=\Big{(}\frac{X_{1}(t)}{W(t)},\cdots,\frac{X_{n}(t)}{W(t)}\Big{)},$

where $X_{i}(t),W(t)\in\mathbb{R}[t]$ and
$\gcd(X_{1}(t),\ldots,X_{n}(t),W(t))=1$. One can verify that

$\omega_{p}=\dfrac{\sqrt{F}}{\sum\limits_{i}X_{i}{}^{2}},\quad\text{where}\quad
F=\sum\limits_{i\neq
j}\left|\begin{array}[c]{cc}X_{i}^{\prime}&X_{j}^{\prime}\\\
X_{i}&X_{j}\end{array}\right|^{2}.$

Let $F$ be written as
$F=\left(\prod_{i=0}^{k}(t-\tilde{t}_{i})^{2\,\mu_{i}}\right)\zeta(t)$ for
positive $k$. Note that $\\{\tilde{t}_{i}:\,\tilde{t}_{i}<\tilde{t}_{i+1}\
\text{for}\ 0\leq i<k\\}$ contains all the zeros of $F$ over $[0,1]$. It is
allowed that some $t_{i}$’s are not the roots of $F$. The positive integer
$\mu_{i}\in\mathbb{N}$ is called the _multiplicity_ of $\tilde{t}_{i}$ in
$\omega_{p}$ and denoted by ${\mathtt{mult}}(\omega_{p},\tilde{t}_{i})$. If
$\omega_{p}(\tilde{t}_{i})\neq 0$, then
${\mathtt{mult}}(\omega_{p},\tilde{t}_{i})=0$.

Let

$T=(t_{0},\ldots,t_{N}),\quad S=(s_{0},\ldots,s_{N}),\quad
Z=(z_{0},\ldots,z_{N}),\quad\alpha=(\alpha_{0},\ldots,\alpha_{N-1})$

be sequences such that

  * •

$0=t_{0}<\cdots<t_{N}=1$, $0=z_{0}<\cdots<z_{N}=1$, $0=s_{0}<\cdots<s_{N}=1$,
$0<\alpha_{i}<1$;

  * •

at most one of $\omega_{p}(t_{i})=0$ and $\omega_{p}(t_{i+1})=0$ holds for
$0\leq i<N$, that is, the successive appearance of two zeros of $\omega_{p}$
are not allowed;

  * •

the multiplicity of $t_{i}$ in $\omega_{p}$ is $\mu_{i}$;

  * •

$\omega_{p}(t)\neq 0$ for all $t\in(t_{i},t_{i+1})$.

######  Definition 3 (Elementary Piecewise Radical Transformation)

Let $p$ be a parametric curve with $T,S$ defined above. Then $\varphi$ is
called an _elementary piecewise radical transformation_ associated to $p$ if
$\varphi$ has the following form:

$\varphi(s)=\left\\{\begin{array}[c]{cll}\vdots{}&&\\\
\varphi_{i}(s)&\quad\text{if}&s\in[s_{i},s_{i+1}],\\\
\vdots{}&&\end{array}\right.\vspace{-.5em}$

where

$\varphi_{i}(s)=\left\\{\begin{array}[c]{ll}t_{i}+\Delta
t_{i}\sqrt[\mu_{i}+1]{\tilde{s}}&\mbox{if~{}}\omega_{p}(t_{i})=0;\\\\[8.0pt]
t_{i}+\Delta
t_{i}(1-\sqrt[\mu_{i+1}+1]{1-\tilde{s}})&\mbox{if~{}}\omega_{p}(t_{i+1})=0;\\\\[8.0pt]
t_{i}+\Delta t_{i}\cdot\tilde{s}&\mbox{otherwise,}\end{array}\right.$ (6)

and $\Delta t_{i}=t_{i+1}-t_{i},\,\Delta s_{i}=s_{i+1}-s_{i}$,
$\tilde{s}=(s-s_{i})/\Delta s_{i}$.

###### Remark 4

  1. 1.

It can be verified that $\varphi(s_{i})=t_{i}$ and $\varphi(s_{i+1})=t_{i+1}$,
which implies that $\varphi$ is with $C^{0}$ continuity.

  2. 2.

It is allowed that more than one intermediate point lie between two zeros of
$\omega_{p}$ because it can reduce the number of radical pieces and thus
enhance the efficiency of generating points with the new parameterization.

It can be shown that $\omega_{p\circ\varphi}(s)\neq 0$ (see Theorem 7). Next
let $q=p\circ\varphi$ and thus $q$ has no inflation point. We adapt the
reparameterization methods from [13] to increase the uniformity of
$\omega_{q}$ to any value close to 1. For this purpose, we recall the
following piecewise Möbius transformation.

######  Definition 5 (Piecewise Möbius Transformation)

Let $p$ be a parametric curve with $S,Z,\alpha$ defined above. Then $m$ is
called a _piecewise Möbius transformation_ associated to $p$ if $m$ has the
following form:

$m(z)=\left\\{\begin{array}[c]{cll}\vdots{}&&\\\
m_{i}(z)&\quad\text{if}&z\in[z_{i},z_{i+1}],\\\ \vdots{}&&\end{array}\right.$

where

$m_{i}(z)=s_{i}+\Delta
s_{i}\cdot\dfrac{(1-\alpha_{i})\tilde{z}}{(1-\alpha_{i})\tilde{z}+\alpha_{i}(1-\tilde{z})}$
(7)

and $\Delta z_{i}=z_{i+1}-z_{i},\,\Delta s_{i}=s_{i+1}-s_{i}$,
$\tilde{z}=(z-z_{i})/\Delta z_{i}$.

The problem addressed in this paper may be formulated as follows.

###### Problem 6

Given a parametric curve $p$ with $\omega_{p}(t)=0$ for some $t\in[0,1]$, find
a radical piecewise transformation $\varphi$ and an optimal piecewise Möbius
transformation $m$ over $[0,1]$ such that

  * •

$u_{p\circ\varphi\circ{m}}\doteq 1$;

  * •

$\forall s\in[0,1]$, $\omega_{p\circ\varphi\circ{m}}(s)\neq 0$.

##  3 Theory

###  3.1 Property of $\varphi$

###### Theorem 7

For any $s\in[0,1]$, $\omega_{p\circ\varphi}(s)\neq 0$.

######  Proof 3.8.

Taking derivative of $\varphi_{i}$, we have

$\varphi_{i}^{\prime}(s)=\left\\{\begin{array}[]{ll}\dfrac{\Delta
t_{i}}{\mu_{i}+1}\cdot\dfrac{1}{\sqrt[\mu_{i}+1]{\tilde{s}^{\mu_{i}}}}\cdot\dfrac{1}{\Delta
s_{i}}&\mbox{if~{}}\omega_{p}(t_{i})=0;\\\ \dfrac{\Delta
t_{i}}{\mu_{i+1}+1}\cdot\dfrac{1}{\sqrt[\mu_{i+1}+1]{(1-\tilde{s})^{\mu_{i+1}}}}\cdot\dfrac{1}{\Delta
s_{i}}&\mbox{if~{}}\omega_{p}(t_{i+1})=0;\\\ \dfrac{\Delta t_{i}}{\Delta
s_{i}}&\mbox{otherwise}.\end{array}\right.$

Next we show that in the above three cases, $\omega_{p\circ\varphi}(s)\neq 0$.

  1. Case 1:

$\omega_{p}(t_{i})=0.$

Assume that $\mu_{i}={\texttt{mult}}(\omega_{p},t_{i})$. Then $\omega_{p}$ can
be written as

$\omega_{p}=|t-t_{i}|^{\mu_{i}}\cdot\tilde{\zeta}(t),$

where $\tilde{\zeta}(t)>0$ for $t\in[t_{i},t_{i+1}]$. Therefore,

$\displaystyle\omega_{p\circ\varphi}(s)$
$\displaystyle=~{}|\varphi_{i}(s)-t_{i}|^{\mu_{i}}\cdot(\tilde{\zeta}\circ\varphi_{i})(s)\cdot\varphi_{i}^{\prime}(s)$
$\displaystyle=(\Delta
t_{i}\tilde{s}^{\frac{1}{\mu_{i}+1}})^{\mu_{i}}\cdot(\tilde{\zeta}\circ\varphi_{i})(s)\cdot\left[\dfrac{\Delta
t_{i}}{\mu_{i}+1}\cdot\dfrac{1}{\sqrt[\mu_{i}+1]{\tilde{s}^{\mu_{i}}}}\cdot\dfrac{1}{\Delta
s_{i}}\right]$ $\displaystyle=\dfrac{\Delta
t_{i}^{\mu_{i}+1}}{\mu_{i}+1}\cdot(\tilde{\zeta}\circ\varphi_{i})(s)\cdot\dfrac{1}{\Delta
s_{i}}$ $\displaystyle=\dfrac{\Delta
t_{i}^{\mu_{i}+1}}{\mu_{i}+1}\cdot\dfrac{1}{\Delta
s_{i}}\cdot\tilde{\zeta}(t)\neq 0$

for $s\in[s_{i},s_{i+1}]$.

  2. Case 2:

$\omega_{p}(t_{i+1})=0$.

Assume that $\mu_{i+1}={\texttt{mult}}(\omega_{p},t_{i+1})$. Then $\omega_{p}$
can be written as

$\omega_{p}=|t_{i+1}-t|^{\mu_{i+1}}\cdot\tilde{\zeta}(t),$

where $\tilde{\zeta}(t)>0$ for $t\in[t_{i},t_{i+1}]$. Therefore,

$\displaystyle\omega_{p\circ\varphi}(s)$
$\displaystyle=\,|t_{i+1}-\varphi_{i}(s)|^{\mu_{i+1}}\cdot(\tilde{\zeta}\circ\varphi_{i})(s)\cdot\varphi_{i}^{\prime}(s)$
$\displaystyle=\,\dfrac{\Delta
t_{i}}{\mu_{i+1}+1}\cdot\dfrac{1}{\sqrt[\mu_{i+1}+1]{(1-\tilde{s})^{\mu_{i+1}}}}\cdot\dfrac{1}{\Delta
s_{i}}$ $\displaystyle=\,[\Delta
t_{i}(1-\tilde{s})^{\frac{1}{\mu_{i+1}+1}}]^{\mu_{i+1}}$ $\displaystyle\ \ \ \
\cdot(\tilde{\zeta}\circ\varphi_{i})(s)\cdot\dfrac{\Delta
t_{i}}{\mu_{i+1}+1}\cdot\dfrac{1}{\sqrt[\mu_{i+1}+1]{(1-\tilde{s})^{\mu_{i+1}}}}\cdot\dfrac{1}{\Delta
s_{i}}$ $\displaystyle=\,\dfrac{\Delta
t_{i}^{\mu_{i+1}+1}}{\mu_{i+1}+1}\cdot(\tilde{\zeta}\circ\varphi_{i})(s)\cdot\dfrac{1}{\Delta
s_{i}}$ $\displaystyle=\,\dfrac{\Delta
t_{i}^{\mu_{i+1}+1}}{\mu_{i+1}+1}\cdot\tilde{\zeta}(t)\cdot\dfrac{1}{\Delta
s_{i}}\neq 0.$

  3. Case 3:

$\omega_{p}(t_{i})\omega(t_{i+1})\neq 0$.

Combining $\omega_{p}(t)\neq 0$ for $t\in[t_{i},t_{i+1}]$, ${\Delta t_{i}>0}$
and ${\Delta s_{i}>0}$, we have

$\omega_{p\circ\varphi}(s)=(\omega_{p}\circ\varphi)(s)\cdot\varphi^{\prime}(s)=\omega_{p}(t)\cdot\dfrac{\Delta
t_{i}}{\Delta s_{i}}\neq 0.$

To sum up, we have $\omega_{p\circ\varphi}(s)\neq 0$ when
$s\in[s_{i},s_{i+1}]$.

######  Example 3.9 (Continued from Example 2).

For the cubic curve $p=(t,t^{3})$ whose angular speed is
$\omega_{p}=\dfrac{6\,t}{9\,t^{4}+1},$ it is easy to see that $t=0$ is a zero
of $\omega_{p}$ with multiplicity $1$. Let $T=(0,1)$ and $S=(0,1)$. Then the
constructed $\varphi$ is $\varphi(s)=\sqrt{s}$. It follows that

$\omega_{p\circ\varphi}(s)=(\omega_{p}\circ\varphi)(s)\cdot\varphi^{\prime}(s)=\dfrac{6\,\sqrt{s}}{9\,s^{2}+1}\cdot\dfrac{1}{2\,\sqrt{s}}=\dfrac{3}{9\,s^{2}+1}$

which is nonzero over $[0,1]$.

######  Remark 3.10.

It may be further deduced that $\omega_{p\circ\varphi}(s)$ is discontinuous at
$s=s_{i}$.

###  3.2 Choice of $T$

By Definition 3, $T$ should contain all the zeros of $\omega_{p}$ over $[0,1]$
and some intermediate points in the subintervals separated by the zeros of
$\omega_{p}$. One question is how to choose intermediate points to make the
uniformity improvement as significant as possible. In this subsection, we
present a strategy similar to the one introduced in [13] for determining such
points.

Recall [14, Theorem 2] which states that the uniformizing parameter
transformation $r_{p}$ of $p$ satisfies

$(r_{p})^{-1}=\int_{0}^{t}\,\omega_{p}(\gamma)d\gamma/\mu_{p}.$

Let $\varphi$ be a piecewise radical transformation associated to $p$. If
$(r_{p})^{-1}$ and $\varphi^{-1}$ share some common properties, we say
informally that $r_{p}$ and $\varphi$ are similar to each other.

First of all, the following can be derived:

$\varphi^{-1}(t)=\left\\{\begin{array}[c]{ll}s_{i}+\Delta
s_{i}\cdot\tilde{t}^{\mu_{i}+1}{}&\mbox{if~{}}\omega_{p}(t_{i})=0;\\\\[8.0pt]
s_{i}+\Delta
s_{i}\cdot[1-(1-\tilde{t})^{\mu_{i+1}+1}]{}&\mbox{if~{}}\omega_{p}(t_{i+1})=0;\\\\[8.0pt]
s_{i}+\Delta s_{i}\cdot\tilde{t}{}&\mbox{otherwise},\end{array}\right.$ (8)

where $\tilde{t}=(t-t_{i})/\Delta t_{i}$. Furthermore,

$\displaystyle\left[\varphi^{-1}\right]^{\prime}$
$\displaystyle=~{}\left\\{\begin{array}[c]{ll}\dfrac{\Delta s_{i}}{\Delta
t_{i}}\cdot(\mu_{i}+1)\cdot\tilde{t}^{\mu_{i}}{}&\mbox{if~{}}\omega_{p}(t_{i})=0;\\\\[8.0pt]
\dfrac{\Delta s_{i}}{\Delta
t_{i}}\cdot(\mu_{i+1}+1)\cdot(1-\tilde{t})^{\mu_{i+1}}{}&\mbox{if~{}}\omega_{p}(t_{i+1})=0;\\\\[8.0pt]
\dfrac{\Delta s_{i}}{\Delta t_{i}}{}&\mbox{otherwise};\end{array}\right.$
$\displaystyle\left[\varphi^{-1}\right]^{\prime\prime}$
$\displaystyle=~{}\left\\{\begin{array}[c]{ll}\dfrac{\Delta s_{i}}{\Delta
t_{i}^{2}}\cdot(\mu_{i}+1)\mu_{i}\cdot\tilde{t}^{\mu_{i}-1}&\mbox{if~{}}\omega_{p}(t_{i})=0;\\\\[8.0pt]
-\dfrac{\Delta s_{i}}{\Delta
t_{i}^{2}}\cdot(\mu_{i+1}+1)\mu_{i+1}\cdot(1-\tilde{t})^{\mu_{i+1}-1}&\mbox{if~{}}\omega_{p}(t_{i+1})=0;\\\\[8.0pt]
0{}&\mbox{otherwise}.\end{array}\right.$

Note that $\varphi$ has the properties listed below.

  * •

$\varphi^{-1}(0)=0$, $\varphi^{-1}(1)=1$.

  * •

$\varphi_{i}^{-1}$ is monotonic over $(t_{i},t_{i+1})$ because
$(\varphi_{i}^{-1})^{\prime}(t)\geq 0$ for all $t\in(t_{i},t_{i+1})$; since
$\varphi^{-1}$ is continuous over $[0,1]$, $\varphi^{-1}$ is monotonic over
$[0,1]$.

  * •

$[\varphi_{i}^{-1}]^{\prime}$ is monotonic over $(t_{i},t_{i+1})$ because
$[\varphi_{i}^{-1}]^{\prime\prime}$ has a constant sign over
$(t_{i},t_{i+1})$.

The above properties indicate that $\varphi$ is composed of some monotonically
increasing convex or concave pieces. Moreover, it can be verified that

  * •

$r_{p}^{-1}(0)=\int_{0}^{0}\omega_{p}(\gamma)\,d\gamma/\mu_{p}=0$,
$r_{p}^{-1}(1)=\int_{0}^{1}\omega_{p}(\gamma)\,d\gamma/\mu_{p}=1$;

  * •

$r_{p}^{-1}$ is monotonic over $[0,1]$ because
$(r_{p}^{-1})^{\prime}(t)=\omega_{p}(t)/\mu_{p}\geq 0$.

One may observe that $\varphi$ shares the first two properties with $r_{p}$.
If $r_{p}$ possesses the third property of $\varphi$, then $r_{p}$ and
$\varphi$ are expected to be similar. This inspires us to divide $[0,1]$ into
some monotonic intervals of $(r_{p}^{-1})^{\prime}(t)$ (i.e., $\omega_{p}$).
Thus we may try to choose the intermediate $t_{i}$ in $T$ by solving

$\omega_{p}(t_{i})\omega_{p}^{\prime}(t_{i})=0.$

Note that $\omega_{p}(t)$ is nonnegative. Thus $0$ is the local minimum value
of $\omega_{p}$. In this sense, $T$ consists of all the local extreme points
of $\omega_{p}$ and the two boundary points of the unit interval.

With the above operation, $r_{p}$ is divided into some monotonically
increasing/decreasing convex or concave pieces with each piece having a
corresponding one in $\varphi$. Therefore, $T$ can be obtained by collecting
and inserting the zeros of $\omega_{p}$ and $\omega_{p}^{\prime}$ into $[0,1]$
in order.

######  Example 3.11 (Continued from Example 3.9).

One may compute that

$\omega_{p}^{\prime}(t)=-\dfrac{6\,(27\,t^{4}-1)}{(9\,t^{4}+1)^{2}}.$

Then the solution of $\omega_{p}(t)\omega_{p}^{\prime}(t)=0$ over $[0,1]$
gives us a partition of $[0,1]$, i.e.,

$T\doteq(0,0.439,1).$

Furthermore, one may check that the multiplicities of $t_{0},t_{1},t_{2}$ as
roots of $\omega_{p}$ are $1,0$ and $0$, respectively.

###  3.3 Determination of $S$

Once a partition $T$ of $[0,1]$ is obtained, one can compute the sequence $S$
in various ways. In this subsection, we present an optimization strategy for
the computation of $S$.

When $T$ is fixed, $u_{p\circ\varphi}$ becomes a function of
$s_{i}~{}(i=1,\ldots,N-1)$. The following theorem provides a formula for
computing the optimal values for $s_{i}$’s.

######  Theorem 3.12.

The uniformity $u_{p\circ\varphi}$ reaches the maximum when

$s_{i}=s_{i}^{*}=\dfrac{\sum_{k=0}^{i-1}\sqrt{L_{k}}}{\sum_{k=0}^{N-1}\sqrt{L_{k}}},$
(9)

where

$L_{k}=\left\\{\begin{array}[c]{ll}{\Delta
t_{k}}\int_{t_{k}}^{t_{k+1}}\dfrac{\omega_{p}^{2}(t)}{(\mu_{k}+1)\tilde{t}^{\mu_{k}}}\,dt&\mbox{if}\quad\omega_{p}(t_{k})=0;\\\\[10.0pt]
{\Delta
t_{k}}\int_{t_{k}}^{t_{k+1}}\dfrac{\omega_{p}^{2}(t)}{(\mu_{k+1}+1)(1-\tilde{t})^{\mu_{k+1}}}\,dt&\mbox{if}\quad\omega_{p}(t_{k+1})=0;\\\\[10.0pt]
\Delta
t_{k}\int_{t_{k}}^{t_{k+1}}\omega_{p}^{2}(t)\,dt&\mbox{otherwise.}\end{array}\right.$
(10)

The maximum value of $u_{p\circ\varphi}$ is

$u_{p\circ\varphi}^{*}=\mu_{p}^{2}\big{/}\eta_{p,\varphi}^{*},\quad\mbox{where}\quad\eta_{p,\varphi}^{*}=\left(\sum_{i=0}^{N-1}\sqrt{L_{i}}\right)^{2}.$

######  Proof 3.13.

Recall (5). Since $\mu_{p}$ is a constant for any given $p$, the problem of
maximizing $u_{p\circ\varphi}$ can be reduced to that of minimizing

$\eta_{p,\varphi}=\int_{0}^{1}\dfrac{\omega_{p}^{2}}{(\varphi^{-1})^{\prime}}(t)\,dt=\sum_{i=0}^{N-1}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}}{(\varphi_{i}^{-1})^{\prime}}(t)\,dt.$

We first simplify each component in the above equation. Denote
$\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}}{(\varphi_{i}^{-1})^{\prime}}(t)\,dt$
by $I_{i}$. Note that

$\dfrac{1}{(\varphi_{i}^{-1})^{\prime}(t)}=\left\\{\begin{array}[]{ll}\dfrac{\Delta
t_{i}}{\Delta
s_{i}}\cdot\dfrac{1}{\mu_{i}+1}\cdot\dfrac{1}{\tilde{t}^{\mu_{i}}}&\mbox{if}\quad\omega_{p}(t_{i})=0;\\\
\dfrac{\Delta t_{i}}{\Delta
s_{i}}\cdot\dfrac{1}{\mu_{i+1}+1}\cdot\dfrac{1}{(1-\tilde{t})^{\mu_{i+1}}}&\mbox{if}\quad\omega_{p}(t_{i+1})=0;\\\
\dfrac{\Delta t_{i}}{\Delta s_{i}}&\mbox{otherwise}.\end{array}\right.$

When $\omega_{p}(t_{i})=0$,

$I_{i}=\dfrac{\Delta t_{i}}{\Delta
s_{i}}\cdot\dfrac{1}{\mu_{i}+1}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}}{\tilde{t}^{\mu_{i}}}\,dt=L_{i}/\Delta
s_{i}.$

Similarly, when $\omega_{p}(t_{i+1})=0$,

$I_{i}=\dfrac{\Delta t_{i}}{\Delta
s_{i}}\cdot\dfrac{1}{\mu_{i+1}+1}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}}{(1-\tilde{t})^{\mu_{i+1}}}\,dt=L_{i}/\Delta
s_{i}.$

When $\omega_{p}(t_{i})\cdot\omega_{p}(t_{i+1})\neq 0$,

$I_{i}=\dfrac{\Delta t_{i}}{\Delta
s_{i}}\cdot\int_{{}_{i}}^{t_{i+1}}\omega_{p}^{2}\,dt={L_{i}}/{\Delta s_{i}}.$

It is obvious that $\eta_{p,\varphi}=\sum_{i=0}^{N-1}I_{i}>0$; it increases to
$+\infty$ when $s_{i}$ approaches the boundary of the feasible set of
parameters. Now we compute the extrema of $\eta_{p,\varphi}$. Let

$\dfrac{\partial\eta_{p,\varphi}}{\partial s_{i}}=0,$

i.e.,

$\dfrac{L_{i}}{\Delta s_{i}^{2}}-\dfrac{L_{i-1}}{\Delta s_{i-1}^{2}}=0,$

where $L_{i}$ is as in (10). Solving the above equation, we obtain

$\Delta s_{i}=\Delta s_{i}^{*}=\Delta s_{0}^{*}\sqrt{L_{i}/L_{0}}.$

Note that $\sum_{i=0}^{N-1}\Delta s_{i}^{*}=1$. Thus

$\Delta s_{0}^{*}=\left(\sum_{k=0}^{N-1}\sqrt{L_{k}/L_{0}}\right)^{-1},\quad
s_{i}^{*}=\sum_{k=0}^{i-1}{\Delta
s_{k}^{*}}=\dfrac{\sum_{k=0}^{i-1}\sqrt{L_{k}/L_{0}}}{\sum_{k=0}^{N-1}\sqrt{L_{k}/L_{0}}}=\dfrac{\sum_{k=0}^{i-1}\sqrt{L_{k}}}{\sum_{k=0}^{N-1}\sqrt{L_{k}}}.$

Therefore,

$\Delta s_{i}^{*}=\dfrac{\sqrt{L_{i}}}{\sum_{k=0}^{N-1}\sqrt{L_{k}}}.$

Moreover, the optimal value of $\eta_{p,\varphi}$ is

$\eta_{p,\varphi}=\eta_{p,\varphi}^{*}=\sum_{i=0}^{N-1}\dfrac{L_{i}}{\Delta
s_{i}^{*}}=\sum_{k=0}^{N-1}\dfrac{L_{i}}{\dfrac{\sqrt{L_{i}}}{\sum_{i=0}^{N-1}\sqrt{L_{k}}}}=\left(\sum_{k=0}^{N-1}\sqrt{L_{k}}\right)^{2},$

from which it follows that the optimal value of $u_{p\circ\varphi}$ is

$u_{p\circ\varphi}=u_{p\circ\varphi}^{*}=\dfrac{\mu_{p}^{2}}{\eta_{p,\varphi}^{*}}=\dfrac{\mu_{p}^{2}}{\left(\sum_{k=0}^{N-1}\sqrt{L_{k}}\right)^{2}}.$

The proof is completed.

######  Example 3.14 (Continued from Example 3.11).

By using (10), we compute the values of $L_{0}$ and $L_{1}$ and obtain

$\displaystyle L_{0}$ $\displaystyle\doteq
0.439\int_{0}^{0.439}\dfrac{\left(\dfrac{6\,t}{9\,t^{4}+1}\right)^{2}}{2\cdot\dfrac{t-0}{0.439}}\,dt\doteq
0.276,$ $\displaystyle L_{1}$
$\displaystyle\doteq(1-0.439)\int_{0.439}^{1}\left(\frac{6\,t}{9\,t^{4}+1}\right)^{2}\,dt\doteq
0.590.$

By (9), we have $s_{1}=0.406$. Thus $S\doteq(0,0.406,1)$. Furthermore, one may
calculate the optimal value of $u_{p\circ\varphi}$ and obtain
$u_{p\circ\varphi}^{*}\doteq 0.932$.

###  3.4 Determination of $Z$ and $\alpha$

Once a partition $S$ of $[0,1]$ is obtained, one can compute the sequence $Z$.
In this subsection, we give explicit formulae for the optimal values of $Z$
and $\alpha$ which are directly computed from the sequence $T$. For this
purpose, we first recall the the following result from [12].

######  Theorem 3.15.

Let $q$ be a rational parameterization such that $\omega_{q}(s)\neq 0$ over
$[0,1]$ and $m$ be a piecewise Möbius transformation determined by $S$, $Z$
and $\alpha$. For a given sequence $S$, the uniformity $u_{q\circ m}$ reaches
the maximum when

$\alpha_{i}=\alpha_{i}^{*}=\dfrac{1}{1+\sqrt{C_{i}/A_{i}}},\quad
z_{i}=z_{i}^{*}=\dfrac{\sum_{k=0}^{i-1}\sqrt{M_{k}}}{\sum_{k=0}^{N-1}\sqrt{M_{k}}},$
(11)

where

$\displaystyle A_{i}$
$\displaystyle=\int_{s_{i}}^{s_{i+1}}\omega_{q}^{2}\cdot(1-\tilde{s})^{2}ds,$
$\displaystyle B_{i}$ $\displaystyle=\int_{s_{i}}^{s_{i+1}}\omega_{q}^{2}\cdot
2\tilde{s}(1-\tilde{s})ds,$ $\displaystyle C_{i}$
$\displaystyle=\int_{s_{i}}^{s_{i+1}}\omega_{q}^{2}\cdot\tilde{s}^{2}ds,$
$\displaystyle M_{k}$ $\displaystyle=\Delta
s_{k}\left(2\sqrt{A_{k}C_{k}}+B_{k}\right).$

Let $m^{*}$ be the piecewise Möbius transformation determined by $S$, $Z^{*}$
and $\alpha^{*}$. Then the maximum value of $u_{q\circ m}$ is $u_{q\circ
m^{*}}=\mu_{q}^{2}/\eta_{q,m^{*}}$ where

$\eta_{q,m^{*}}=\left(\sum_{i=0}^{N-1}\sqrt{M_{k}}\right)^{2}.$

######  Remark 3.16.

Let $\varphi$ be an elementary radical transformation as in Definition 3 and
$q=p\circ\varphi$. Note that

$\mu_{q}=\int_{0}^{1}\omega_{q}ds=\int_{0}^{1}\omega_{p\circ\varphi}ds=\int_{0}^{1}(\omega_{p}\circ\varphi)(s)\cdot\varphi^{\prime}(s)ds=\int_{0}^{1}\omega_{p}dt=\mu_{p}.$

Thus

$u_{p\circ\varphi\circ m^{*}}=u_{q\circ
m^{*}}=\mu_{q}^{2}/\eta_{q,m^{*}}=\mu_{p}^{2}\bigg{/}\left(\sum_{i=0}^{N-1}\sqrt{M_{k}}\right)^{2}.$

Let $\varphi$ and $q$ be defined as before. By Theorem 7, $\omega_{q}\neq 0$
over $[0,1]$. One may compute the optimal values of $S$, $\alpha$ and $Z$ by
Theorems 3.12 and 3.15. However, $p\circ\varphi$ is a composition of radical
function and rational function and the composition will cause an increase of
complexity because $\omega_{q}$ is radical. In what follows, we simplify the
formulae for $A_{i},B_{i}$ and $C_{i}$ with the goal of computing the values
of $A_{i},B_{i}$ and $C_{i}$ directly from $p$.

The formula of $A_{i}~{}(0\leq i\leq N-1)$ is derived via the following steps:

$\displaystyle A_{i}$
$\displaystyle=\int_{s_{i}}^{s_{i+1}}\omega_{q}^{2}\cdot(1-\tilde{s})^{2}ds$
$\displaystyle=\int_{s_{i}}^{s_{i+1}}[(\omega_{p}\circ\varphi)(s)]^{2}\cdot[\varphi^{\prime}(s)]^{2}\cdot(1-\tilde{s})^{2}ds$
$\displaystyle=\int_{s_{i}}^{s_{i+1}}[(\omega_{p}\circ\varphi)(s)]^{2}\cdot[\varphi^{\prime}(s)]\cdot(1-\tilde{s})^{2}\left[\varphi^{\prime}(s)ds\right]$
$\displaystyle=\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}}{\left(\varphi^{-1}\right)^{\prime}}(t)\cdot\left(1-\dfrac{\varphi^{-1}-s_{i}}{\Delta
s_{i}}\right)^{2}dt\qquad\qquad\qquad\qquad\quad\text{by~{}\eqref{eqs:inversephi}}$
$\displaystyle=\left\\{\begin{array}[]{ll}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}}{\left(\varphi^{-1}\right)^{\prime}}(t)\cdot(1-\tilde{t}^{\mu_{i}+1})^{2}dt&\text{if~{}}\omega(t_{i})=0;\\\
\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}}{\left(\varphi^{-1}\right)^{\prime}}(t)\cdot(1-\tilde{t})^{2(\mu_{i+1}+1)}dt&\text{if~{}}\omega(t_{i+1})=0;\\\
\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}}{\left(\varphi^{-1}\right)^{\prime}}(t)\cdot(1-\tilde{t})^{2}dt&\text{otherwise};\end{array}\right.$
$\displaystyle=\left\\{\begin{array}[c]{lll}\dfrac{\Delta t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}(t)}{(\mu_{i}+1)\tilde{t}^{\mu_{i}}}\cdot(1-\tilde{t}^{\mu_{i}+1})^{2}dt&&\hskip
70.0001pt\text{if~{}}\omega(t_{i})=0;\\\\[10.0pt] \dfrac{\Delta t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}(t)}{\mu_{i+1}+1}\cdot(1-\tilde{t})^{\mu_{i+1}+2}dt&&\hskip
70.0001pt\text{if~{}}\omega(t_{i+1})=0;\\\\[10.0pt] \dfrac{\Delta
t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}{\omega_{p}^{2}}(t)\cdot(1-\tilde{t})^{2}dt&&\hskip
70.0001pt\text{otherwise.}\end{array}\right.$

Similarly, we have

$\displaystyle B_{i}$ $\displaystyle=\left\\{\begin{array}[c]{ll}\dfrac{\Delta
t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}(t)}{\mu_{i}+1}\cdot
2\tilde{t}(1-\tilde{t}^{\mu_{i}+1})dt&\hskip
23.00006pt\text{if~{}}\omega(t_{i})=0;\\\\[10.0pt] \dfrac{\Delta t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}(t)}{\mu_{i+1}+1}\cdot
2[1-(1-\tilde{t})^{\mu_{i+1}+1}](1-\tilde{t})dt&\hskip
23.00006pt\text{if~{}}\omega(t_{i+1})=0;\\\\[10.0pt] \dfrac{\Delta
t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}{\omega_{p}^{2}}(t)\cdot(1-\tilde{t})^{2}dt&\hskip
23.00006pt\text{otherwise;}\end{array}\right.$ $\displaystyle C_{i}$
$\displaystyle=\left\\{\begin{array}[c]{ll}\dfrac{\Delta t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}(t)}{\mu_{i}+1}\cdot\tilde{t}^{\mu_{i}+2}dt&\text{if~{}}\omega(t_{i})=0;\\\\[10.0pt]
\dfrac{\Delta t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}(t)}{(\mu_{i+1}+1)(1-\tilde{t})^{\mu_{i+1}}}\cdot[1-(1-\tilde{t})^{\mu_{i+1}+1}]^{2}dt&\text{if~{}}\omega(t_{i+1})=0;\\\\[10.0pt]
\dfrac{\Delta t_{i}}{\Delta
s_{i}}\int_{t_{i}}^{t_{i+1}}{\omega_{p}^{2}}(t)\cdot(1-\tilde{t})^{2}dt&\text{otherwise.}\end{array}\right.$

######  Example 3.17 (Continued from Example 3.14).

With the above formulae and $T$, $S$ as in Examples 3.11 and 3.14, one may
obtain the following:

$\begin{array}[]{lllll}A_{0}\doteq 0.258,&&B_{0}\doteq 0.229,&&C_{0}\doteq
0.193,\\\ A_{1}\doteq 0.518,&&B_{1}\doteq 0.317,&&C_{1}\doteq
0.159.\end{array}$

Thus

$\displaystyle M_{0}$ $\displaystyle\doteq 0.406(2\sqrt{0.258\cdot
0.193}+0.229)\doteq 0.274,$ $\displaystyle M_{1}$
$\displaystyle\doteq(1-0.406)(2\sqrt{0.518\cdot 0.159}+0.317)\doteq 0.529.$

By Theorem 3.15, we obtain

$\displaystyle\alpha_{0}$ $\displaystyle\doteq 1/(1+\sqrt{0.193/0.258})\doteq
0.536,$ $\displaystyle\alpha_{1}$ $\displaystyle\doteq
1/(1+\sqrt{0.159/0.518})\doteq 0.643,$

and $z_{1}^{*}\doteq 0.419$. Thus $\alpha\doteq(0.536,0.643)$ and
$Z\doteq(0,.419,1)$. One may further calculate

$u_{q\circ
m^{*}}\doteq\dfrac{1.249^{2}}{(\sqrt{0.274}+\sqrt{0.529})^{2}}\doteq 0.997.$

##  4 Algorithm

In this section, we summarize the above ideas and results as Algorithm 1 and
illustrate how the algorithm works for the cubic curve in Example 2.

  * Input:

$p$, a rational parameterization of a plane curve.

  * Output:

$r$, the optimal piecewise radical transformation of $p$ such that $u_{p\circ
r}>u_{p}$.

  * 1\.

Compute $\omega_{p}$ and $\mu_{p}$ using (2), $u_{p}$ using (3) and
$\omega_{p}^{\prime}$.

  * 2\.

Solve $\omega_{p}\omega_{p}^{\prime}=0$ and get $T$.

  * 3\.

Compute $S$, $Z$, $\alpha$ and $u$ using (9) and (11).

  * 4\.

Construct $\varphi$ with $T$, $S$ and $m$ with $S$, $Z$, $\alpha$ using (6)
and (7).

  * 5\.

$r\leftarrow\varphi\circ m$.

  * 6\.

Return $r$.

Algorithm 1 Optimal_Radical_Transformation

######  Example 4.18 (Continued from Example 3.17).

Given $p=(t,t^{3})$, after the above calculation, one may obtain

$T\doteq(0,0.439,1),\ \ S\doteq(0,0.406,1),\ \ Z\doteq(0,.419,1),\ \
\alpha\doteq(0.536,0.643).$

Then one may construct $\varphi$ with $T$ and $S$, and $m$ with $S$, $Z$ and
$\alpha$, and obtain

$\displaystyle\varphi\doteq$
$\displaystyle\begin{cases}0.688\sqrt{s}&\text{if}\quad 0.000\leq s\leq
0.406;\\\ 0.055+0.945s&\text{if}\quad 0.406\leq s\leq 1.000;\end{cases}$
$\displaystyle m\doteq$
$\displaystyle\begin{cases}\dfrac{-0.450z}{0.172z-0.536}&\text{if}\quad
0.000\leq z\leq 0.049;\\\\[8.0pt]
-\dfrac{0.165z+0.192z}{0.492z-0.849}&\text{if}\quad 0.419\leq z\leq
1.000.\end{cases}$

Then the optimal transformation $r$ is constructed below.

$r=\varphi\circ
m\doteq\begin{cases}0.462\,\sqrt{-{\dfrac{z}{0.172z-0.536}}}&\text{if}\quad
0.000\leq z\leq 0.419;\\\\[10.0pt]
\dfrac{-0.129z-0.228}{0.492z-0.849}&\text{if}\quad 0.419\leq z\leq
1.000.\end{cases}$

With the optimal radical transformation $r$, one may construct $p\circ r$ and
obtain

$p\circ
r\doteq\begin{cases}\left({\dfrac{-0.079\,\sqrt{z}\left(z-3.116\right)}{\left(-0.172\,z+0.5359\right)^{3/2}}},{\dfrac{0.098\,{z}^{3/2}}{\left(-0.172\,z+0.536\right)^{3/2}}}\right)&\text{if}\quad
0.000\leq z\leq 0.419;\\\\[10.0pt]
\left({\dfrac{-0.129\,z-0.228}{0.492\,z-0.849}},-{\dfrac{0.002\,\left(z+1.771\right)^{3}}{\left(0.492\,z-0.849\right)^{3}}}\right)&\text{if}\quad
0.419\leq z\leq 1.000.\end{cases}$

The angular speed function of $p\circ r$ is

$w_{p\circ
r}\doteq\begin{cases}\dfrac{0.781}{{z}^{2}-0.420\,z+0.655}&\text{if}\quad
0.000\leq z\leq 0.4187;\\\\[10.0pt]
{\dfrac{-1.379\,\left(z+1.771\right)\left(z-1.725\right)}{\left({z}^{2}-1.456\,z+0.899\right)\left({z}^{2}-4.876\,z+9.888\right)}}&\text{if}\quad
0.4187\leq z\leq 1.000.\end{cases}$

Furthermore, one may calculate its uniformity $u_{p\circ r}\doteq 0.997$.

The plots of $p$ and $p\circ r$ as well as the behavior of their angular speed
functions are shown below:

where

  * •

the left plot shows the equi-sampling of the original parameterization $p$
(green);

  * •

the middle plot shows the equi-sampling of the optimal piecewise radical
reparameterization $p\circ r$ (red);

  * •

the right plot shows the angular speed functions of $p$ and $p\circ r$.

It is seen that the angular speed uniformity is greatly improved by the
piecewise radical reparameterization.

##  5 Implementational Issues/Suggestions

If one chooses to implement the proposed algorithm using floating-point
arithmetic, then, as usual, one should be careful to avoid numerical
instability.

For instance, if $L_{i}$ is computed by (10) naively, then it leads to
instability. For example, $t_{i}=1/\sqrt{2}$ is a zero of $\omega_{p}$ with
multiplicity $1$, so

$\omega_{p}(t)=|t-1/\sqrt{2}|\cdot{m}(t),$

where ${m}(1/\sqrt{2})\neq 0$. The numeric solution over $[0,1]$ is
$t_{i}=0.707$. Thus

$L_{i}\,=\,{\Delta
t_{i}}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}(t)}{(\mu_{i}+1)\tilde{t}^{\mu_{i}}}\,dt=\,\Delta
t_{i}^{2}\int_{t_{i}}^{t_{i+1}}\dfrac{(t-1/\sqrt{2})^{2}\cdot{m}^{2}(t)}{2\,(t-0.707)}\,dt.$

During integration, it is necessary to evaluate the integral at $t=0.707$.
When $t$ approaches $0.707$, the integral quickly increases to $+\infty$,
causing numerical instability.

To avoid such cases, one could adopt a technique from symbolic computation to
represent algebraic numbers. Suppose that $t=\gamma$ is a zero of
$\omega_{p}(t)$ with multiplicity $\mu_{i}$ and $t_{i}$ is its numerical
approximation. By (2), $\omega_{p}^{2}(t)$ is a rational function. Let $G$ and
$H$ be its numerator and denominator. Then $t=\gamma$ is a zero of $G$ with
multiplicity $2\,\mu_{i}$. Carrying out the Euclidean division with $G$ as the
dividend and $(t-\gamma)^{2\,\mu_{i}}$ as the divisor, we obtain

$G(t)=(t-\gamma)^{2\,\mu_{i}}Q(t,\gamma)+R(t,\gamma).$

Since $t=\gamma$ is a zero of $G$ with multiplicity $2\,\mu_{i}$, it is also a
zero of $R(t,\gamma)$ with multiplicity at least $2\,\mu_{i}$. Given that
$\deg(R,t)<2\,\mu_{i}$, $R(t,\gamma)$ must be zero, which leads to the
following conclusion:

$L_{i}\,=\,{\Delta
t_{i}}\int_{t_{i}}^{t_{i+1}}\dfrac{\omega_{p}^{2}(t)}{(\mu_{i}+1)\,\tilde{t}^{\mu_{i}}}\,dt\doteq\,\dfrac{\Delta
t_{i}^{\mu_{i}+1}}{\mu_{i}+1}\cdot\int_{t_{i}}^{t_{i+1}}\dfrac{Q(t,t_{i})(t-t_{i})^{\mu_{i}}}{H(t)}\,dt.$

#### Acknowledgements

Hoon Hong’s work was supported by National Science Foundations of USA under
Grant No. 1813340 and Jing Yang’s work was supported by National Natural
Science Foundation of China under Grant Nos. 11526060 and 12261010.

## References

  * [1]
  * [2] P. Costantini, R. T. Farouki, C. Manni & Sestini A (2001): _Computation of optimal composite re-parameterizations_.  Computer Aided Geometric Design 18(9), pp. 875–897, 10.1016/S0167-8396(01)00071-1.
  * [3] G. Farin (2006): _Rational quadratic circles are parametrized by chord length_.  Computer Aided Geometric Design 23(9), pp. 722–724, 10.1016/j.cagd.2006.08.002.
  * [4] R. T. Farouki (1997): _Optimal parameterizations_.  Computer Aided Geometric Design 14(2), pp. 153–168, 10.1016/S0167-8396(96)00026-X.
  * [5] H. Hong, D. Wang & J. Yang (2013): _A framework for improving uniformity of parameterizations of curves_.  Science China Information Sciences 56(10), pp. 1–22, 10.1007/s11432-013-4924-4.
  * [6] B. Jüttler (1997): _A vegetarian approach to optimal parameterizations_.  Computer Aided Geometric Design 14(9), pp. 887–890, 10.1016/S0167-8396(97)00044-7.
  * [7] M. Kosters (1991): _Curvature-dependent parameterization of curves and surfaces_.  Computer-Aided Design 23(8), pp. 569–578, 10.1016/0010-4485(91)90058-5.
  * [8] X. Liang, C. Zhang, L. Zhong & Y. Liu (2005): _$C^{1}$ continuous rational re-parameterization using monotonic parametric speed partition_.  In: Ninth International Conference on Computer Aided Design and Computer Graphics, IEEE Computer Society, Los Alamitos, CA, USA, pp. 16–21, 10.1109/CAD-CG.2005.23.
  * [9] R. Patterson & C. Bajaj (1989): _Curvature adjusted parameterization of curves_.  Technical Report CSD-TR-907, Department of Computer Science, Purdue University, US.  Available at https://docs.lib.purdue.edu/cstech/773/.
  * [10] J. R. Sendra & C. Villarino (2001): _Optimal reparameterization of polynomial algebraic curves_.  International Journal of Computational Geometry & Applications 11(04), pp. 439–453, 10.1142/S0218195901000572.
  * [11] J. R. Sendra, F. Winkler & S. Pérez-Díaz (2008): _Rational algebraic curves. A computer algebra approach_.  Algorithms and Computation in Mathematics 22, Springer Verlag, 10.1007/978-3-540-73725-4.
  * [12] J. Yang, D. Wang & H. Hong (2012): _Improving angular speed uniformity by optimal $C^{0}$ piecewise reparameterization_.  In V. P. Gerdt, W. Koepf, E. W. Mayr & E. V. Vorozhtsov, editors: Computer Algebra in Scientific Computing, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 349–360, 10.1007/978-3-642-32973-9_29.
  * [13] J. Yang, D. Wang & H. Hong (2013): _Improving angular speed uniformity by $C^{1}$ piecewise reparameterization_.  In T. Ida & J. Fleuriot, editors: Automated Deduction in Geometry, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 33–47, 10.1007/978-3-642-40672-0_3.
  * [14] J. Yang, D. Wang & H. Hong (2013): _Improving angular speed uniformity by reparameterization_.  Computer Aided Geometric Design 30(7), pp. 636–652, 10.1016/j.cagd.2013.04.001.
  * [15] J. Yang, D. Wang & H. Hong (2014): _ImUp: a Maple package for uniformity-improved reparameterization of plane curves_.  In R. Feng, W. Lee & Y. Sato, editors: Computer Mathematics, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 437–451, 10.1007/978-3-662-43799-5_29.