Nesting the Radii
Lemma 1.
The interval that contains the squares of abscissae of (all and only) the grid points
constituting the $k(\geq0)$th run in Octant 1 of $\dcir(o,r)$ is
$I_k:=[u_k,v_k]=[\max\{0,(2k-1)r-k(k-1)\},(2k+1)r-k(k+1)-1]$.
Proof.
Follows from an earlier work by
Bhowmick & Bhattacharya (2008).
Lemma 2.
$\lambda_0$ is the length of top run of $\dcir(o,r)$
if and only if $r$ lies in the interval
$R_0=\left[(\lambda_0-1)^2+1,\lambda_0^2\right]$.
Proof. Using Lemma 1.
Lemma 3.
$\lambda_0$ and $\lambda_1$ are the lengths of top two runs of a digital circle $\dcir(o,r)$
if and only if $r\in R_0\cap R_1$,
where,
$R_1=\left[\left\lceil\dfrac{(\Lambda_1-1)^2+3}{3}\right\rceil,
\left\lfloor\dfrac{\Lambda_1^2+2}{3}\right\rfloor\right]$ and $\Lambda_1=\lambda_0+\lambda_1$.
In particular, if $R_0\cap R_1=\emptyset$, then there exists no digital circle whose top two runs
have length $\lambda_0$ and $\lambda_1$.
Proof. Using Lemma 1 and Lemma 2.
To decide whether there exits a valid range of radii corresponding to a given
sequence of run-lengths, we obtain the following theorems using Lemmas 1—3.
Theorem 1 (Radii interval).
$\langle \lambda_0,\lambda_1,\ldots,\lambda_{n}\rangle$ is the sequence of top $n+1$ run-lengths
of $\dcir(o,r)$ if and only if
\[r\in \bigcap\limits_{k=0}^{n} R_k\]
where,
\[R_{k}=\left[\left\lceil\dfrac{1}{2k+1}\left(\left(\Lambda_k-1\right)^2+k(k+1)+1\right)\right\rceil,
\left\lfloor\dfrac{1}{2k+1}\left(\Lambda_k^2+k(k+1)\right)\right\rfloor\right]\]
and
\[\Lambda_k=\sum\limits_{j=0}^{k}\lambda_j.\]
In particular, if $\bigcap\limits_{k=0}^{n} R_k=\emptyset$, then there exists no digital circle
whose top $n+1$ runs have length $\langle \lambda_0,\lambda_1,\ldots,\lambda_{n}\rangle$.
The decision algorithm DCT that verifies whether a sequence $S$ corresponds to
top $n$ runs of a digital circle, is as follows.
|
$\mbox{Algorithm DCT(int } S[0\,.\,.\,n-1])$
|
|
\(
\newcommand {\T} {\ \ \ \ \ }
\begin{array}{@{}l@{}l}
1.& \Lambda\leftarrow S[0]\\
2.& [r',r'']\leftarrow[(\Lambda-1)^2+1,\Lambda^2]\\
3.& \bold{for } k\leftarrow1,2,\ldots,n-1\\
4.&\T \Lambda\leftarrow \Lambda+S[k]\\
5.&\T s'\leftarrow \left\lceil((\Lambda-1)^2+k(k+1)+1)/(2k+1)\right\rceil\\
6.&\T s''\leftarrow \left\lfloor(\Lambda^2+k(k+1))/(2k+1)\right\rfloor\\
7.&\T \bold{if } (s'' < r') \vee (s' > r'')\\
8.&\T\T \bold{print}\ \mbox{$S$ is circular up to $(k-1)$th run for $[r',r'']$.}\\
9.&\T\T \bold{return}\\
10.&\T \bold{else}\\
11.&\T\T [r',r'']\leftarrow[\max(r',s'),\min(r'',s'')]\\
12.& \bold{print}\ \mbox{$S$ is circular in entirety for $[r',r'']$.}
\end{array}
\)
|
General Case
Deals with properties of digital circularity for an arbitrary
run or a sequence of runs that does not start from the topmost run ($k = 0$).
Lemma 4.
If a digital circle of radius $r$ contains a given run of length $\lambda$,
then there exist two positive integers $a$ and $k$ such that
$r\geq\left\lceil\max\left(\fnt_{1,\lambda}(a,k),\fnt_{2,\lambda}(a,k)\right)\right\rceil$,
where
\[
\fnt_{1,\lambda}(a,k)=\dfrac{(a-1)^2+k(k-1)+1}{2k-1} \ \mbox{ and } \
\fnt_{2,\lambda}(a,k)=\dfrac{(a+\lambda-1)^2+k(k+1)+1}{2k+1}.
\]
Lemma 5.
If a digital circle of radius $r$ contains a given run of length $\lambda$,
then there exist two positive integers $a$ and $k$ such that
$r\leq\left\lfloor\min\left({\fnt_{3,\lambda}}(a,k),{\fnt_{4,\lambda}}(a,k)\right)\right\rfloor$,
where
\[
\fnt_{3,\lambda}(a,k)=\dfrac{a^2+k(k-1)}{2k-1} \ \mbox{ and } \
\fnt_{4,\lambda}(a,k)=\dfrac{(a+\lambda)^2+k(k+1)}{2k+1}.
\]
Proofs of Lemmas 4 and 5 are based on previous lemmas and
location of perfect squares in integer intervals.
And from these two lemmas, the following theorem:
Theorem 2 (Run to Radius).
An arbitrary run of given length $\lambda$ belongs to a digital circle if and only if its radius lies
in the range
\[{\mathcal R}_{ak}=
\left\{r: r\geq\left\lceil\max\limits_{a,k\inZp}
\left({\fnt_{1,\lambda}}(a,k),{\fnt_{2,\lambda}}(a,k)\right)\right\rceil\right\}
\bigcap
\left\{r: r\leq\left\lfloor\min\limits_{a,k\inZp}\left({\fnt_{3,\lambda}}(a,k),
{\fnt_{4,\lambda}}(a,k)\right)\right\rfloor\right\}.\]
Table. Points of intersection (in $\rr$) among the parabolas $\{{\fnt_{i,\lambda}}: i=1,2,3,4\}$
defining ${\mathcal R}_{ak}$.
$
\begin{array}{c|c|l}\hline
\mbox{Parabolas} & \mbox{Point} & \mbox{Abscissa of the point}\\\hline
{\fnt_{1,\lambda}}, {\fnt_{2,\lambda}}& \alpha_{12}& \dfrac12\left(\bot{k}\lambda + \sqrt{(\bot{k}\lambda+2)^2+2(\bot{k}\bot{\lambda}^2+2\hat{\bot{k}}-3)} +2 \right)\\\hline
{\fnt_{2,\lambda}}, {\fnt_{3,\lambda}}& \alpha_{23}& \dfrac12\left(\bot{k}\bot{\lambda} + \sqrt{(\bot{k}\bot{\lambda})^2+2(\bot{k}\bot{\lambda}^2+2\hat{\top{k}}-1)}\right)\\\hline
{\fnt_{3,\lambda}}, {\fnt_{4,\lambda}}& \alpha_{34}& \dfrac12\left(\bot{k}\lambda + \sqrt{(\bot{k}\lambda)^2+2(\bot{k}\lambda^2+2k^2)}\right)\\\hline
{\fnt_{4,\lambda}}, {\fnt_{1,\lambda}}& \alpha_{41}& \dfrac12\left(\bot{k}\lambda+\top{k}+ \sqrt{(\bot{k}\lambda+\top{k})^2+2(\bot{k}\lambda^2+2\hat{\bot{k}}-\top{k}-1)}\right)\\\hline
\end{array}
$
Note: $\bot{k}=2k-1, \top{k}=2k+1, \hat{\bot{k}}=k(k-1), \hat{\top{k}}=k(k+1), \bot{\lambda}=\lambda-1$
Table. Specifications of the parabolas $\{{\fnt_{i,\lambda}}: i=1,2,3,4\}$.
$
\begin{array}{c|l|l|c|c|c}\hline
& & & \mbox{Length of } & & \\
\mbox{Parabola} & \mbox{Axis} & \mbox{Directrix} & \mbox{Latus Rectum} & \mbox{Vertex} & \mbox{Focus}\\\hline
{\fnt_{1,\lambda}} & x=1 & \bot{k}\,y=3/4 & \bot{k} & \left(1, (\hat{\bot{k}}+1)/\bot{k} \right) & \left(1, (8\hat{\top{k}}+5)/(4\bot{k}) \right)\\\hline
{\fnt_{2,\lambda}} & x=-\bot{\lambda} & \top{k}\,y=3/4 & \top{k} & \left(-\bot{\lambda}, (\hat{\top{k}}+1)/\top{k} \right) & \left(-\bot{\lambda}, (8\hat{\bot{k}}+5)/(4\top{k}) \right)\\\hline
{\fnt_{3,\lambda}} & x=0 & \bot{k}\,y=-1/4 & \bot{k} & \left(0, (\hat{\bot{k}})/\bot{k} \right) & \left(0, (8\hat{\top{k}}+1)/(4\bot{k}) \right)\\\hline
{\fnt_{4,\lambda}} & x=-\lambda & \top{k}\,y=-1/4 & \top{k} & \left(-\lambda, \hat{\top{k}}/\top{k} \right) & \left(-\lambda, (8\hat{\bot{k}}+1)/(4\top{k}) \right)\\\hline
\end{array}
$
From Theorem 2, we get the following generalized algorithm to determine digital circularity.
|
$\mbox{Algorithm DCG(int } S[0\,.\,.\,n-1])$
|
|
\(
\begin{array}{@{}l@{}l}
1.& n_{\max}\leftarrow 0\\
2.& \bold{for } k'\leftarrow k_{\min} \mbox{ to } k_{\max}\\
3.&\T \Lambda\leftarrow S[0], i\leftarrow 0\\
4.&\T \mbox{Find-Params}(A,\Lambda,k')\\
5.&\T \bold{while } (i < m) \wedge (n_{\max} < n)
\triangleright \mbox{ for all $a$'s of first run}\\
6.&\T\T [s',s'']\leftarrow[r',r'']\leftarrow [A[i][1],A[i][2]]\\
7.&\T\T \Lambda\leftarrow A[i][0]+S[0], j\leftarrow 1\\
8.&\T\T \bold{while } (j < n) \wedge (s''\geq r') \wedge (s'\leq r'')
\triangleright \mbox{ verifying other $n-1$ runs}\\
9.&\T\T\T \Lambda\leftarrow \Lambda+S[j], k\leftarrow k'+j\\
10.&\T\T\T s'\leftarrow \left\lceil\dfrac{(\Lambda-1)^2+k(k+1)+1}{2k+1}\right\rceil\\
11.&\T\T\T s''\leftarrow \left\lfloor\dfrac{\Lambda^2+k(k+1)}{2k+1}\right\rfloor\\
12.&\T\T\T \bold{if } s''\geq r' \wedge s'\leq r''\\
13.&\T\T\T\T [r',r'']\leftarrow[\max(r',s'),\min(r'',s'')]\\
14.&\T\T\T j\leftarrow j+1\\
15.&\T\T i\leftarrow i+1\\
16.&\T\T \bold{if } n_{\max} < j\\
17.&\T\T\T n_{\max}\leftarrow j, k_{\mathrm{off}}\leftarrow k',
[r_{\min},r_{\max}]\leftarrow [r',r'']\\
18.& \bold{print}\ \mbox{$S$ is circular for $n_{\max}$ runs;
starting run $=k_{\mathrm{off}}$; $r\in[r_{\min},r_{\max}]$.}
\end{array}
\)
|
And the following procedure computes the parameters
corresponding to the first run-length of $S$.
|
$\mbox{Procedure Find-Params(int $A$, int $\Lambda$, int $k$)}$
|
|
\(
\begin{array}{@{}l@{}l}
1.& \mbox{Compute } \{\alpha_{uv}: 1\leq u\leq 4 \wedge v=(u+1)\mbox{ mod } 4\}
\triangleright \mbox{(from Table)}\\
2.& i\leftarrow 0\\
3.& \bold{for } a\leftarrow \lceil \alpha_{23}\rceil \mbox{ to } \lfloor \alpha_{41}\rfloor\\
4.&\T A[i][0]\leftarrow a \triangleright \mbox{computing } r'\\
5.&\T \bold{if } a< \alpha_{12}\\
6.&\T\T A[i][1]\leftarrow \lceil {\fnt_{2,\lambda}}(a,k)\rceil\\
7.&\T \bold{else}\\
8.&\T\T A[i][1]\leftarrow \lceil {\fnt_{1,\lambda}}(a,k)\rceil \triangleright \mbox{computing } r''\\
9.&\T \bold{if } a< \alpha_{34}\\
10.&\T\T A[i][2]\leftarrow \lfloor {\fnt_{3,\lambda}}(a,k)\rfloor\\
11.&\T \bold{else}\\
12.&\T\T A[i][2]\leftarrow \lfloor {\fnt_{4,\lambda}}(a,k)\rfloor\\
13.&\T i\leftarrow i+1\\
14.& m\leftarrow i
\end{array}
\)
|
|
|
Shown aside: Demonstration of the procedure FIND-PARAMS
on a run-length 7 to obtain the solution space $R_{ak}$ of the radius intervals
$\left\{\left[r'_j, r''_j\right]: j = 0, 1, 2\right\}$
corresponding to $m= 3$ square numbers lying in the interval
$\left[\left\lceil\alpha_{23}^2\right\rceil, \left\lfloor\alpha_{41}^2\right\rfloor\right] =
\left[9^2, 11^2\right]$.
|
Plots showing how the region the solution space R_{ak}
(shown in green) goes on changing as $k$ increases for a given
$\lambda = 10$.
|
Infimum and supremum circles
Provide a feasible range of $k$ (used in the Algorithm DCG),
based on the following lemma and theorem.
Lemma 6.
For the $k$th run $\langle p_{kt}\mid\,p_{kt}=(i_t,r-k)\rangle_{t=1}^{n_k}$,
the corresponding arc of the real circle $\rcir(o,r)$ in Octant 1
from $x=i_1$ to $x=i_{n_k}$ lies strictly between $y=r-k-\frac12$ and $y=r-k+\frac12$.
Theorem 3 (General radius range).
If $S$ is a part (in Octant 1) of a digital circle $\dcir(o,r)$, then
$r\in \left[\lceil \widetilde{r'}\rceil, \lfloor \widetilde{r''}\rfloor \right]$.
|
An instance of finding the infimum circle (shown in blue) and the
supremum circle (in red)
with radii 61 and 158 respectively, corresponding to the digital curve segment
$S=\langle 7, 5, 3, 4, 3, 2, 3, 2\rangle$.
Note that the first point of the first run is considered here to be $(0,0)$
for the purpose of simply finding the radii of the infimum and the supremum circles.
|
|
