# Conditional constrained and unconstrained quantization for a uniform
distribution on a hexagon

1Christina Hamilton  ,  2Evans Nyanney  ,  3Megha Pandey  and  4Mrinal K.
Roychowdhury  {1christina.hamilton01, 2evans.nyanney01,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In this paper, we have considered a uniform distribution on a regular hexagon
and the set of all its six vertices as a conditional set. For the uniform
distribution under the conditional set first, for all positive integers $n\geq
6$, we obtain the conditional optimal sets of $n$-points and the $n$th
conditional quantization errors, and then we calculate the conditional
quantization dimension and the conditional quantization coefficient in the
unconstrained scenario. Then, for the uniform distribution on the hexagon
taking the same conditional set, we investigate the conditional constrained
optimal sets of n-points and the conditional constrained quantization errors
for all $n\geq 6$, taking the constraint as the circumcircle, incircle, and
then the different diagonals of the hexagon.

###### Key words and phrases:

Probability measure, constrained and unconstrained quantization, optimal sets
of $n$-points, quantization dimension, quantization coefficient, hexagon

###### 2010 Mathematics Subject Classification:

60Exx, 94A34.

A part of the results in this paper was used in partial fulfillment of the
first author’s Master’s thesis at the University of Texas Rio Grande Valley
under the direction of the last author.

##  1\. Introduction

Constrained quantization has recently been introduced by Pandey and
Roychowdhury (see [PR1, PR2]). They have also introduced the conditional
quantization in both constrained and unconstrained quantization (see [PR5]).
For some follow up papers in the direction of constrained quantization, one
can see [PR3, PR4, BCDRV]). With the introduction of constrained quantization,
quantization now has two classifications: constrained quantization and
unconstrained quantization. For unconstrained quantization and its
applications one can see [DFG, DR, GG, GL, GL1, GL2, GL3, GN, KNZ, P, P1, R1,
R2, R3, Z1, Z2]. Constrained quantization has much more interdisciplinary
applications in the areas such as information theory, machine learning and
data compression, signal processing and national security. Let $P$ be a Borel
probability measure on $\mathbb{R}^{2}$ equipped with a Euclidean metric $d$
induced by the Euclidean norm $\|\cdot\|$.

######  Definition 1.1.

Let $S\subseteq\mathbb{R}^{2}$ be nonempty and closed. Let
$\beta\subset\mathbb{R}^{2}$ be given with $\text{card}(\beta)=\ell$ for some
$\ell\in\mathbb{N}$. Then, for $n\in\mathbb{N}$ with $n\geq\ell$, the $n$th
conditional constrained quantization error for $P$ with respect to the
constraint $S$ and the set $\beta$, is defined as

$V_{n}:=V_{n}(P)=\inf_{\alpha}\Big{\\{}\int\mathop{\min}\limits_{a\in\alpha\cup\beta}d(x,a)^{2}dP(x):\alpha\subseteq
S,~{}0\leq\text{card}(\alpha)\leq n-\ell\Big{\\}},$ (1)

where $\text{card}(A)$ represents the cardinality of the set $A$.

If $S=\mathbb{R}^{2}$, i.e., if there is no constraint, then the $n$th
conditional constrained quantization error, defined by Definition 1.1, reduces
to the definition of the $n$th conditional unconstrained quantization error,
i.e., the $n$th conditional unconstrained quantization error is defined as

$V_{n}:=V_{n}(P)=\inf_{\alpha}\Big{\\{}\int\mathop{\min}\limits_{a\in\alpha\cup\beta}d(x,a)^{2}dP(x):\alpha\subseteq\mathbb{R}^{2},~{}0\leq\text{card}(\alpha)\leq
n-\ell\Big{\\}}.$ (2)

For any $\gamma\subset\mathbb{R}^{2}$, the number

$V(P;\gamma):=\int\mathop{\min}\limits_{a\in\gamma}d(x,a)^{2}dP(x)$

is called the distortion error for $P$ with respect to the set $\gamma$. We
assume that $\int d(x,0)^{2}dP(x)<\infty$ to make sure that the infimum in (1)
and (2) exist (see [PR1]). For a finite set $\gamma\subset\mathbb{R}^{2}$ and
$a\in\gamma$, by $M(a|\gamma)$ we denote the set of all elements in
$\mathbb{R}^{2}$ which are nearest to $a$ among all the elements in $\gamma$,
i.e.,
$M(a|\gamma)=\\{x\in\mathbb{R}^{2}:d(x,a)=\mathop{\min}\limits_{b\in\gamma}d(x,b)\\}.$
$M(a|\gamma)$ is called the Voronoi region in $\mathbb{R}^{2}$ generated by
$a\in\gamma$.

######  Definition 1.2.

A set $\alpha\cup\beta$, where $P(M(b|\alpha\cup\beta))>0$ for $b\in\beta$,
for which the infimum in $V_{n}$ exists and contains no less than $\ell$
elements, and no more than $n$ elements is called an optimal set of $n$-points
for $P$, or more specifically a conditional optimal set of $n$-points for $P$.
Elements of an optimal set are called optimal elements.

Write $V_{\infty}(P):=\mathop{\lim}\limits_{n\to\infty}V_{n}(P).$ Then, the
number

$\displaystyle D(P):=\mathop{\lim}\limits_{n\to\infty}\frac{2\log
n}{-\log(V_{n}(P)-V_{\infty}(P))}$

if it exists, is called the conditional quantization dimension of $P$ and is
denoted by $D(P)$. The conditional quantization dimension measures the speed
at which the specified measure of the quantization error converges as $n$
tends to infinity. For any $\kappa>0$, the number

$\lim_{n}n^{\frac{2}{\kappa}}(V_{n}(P)-V_{\infty}(P)),$

if it exists, is called the $\kappa$-dimensional conditional quantization
coefficient for $P$.

Let us consider a regular hexagon with vertices
$A(-\frac{1}{2},-\frac{\sqrt{3}}{2})$, $B(\frac{1}{2},-\frac{\sqrt{3}}{2})$,
$C(1,0)$, $D(\frac{1}{2},\frac{\sqrt{3}}{2})$,
$E(-\frac{1}{2},\frac{\sqrt{3}}{2})$, and $F(-1,0)$ as shown in Figure 1. Let
us take the conditional set $\beta$ as the set of all the vertices of the
hexagon. Let $P$ be a uniform probability distribution on the hexagon. In this
paper, in Section 3 first, we calculate the conditional unconstrained optimal
sets of $n$-points and the $n$th conditional unconstrained quantization errors
for all $n\in\mathbb{N}$ with $n\geq 6$, and then we calculate the conditional
unconstrained quantization dimension and the conditional unconstrained
quantization coefficient for the uniform distribution $P$. Then, for all
$n\in\mathbb{N}$ with $n\geq 6$, we calculate the conditional constrained
optimal sets of $n$-points, and the $n$th conditional constrained quantization
errors for the uniform distribution $P$ taking different constraints: In
Section 4, taking the constraint as the circumcircle of the hexagon; in
Section 5, taking the constraint as the incircle of the hexagon, and in
Section 6, taking the constraint as a diagonal of the hexagon.

##  2\. Preliminaries

For any two elements $(a,b)$ and $(c,d)$ in $\mathbb{R}^{2}$, we write

$\rho((a,b),(c,d)):=(a-c)^{2}+(b-d)^{2},$

which gives the squared Euclidean distance between the two elements $(a,b)$
and $(c,d)$. Let $p$ and $q$ be two elements that belong to an optimal set of
$n$-points for some positive integer $n$, and let $e$ be an element on the
boundary of the Voronoi regions of the elements $p$ and $q$. Since the
boundary of the Voronoi regions of any two elements is the perpendicular
bisector of the line segment joining the elements, we have

$\rho(p,e)-\rho(q,e)=0.$

We call such an equation a canonical equation. Let $L$ be the regular hexagon
$ABCDEF$ as described in the previous section. Let
$L_{1},L_{2},L_{3},L_{4},L_{5},L_{6}$ represent the sides $AB,BC,CD,DE,EF,FA$,
respectively. Then, we have

$L=L_{1}\cup L_{2}\cup L_{3}\cup L_{4}\cup L_{5}\cup L_{6}.$

Let $s$ represent the distance of any point on the hexagon $L$ from the vertex
$A$ tracing along the boundary of the hexagon in the counterclockwise
direction. Then, the points $A,B,C,D,E,F$ are, respectively, represented by
$s=0,s=1,s=2,s=3,s=4,s=5,s=6$. The probability density function (pdf) $f$ of
the uniform distribution $P$ is given by $f(s):=f(x,y)=\frac{1}{6}$ for all
$(x,y)\in L$, and zero otherwise. The sides
$L_{1},L_{2},L_{3},L_{4},L_{5},L_{6}$ are represented by the parametric
equations as follows:

$\displaystyle L_{1}=\\{(t-\frac{1}{2},-\frac{\sqrt{3}}{2})\\},$
$\displaystyle\quad L_{2}=\\{(\frac{t+1}{2},\frac{1}{2}\sqrt{3}(t-1))\\},\quad
L_{3}=\\{(1-\frac{t}{2},\frac{\sqrt{3}t}{2})\\},\quad
L_{4}=\\{(\frac{1}{2}-t,\frac{\sqrt{3}}{2}),$ $\displaystyle\quad
L_{5}=\\{(\frac{1}{2}(-t-1),-\frac{1}{2}\sqrt{3}(t-1)),\quad
L_{6}=\\{(\frac{t-2}{2},-\frac{\sqrt{3}t}{2})\\},$

where $0\leq t\leq 1$. Again, $dP(s)=P(ds)=f(x_{1},x_{2})ds$. Notice that on
each of $L_{j}$, for $1\leq j\leq 6$, we have
$ds=\sqrt{(dx)^{2}+(dy)^{2}}=dt$. The conditional set $\beta$ considered in
this paper is the set

$\beta=\Big{\\{}(\cos\theta,\sin\theta):\theta=0,\frac{\pi}{3},\frac{2\pi}{3},\frac{3\pi}{3},\frac{4\pi}{3},\frac{5\pi}{3}\Big{\\}}.$

Let $T:\mathbb{R}^{2}\to\mathbb{R}^{2}$ be an affine transformations such that
$T(x,y)=(\frac{x}{2}-\frac{\sqrt{3}y}{2},\frac{\sqrt{3}x}{2}+\frac{y}{2})$ for
$(x,y)\in\mathbb{R}^{2}$. Also, for any $j\in\mathbb{N}$, by $T^{j}$ it is
meant the composition mapping $T^{j}=T\circ T\circ T\circ\cdots
j\text{-times}.$ If $j=0$, i.e., by $T^{0}$ it is meant the identity mapping
on $\mathbb{R}^{2}$. Then, notice that

$\displaystyle T(L_{1})$
$\displaystyle=L_{2},\,T^{2}(L_{1})=L_{3},\,T^{3}(L_{1})=L_{4},T^{4}(L_{1})=L_{5},T^{5}(L_{1})=L_{6}.$

The following proposition is a modified version of Proposition 2.1 in [PR5].

######  Proposition 2.1.

(see [PR5]) Let $\alpha_{n}$ be an optimal set of $n$-points for $P$ such that
$\alpha_{n}$ contains $m$ elements, for some $m\leq n$, from the side $L_{1}$
including the endpoints $A(-\frac{1}{2},-\frac{\sqrt{3}}{2})$ and
$B(\frac{1}{2},-\frac{\sqrt{3}}{2})$, then

$\alpha_{n}\cap
L_{1}=\Big{\\{}\Big{(}-\frac{1}{2}+\frac{i-1}{m-1},\,-\frac{\sqrt{3}}{2}\Big{)}:1\leq
i\leq m\Big{\\}},$

and the distortion error contributed by these $m$ elements from the side $AB$
is given by

$V(P,\alpha_{n}\cap L_{1})=\frac{1}{72(m-1)^{2}}.$

In the following sections, we give the main results of the paper.

$A(-\frac{1}{2},-\frac{\sqrt{3}}{2})$$B(\frac{1}{2},-\frac{\sqrt{3}}{2})$$D(\frac{1}{2},\frac{\sqrt{3}}{2})$$E(-\frac{1}{2},\frac{\sqrt{3}}{2})$$C(1,0)$$F(-1,0)$
Figure 1. The regular hexagon with the circumcircle and the incircle.

##  3\. Conditional unconstrained quantization for the uniform distribution
$P$

In this section, we calculate the conditional unconstrained optimal sets of
$n$-points and the conditional unconstrained quantization errors for all
$n\geq 6$. Clearly the conditional optimal set of six-points is the set
$\beta$ itself. We now investigate them for $n\geq 6$. Recall that in
unconstrained quantization, if $\alpha_{n}$ is an optimal set of $n$-points
for any $n\geq 6$, then the elements in $\alpha_{n}\setminus\beta$ are the
conditional expectations in their own Voronoi regions. Hence, for any $n\geq
6$, the elements of the optimal sets $\alpha_{n}$ must lie on the hexagon $L$.
Let $\alpha_{n}$ contain $n_{i}$ elements from a side $L_{j}$, then the set of
all these $n_{i}$ elements from $L_{j}$, except the rightmost element, is
denoted by $\alpha_{n}\cap(L_{j}(n_{i}-1))$, and the corresponding distortion
error due to these $n_{i}$ elements on $L_{j}$ is denoted by
$V(P;\alpha_{n}\cap(L_{j}(n_{i})))$, where $1\leq i,j\leq 6$. Notice that
$n_{i}\geq 2$ for all $1\leq i\leq 6$.

Let us now give the following proposition which plays an important role in
this section.

######  Proposition 3.1.

Let $\alpha_{n}$ be a conditional optimal set of $n$-points for $P$ for some
$n\geq 6$. Let $\text{card}(\alpha_{n}\cap L_{j})=n_{j}$ for $1\leq j\leq 6$
and $T$ be the affine transformation. Then,

$\alpha_{n}\cap
L_{1}(n_{1}-1)=\Big{\\{}\Big{(}-\frac{1}{2}+\frac{j-1}{n_{1}-1},\,-\frac{\sqrt{3}}{2}\Big{)}:1\leq
i\leq n_{1}-1\Big{\\}},$

and

$\alpha_{n}\cap L_{j}(n_{j}-1)=T^{j}\Big{(}\alpha_{n}\cap
L_{1}(n_{j}-1)\Big{)}\text{ for }2\leq j\leq 6,$

with the conditional unconstrained quantization error

$V_{n}=V_{n_{1},n_{2},n_{3},n_{4},n_{5},n_{6}}(P):=\sum_{j=1}^{6}V(P;\alpha_{n}\cap
L_{j}(n_{j}))=\frac{1}{72}\sum_{j=1}^{6}\frac{1}{(n_{j}-1)^{2}}.$

###### Proof.

The proof of the expression for $\alpha_{n}\cap L_{1}(n_{1}-1)$ directly
follows from Proposition 2.1. The proof of the expressions for $\alpha_{n}\cap
L_{j}(n_{j}-1)$ are the consequence of Proposition 2.1 and the affine
transformation $T$. Due to rotational symmetry, using Proposition 2.1, we have

$V(P;\alpha_{n}\cap L_{j}(n_{j}))=V(P;\alpha_{n}\cap
L_{1}(n_{j}))=\frac{1}{72}\frac{1}{(n_{j}-1)^{2}}\text{ for all }1\leq j\leq
6.$

Hence,

$V_{n}=V_{n_{1},n_{2},n_{3},n_{4},n_{5},n_{6}}(P)=\frac{1}{72}\sum_{j=1}^{6}\frac{1}{(n_{j}-1)^{2}}.$

Thus, the proof of the proposition is complete. ∎

######  Lemma 3.2.

Let $n_{j}\in\mathbb{N}$ for $1\leq j\leq 6$ be the numbers as defined in
Proposition 3.1. Then, $|n_{i}-n_{j}|=0$, or $1$ for $1\leq i\neq j\leq 6$.

###### Proof.

We first show that $|n_{1}-n_{2}|=0,\text{ or }1$. Write
$m:=(n_{1}-1)+(n_{2}-1)$. Now, the distortion error contributed by the $m$
elements in $\alpha_{n}(L_{1})\cup\alpha_{n}(L_{2})$ is given by

$\frac{1}{72}\Big{(}\frac{1}{(n_{1}-1)^{2}}+\frac{1}{(n_{2}-1)^{2}}\Big{)}.$

The above expression is minimum if $n_{1}-1\approx\frac{m}{2}$ and
$n_{2}-1\approx\frac{m}{2}$. Thus, we see that if $m=2k$ for some positive
integer $k$, then $n_{1}-1=n_{2}-1=k$, and if $m=2k+1$ for some positive
integer $k$, then either $(n_{1}-1=k+1$ and $n_{2}-1=k)$ or $(n_{1}-1=k$ and
$n_{2}-1=k+1)$ which yields the fact that $|n_{1}-n_{2}|=0,\text{ or }1$.
Similarly, we can show that $|n_{i}-n_{j}|=0$, or $1$ for any $1\leq i\neq
j\leq 6$. Thus, the proof of the lemma is complete. ∎

######  Theorem 3.3.

Let $\alpha_{n}$ be a conditional optimal set of $n$-points for $P$ for some
$n\geq 6$. Then,

$\displaystyle\alpha_{n}=\Big{(}\alpha_{n}\cap
L_{1}(n_{1}-1)\Big{)}\bigcup\Big{(}\bigcup_{j=1}^{6}T^{j}(\alpha_{n}\cap
L_{1}(n_{j}-1))\Big{)}$

with the conditional unconstrained quantization error

$V_{n}=\frac{1}{72}\sum_{j=1}^{6}\frac{1}{(n_{j}-1)^{2}},$

where $n_{j}$ are chosen in such a way that $n_{j}\geq 2$ and
$\sum\limits_{j=1}^{6}(n_{j}-1)=n$, and $|n_{i}-n_{j}|=0,\text{ or }1$ for
$1\leq i\neq j\leq 6$.

###### Proof.

The proof of the theorem follows due to Proposition 3.1 and Lemma 3.2. ∎

######  Remark 3.4.

Let $\alpha_{n}$ be a conditional optimal set of $n$-points for $P$ given by
Theorem 3.3. Then, if $n=6k$ for some $k\in\mathbb{N}$, then $\alpha_{n}$ is
unique. If $n=6k+j$ for some $j,k\in\mathbb{N}$ with $1\leq j\leq 5$, then the
number of such sets is given by $\binom{6}{j}$, where
$\binom{6}{j}=\frac{6!}{j!(6-j)!}$ for $1\leq j\leq 5$.

Using Theorem 3.3, the following example can be obtained.

######  Example 3.5.

Let $\alpha_{n}$ be an optimal set of $n$-points given by Theorem 3.3. Then,
we obtain the optimal sets as follows (see Figure 2):

$\displaystyle\alpha_{6}$
$\displaystyle=\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(\frac{1}{2},-\frac{\sqrt{3}}{2}),(1,0),(\frac{1}{2},\frac{\sqrt{3}}{2}),(-\frac{1}{2},\frac{\sqrt{3}}{2}),(-1,0)\\}$
$\displaystyle\qquad\text{ with quantization error }V_{6}=\frac{1}{12},$
$\displaystyle\alpha_{7}$
$\displaystyle=\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(0,-\frac{\sqrt{3}}{2}),(\frac{1}{2},-\frac{\sqrt{3}}{2}),(1,0),(\frac{1}{2},\frac{\sqrt{3}}{2}),(-\frac{1}{2},\frac{\sqrt{3}}{2}),(-1,0)\\}$
$\displaystyle\qquad\text{ with quantization error }V_{7}=\frac{7}{96},$
$\displaystyle\alpha_{8}$
$\displaystyle=\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(0,-\frac{\sqrt{3}}{2}),(\frac{1}{2},-\frac{\sqrt{3}}{2}),(\frac{3}{4},-\frac{\sqrt{3}}{4}),(1,0),(\frac{1}{2},\frac{\sqrt{3}}{2}),(-\frac{1}{2},\frac{\sqrt{3}}{2}),(-1,0)\\}$
$\displaystyle\qquad\text{ with quantization error }V_{8}=\frac{1}{16},$
$\displaystyle\alpha_{9}$
$\displaystyle=\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(0,-\frac{\sqrt{3}}{2}),(\frac{1}{2},-\frac{\sqrt{3}}{2}),(\frac{3}{4},-\frac{\sqrt{3}}{4}),(1,0),(\frac{3}{4},\frac{\sqrt{3}}{4}),(\frac{1}{2},\frac{\sqrt{3}}{2}),(-\frac{1}{2},\frac{\sqrt{3}}{2}),(-1,0)\\}$
$\displaystyle\qquad\text{ with quantization error }V_{9}=\frac{5}{96},$ and
so on.

Figure 2. In conditional unconstrained quantization the dots represent the
elements in an optimal set of $n$-points for $6\leq n\leq 13$.

######  Theorem 3.6.

The conditional unconstrained quantization dimension $D(P)$ of the probability
measure $P$ exists, and $D(P)=1$, and the $D(P)$-dimensional conditional
unconstrained quantization coefficient for $P$ exists as a finite positive
number and equals $3$.

###### Proof.

For $n\in\mathbb{N}$ with $n\geq 6$, let $\ell(n)$ be the unique natural
number such that $6{\ell(n)}\leq n<6({\ell(n)+1})$. Then,
$V_{6(\ell(n)+1)}\leq V_{n}\leq V_{6{\ell(n)}}$, i.e.,
$\frac{1}{12(\ell(n)+1)^{2}}\leq V_{n}\leq\frac{1}{12(\ell(n))^{2}}$ yielding
$\mathop{\lim}\limits_{n\to\infty}V_{n}=0$. Take $n$ large enough so that
$V_{6{\ell(n)}}-V_{\infty}<1$. Then,

$0<-\log(V_{6{\ell(n)}}-V_{\infty})\leq-\log(V_{n}-V_{\infty})\leq-\log(V_{6({\ell(n)+1})}-V_{\infty})$

yielding

$\frac{2\log 6\ell(n)}{-\log(V_{6({\ell(n)+1})}-V_{\infty})}\leq\frac{2\log
n}{-\log(V_{n}-V_{\infty})}\leq\frac{2\log
6(\ell(n)+1)}{-\log(V_{6{\ell(n)}}-V_{\infty})}.$

Notice that

$\displaystyle\lim_{n\to\infty}\frac{2\log
6\ell(n)}{-\log(V_{6({\ell(n)+1})}-V_{\infty})}$
$\displaystyle=\lim_{n\to\infty}\frac{2\log
6\ell(n)}{-\log\frac{1}{12(\ell(n)+1)^{2}}}=1,\text{ and }$
$\displaystyle\lim_{n\to\infty}\frac{2\log 6(\ell(n)+1)}{-\log
V_{6{\ell(n)}}}$ $\displaystyle=\lim_{n\to\infty}\frac{2\log
6(\ell(n)+1)}{-\log\frac{1}{12(\ell(n))^{2}}}=1.$

Hence, $\lim_{n\to\infty}\frac{2\log n}{-\log(V_{n}-V_{\infty})}=1$, i.e., the
conditional unconstrained quantization dimension $D(P)$ of the probability
measure $P$ exists and $D(P)=1$. Since

$\displaystyle\lim_{n\to\infty}n^{2}(V_{n}-V_{\infty})\geq\lim_{n\to\infty}(6\ell(n))^{2}(V_{6(\ell(n)+1)}-V_{\infty})=\lim_{n\to\infty}(6\ell(n))^{2}\frac{1}{12(\ell(n)+1)^{2}}=3,\text{
and }$
$\displaystyle\lim_{n\to\infty}n^{2}(V_{n}-V_{\infty})\leq\lim_{n\to\infty}(6(\ell(n)+1))^{2}(V_{6\ell(n)}-V_{\infty})=\lim_{n\to\infty}(6(\ell(n)+1))^{2}\frac{1}{12(\ell(n))^{2}}=3,$

by the squeeze theorem, we have $\lim_{n\to\infty}n^{2}(V_{n}-V_{\infty})=3$,
i.e., the $D(P)$-dimensional conditional unconstrained quantization
coefficient for $P$ exists as a finite positive number and equals $3$. Thus,
the proof of the theorem is complete. ∎

##  4\. Conditional constrained quantization for the uniform distribution $P$
when the constraint is the circumcircle

In this section, for all $n\geq 6$, we calculate the conditional constrained
optimal sets $\alpha_{n}$ of $n$-points and the corresponding $n$th
conditional constrained quantization errors $V_{n}$ for the uniform
distribution $P$ on the hexagon with respect to the conditional set $\beta$
and the constraint $S$ which is the circumcircle of the hexagon. Let
$S_{1},S_{2},S_{3},S_{4},S_{5},S_{6}$ be the circular arcs subtended by the
chords $AB,BC,CD,DE,EF,FA$, respectively (see Figure 1). Then, we have

$S=S_{1}\cup S_{2}\cup S_{3}\cup S_{4}\cup S_{5}\cup S_{6}.$

The arcs $S_{1},S_{2},S_{3},S_{4},S_{5},S_{6}$ are represented by the
parametric equations as follows:

$S_{j}=\\{(\cos(\theta+\frac{4\pi}{3}),\sin(\theta+\frac{4\pi}{3})):\frac{(j-1)\pi}{3}\leq\theta\leq\frac{j\pi}{3}\\}$

for $1\leq j\leq 6$. Also notice that for the affine transformation $T$,
defined in Section 2, we have

$T(S_{1})=S_{2},\,T^{2}(S_{1})=S_{3},\,T^{3}(S_{1})=S_{4},T^{4}(S_{1})=S_{5},T^{5}(S_{1})=S_{6}.$

Let $\alpha_{n}$ be an optimal set of $n$-points for $P$ for some $n\geq 6$.
Notice that if $n=6$, then $\alpha_{n}=\beta$, where $\beta$ is the
conditional set. Hence, in the sequel we assume that $n\geq 7$. Let
$\alpha_{n}$ contain $n_{i}$ elements from $S_{i}$ including the end elements,
i.e., $\text{card}(\alpha_{n}\cap S_{i})=n_{i}$, where $n_{i}\geq 2$ with at
least one $n_{i}\geq 3$ for $1\leq i\leq 6$. Notice that to obtain
$\alpha_{n}\cap S_{i}$ and the corresponding distortion error
$V(P;\alpha_{n}\cap S_{i})$ contributed by the elements in $\alpha_{n}\cap
S_{i}$ on $L_{i}$, where $\text{card}(\alpha_{n}\cap S_{i})=n_{i}$, it enough
to obtain $\alpha_{n}\cap S_{1}$ and the corresponding distortion error
$V(P;\alpha_{n}\cap S_{1})$ with $\text{card}(\alpha_{n}\cap S_{1})=n_{i}$,
and then to use the affine transformation $T$, as we know

$\alpha_{n}\cap S_{i}=T^{i-1}(\alpha_{n}\cap S_{1}),\text{ where
}\text{card}(\alpha_{n}\cap S_{1})=n_{i},\text{ for }2\leq i\leq 6.$

Moreover, notice that $V(P;\alpha_{n}\cap S_{i})=V(P;\alpha_{n}\cap
S_{1}),\text{ where }\text{card}(\alpha_{n}\cap S_{1})=n_{i}$ and
$V(P;\alpha_{n}\cap S_{1})$ denote the distortion error contributed by the
$n_{i}$ elements on $L_{1}$. Again, notice that if $\text{card}(\alpha_{n}\cap
S_{i})=n_{i}=2$, then

$\alpha_{n}\cap
S_{i}=T^{i-1}\Big{(}\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(\frac{1}{2},-\frac{\sqrt{3}}{2})\\}\Big{)}\text{
for }1\leq i\leq 6.$

Let $\text{card}(\alpha_{n}\cap S_{1})=k$ with $k\geq 3$. Let the elements in
$\alpha_{n}\cap S_{1}$ be represented by the parameters
$\theta_{1}<\theta_{1}<\theta_{2}<\dots<\theta_{k}$, including the end
elements $\theta_{1}=\frac{4\pi}{3}$ and $\theta_{k}=\frac{5\pi}{3}$, where
$k\geq 3$. Let the boundary of the Voronoi regions of the elements
$\theta_{j}$ and $\theta_{j+1}$ intersect the side $L_{1}$ at the elements
$(a_{j},-\frac{\sqrt{3}}{2})$ for $1\leq j\leq k-1$. Then, the canonical
equations are given by

$\rho((\cos\theta_{j},\sin\theta_{j}),(a_{j},-\frac{\sqrt{3}}{2}))-\rho((\cos\theta_{j+1},\sin\theta_{j+1}),(a_{j},-\frac{\sqrt{3}}{2}))=0$

for $1\leq j\leq k-1$. Solving the canonical equations, we have

$\displaystyle
a_{j}=\frac{-\sin^{2}\theta_{j}+\sin^{2}\theta_{j+1}-\sqrt{3}\sin\theta_{j}+\sqrt{3}\sin\theta_{j+1}-\cos^{2}\theta_{j}+\cos^{2}\theta_{j+1}}{2\cos\theta_{j+1}-2\cos\theta_{j}}$
(3)

for $1\leq j\leq k-1$. Hence, if $V(P;\alpha_{n}\cap S_{1})$ is the distortion
error contributed by the elements in $\alpha_{n}\cap S_{1}$ on $L_{1}$, then
we have

$\displaystyle V(P;\alpha_{n}\cap S_{1})$
$\displaystyle=\frac{1}{6}\Big{(}\int_{-\frac{1}{2}}^{a_{1}}\rho((x,-\frac{\sqrt{3}}{2}),(\cos\theta_{1},\sin\theta_{1}))\,dx+\sum_{j=1}^{k-2}\int_{a_{j}}^{a_{j+1}}\rho((x,-\frac{\sqrt{3}}{2}),(\cos\theta_{j+1},\sin\theta_{j+1}))\,dx$
$\displaystyle\qquad+\int_{a_{k}}^{\frac{1}{2}}\rho((x,-\frac{\sqrt{3}}{2}),(\cos\theta_{k},\sin\theta_{k}))\,dx\Big{)}.$
(4)

######  Methodology 4.1.

To obtain the conditional constrained optimal sets $\alpha_{n}$ of $n$-points
and the $n$th conditional constrained quantization errors for the uniform
distribution $P$ on the hexagon with respect to the conditional set $\beta$
and the constraint $S$ for any $n\geq 7$, assume that
$\text{card}(\alpha_{n}\cap S_{1})=k$, i.e.,

$\alpha_{n}\cap S_{1}=\\{(\cos\theta_{j},\sin\theta_{j}):1\leq j\leq k\\}$

for $k\geq 3$. Then, solving the canonical equations we obtain the boundary of
the Voronoi regions $(a_{j},-\frac{\sqrt{3}}{2})$, where $a_{j}$ are given as
in (3). Putting the values of $a_{j}$, $\theta_{1}=\frac{4\pi}{3}$, and
$\theta_{k}=\frac{5\pi}{3}$ in (4), we obtain the distortion error
$V(P;\alpha_{n}\cap S_{1})$, which is a function of $\theta_{j}$ for $2\leq
j\leq k-1$. Now, using calculus, we obtain the values of $\theta_{j}$ for
$2\leq j\leq k-1$ for which $V(P;\alpha_{n}\cap S_{1})$ is minimum. Upon
obtained the values of $\theta_{j}$, we can easily obtain $\alpha_{n}\cap
S_{1}$ and the corresponding distortion error $V(P;\alpha_{n}\cap S_{1})$. As
described before due to the affine transformation, we can also obtain
$\alpha_{n}\cap S_{i}$ and the corresponding distortion error
$V(P;\alpha_{n}\cap S_{i})$ for $2\leq i\leq 6$. Thus, we have

$\alpha_{n}=\bigcup_{i=1}^{6}(\alpha_{n}\cap S_{i})\text{ with the $n$th
constrianed quantization error }V_{n}=\sum_{i=1}^{6}V(P;\alpha_{n}\cap
S_{i}).$

∎

Recall that $S=\mathop{\cup}\limits_{j=1}^{6}S_{j}$ and $S_{j}$ are
rotationally symmetric, and $P$ is a uniform distribution. Hence, the
following lemma, which is similar to Lemma 3.2, is also true here.

######  Lemma 4.2.

Let $\alpha_{n}$ be an optimal set of $n$-points with
$\text{card}(\alpha_{n}\cap S_{i})=n_{i}$ for $1\leq i\leq 6$. Then,
$|n_{i}-n_{j}|=0$, or $1$ for $1\leq i\neq j\leq 6$.

Figure 3. In conditional constrained quantization with the constraint as the
circumcircle the dots represent the elements in an optimal set of $n$-points
for $6\leq n\leq 13$.

The results in the following examples are obtained using Methodology 4.1 and
Lemma 4.2 (see Figure 3).

######  Example 4.3.

To obtain the optimal set $\alpha_{7}$ and the corresponding conditional
constrained quantization error $V_{7}$, we proceed as follows: By Lemma 4.2,
we can assume that $\text{card}(\alpha_{7}\cap S_{1})=3$ and
$\text{card}(\alpha_{7}\cap S_{j})=2$ for $2\leq j\leq 6$. Then, using
Methodology 4.1, we obtain

$\alpha_{7}\cap
S_{1}=\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(0,1),(\frac{1}{2},-\frac{\sqrt{3}}{2})\\}\text{
and }V(P;\alpha_{7}\cap S_{1})=\frac{\sqrt{3}}{2}-\frac{31}{36}.$

Moreover, we have

$\alpha_{7}\cap
S_{j}=T^{j}(\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(\frac{1}{2},-\frac{\sqrt{3}}{2})\\})\text{
with }V(\alpha_{7}\cap S_{j})=\frac{1}{72}\text{ for }2\leq j\leq 6.$

Hence,

$\displaystyle\alpha_{7}$ $\displaystyle=\bigcup_{j=1}^{6}\alpha_{7}\cap
S_{j}=\beta\bigcup\\{(0,-1)\\}\text{ with }$ $\displaystyle V_{7}$
$\displaystyle=V(P;\alpha_{7}\cap S_{1})+\sum_{j=2}^{6}V(P;\alpha_{7}\cap
S_{j})=\frac{\sqrt{3}}{2}-\frac{31}{36}+\frac{5}{72}=\frac{\sqrt{3}}{2}-\frac{19}{24}.$

######  Example 4.4.

Proceeding analogously as Example 4.3, we obtain the following results (see
Figure 3).

$\displaystyle\alpha_{8}$ $\displaystyle=\beta\cup\\{(0,-1),T(0,-1)\\}\text{
with }V_{8}=2(\frac{\sqrt{3}}{2}-\frac{31}{36})+\frac{4}{72};$
$\displaystyle\alpha_{9}$
$\displaystyle=\beta\cup\\{(0,-1),T(0,-1),T^{2}(0,-1)\\}\text{ with
}V_{9}=3(\frac{\sqrt{3}}{2}-\frac{31}{36})+\frac{3}{72};$
$\displaystyle\alpha_{10}$
$\displaystyle=\beta\cup\\{(0,-1),T(0,-1),T^{2}(0,-1),T^{3}(0,-1)\\}\text{
with }V_{10}=4(\frac{\sqrt{3}}{2}-\frac{31}{36})+\frac{2}{72};$
$\displaystyle\alpha_{11}$
$\displaystyle=\beta\cup\\{(0,-1),T(0,-1),T^{2}(0,-1),T^{3}(0,-1),T^{4}(0,-1)\\}\text{
with }V_{11}=4(\frac{\sqrt{3}}{2}-\frac{31}{36})+\frac{1}{72};$
$\displaystyle\alpha_{12}$
$\displaystyle=\beta\cup\\{(0,-1),T(0,-1),T^{2}(0,-1),T^{3}(0,-1),T^{4}(0,-1),T^{5}(0,-1)\\}\text{
with }V_{12}=5(\frac{\sqrt{3}}{2}-\frac{31}{36}).$

######  Example 4.5.

To obtain the constrained optimal set of $n$-points for $n=13$ (see Figure 3),
we proceed as follows: Notice that $n=13=2\times 6+1$. Hence, by Lemma 4.2, we
can assume that $\text{card}(\alpha_{13}\cap
S_{1})=4,\text{card}(\alpha_{13}\cap S_{j})=3\text{ for }2\leq j\leq 6.$ Then,
using Methodology 4.1, we obtain $\alpha_{13}\cap S_{1}$ and $\alpha_{13}\cap
S_{j}$ for $2\leq j\leq 6$ yielding

$\displaystyle\alpha_{13}\cap S_{1}$
$\displaystyle=\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(-0.181083,-0.983468),(0.181083,-0.983468),(\frac{1}{2},-\frac{\sqrt{3}}{2})\\},$
$\displaystyle\alpha_{13}\cap S_{j}$
$\displaystyle=T^{j}\Big{(}\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(0,1),(\frac{1}{2},-\frac{\sqrt{3}}{2})\\}\Big{)}\text{
for }2\leq j\leq 6.$

Hence,

$\alpha_{13}=\beta\cup\\{(-0.181083,-0.983468),(0.181083,-0.983468)\\}\cup\bigcup_{j=2}^{6}T^{j}\Big{(}\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(0,1),(\frac{1}{2},-\frac{\sqrt{3}}{2})\\}\Big{)},$

and

$V_{13}=V(P;\alpha_{13}\cap S_{1})+\sum_{j=2}^{6}V(P;\alpha_{13}\cap
S_{j})=\frac{1}{72}\left(-17-27\sqrt[3]{3}+27\
3^{2/3}\right)+5(\frac{\sqrt{3}}{2}-\frac{31}{36}).$

##  5\. Conditional constrained quantization for the uniform distribution $P$
when the constraint is the incircle

In this section, for all $n\geq 6$, we calculate the conditional constrained
optimal sets $\alpha_{n}$ of $n$-points and the corresponding $n$th
conditional constrained quantization errors $V_{n}$ for the uniform
distribution $P$ on the hexagon with respect to the conditional set $\beta$
and the constraint $S$ which is the incircle of the hexagon and is represented
by the parametric equations as follows:

$S:=\\{(r\cos\theta,r\sin\theta):r=\frac{\sqrt{3}}{2}\text{ and
}0\leq\theta\leq 2\pi\\}.$

Let $S_{i}$ be the circular arcs of the incircle lying over the sides $L_{i}$
subtending the same central angle of $\frac{\pi}{3}$ for $1\leq i\leq 6$ (see
Figure 4). Let $\alpha_{n}$ be an optimal set of $n$-points for $P$ for some
$n\geq 6$. Notice that if $n=6$, then $\alpha_{n}=\beta$, where $\beta$ is the
conditional set, i.e., $\alpha_{6}$ does not contain any element from $S_{i}$
for any $1\leq i\leq 6$. Hence, in the sequel we assume that $n\geq 7$. Let
$\alpha_{n}$ contains $n_{i}$ elements from $S_{i}\cup L_{i}$ including the
two elements in the set $L_{i}\cap\beta$, i.e.,
$\text{card}(\alpha_{n}\cap(S_{i}\cup L_{i}))=n_{i}$, where $n_{i}\geq 2$ with
at least one $n_{i}\geq 3$ for $1\leq i\leq 6$. Notice that to obtain
$\alpha_{n}\cap(S_{i}\cup L_{i})$ and the corresponding distortion error
$V(P;\alpha_{n}\cap(S_{i}\cup L_{i}))$ contributed by the elements in
$\alpha_{n}\cap(S_{i}\cup L_{i})$ on $L_{i}$, where
$\text{card}(\alpha_{n}\cap(S_{i}\cup L_{i}))=n_{i}$, it enough to obtain
$\alpha_{n}\cap(S_{1}\cup L_{1})$ and the corresponding distortion error
$V(P;\alpha_{n}\cap(S_{1}\cup L_{1}))$ with
$\text{card}(\alpha_{n}\cap(S_{1}\cup L_{1}))=n_{i}$, and then to use the
affine transformation $T$, as we know

$\alpha_{n}\cap(S_{i}\cup L_{i})=T^{i-1}(\alpha_{n}\cap(S_{1}\cup
L_{1})),\text{ where }\text{card}(\alpha_{n}\cap(S_{1}\cup
L_{1}))=n_{i},\text{ for }2\leq i\leq 6.$

Moreover, notice that $V(P;\alpha_{n}\cap(S_{i}\cup
L_{i}))=V(P;\alpha_{n}\cap(S_{1}\cup L_{1})),\text{ where
}\text{card}(\alpha_{n}\cap(S_{1}\cup L_{1}))=n_{i}$ and
$V(P;\alpha_{n}\cap(S_{1}\cup L_{1}))$ denote the distortion error contributed
by the $n_{i}$ elements on $L_{1}$.

Since $P$ is a uniform distribution and $S_{i}\cup L_{i}$ are rotationally
symmetric, the following lemma, which is similar to Lemma 3.2, is also true
here.

######  Lemma 5.1.

Let $\alpha_{n}$ be an optimal set of $n$-points with
$\text{card}(\alpha_{n}\cap(S_{i}\cup L_{i}))=n_{i}$ for $1\leq i\leq 6$.
Then, $|n_{i}-n_{j}|=0$, or $1$ for $1\leq i\neq j\leq 6$.

######  Remark 5.2.

Notice the dotted circles in Figure 4 with centers
$A(-\frac{1}{2},-\frac{\sqrt{3}}{2})$ and
$B(\frac{1}{2},-\frac{\sqrt{3}}{2})$. Recall that $P$ is a uniform
distribution, the support of which is the hexagon $L$, and the elements in an
optimal set $\alpha_{n}$ of $n$-points are located in such a way so that the
overall distortion error is minimum. Hence, from the geometry of Figure 4,
without going into the details of calculations, we can assume that there
cannot be any element in the optimal set $\alpha_{n}$ lying on the lines $OA$,
or $OB$, i.e., on any line joining the center $O$ of the circle and any of the
vertices of the hexagon, i.e., the Voronoi regions of any element in
$\alpha_{n}\cap S_{i}$ contains elements only from $L_{i}$ with $P$-almost
surely, i.e., the Voronoi regions of any element in $\alpha_{n}\cap S_{i}$
does not contain any element from $L_{j}$ for $i\neq j$.

######  Methodology 5.3.

To obtain the conditional constrained optimal sets $\alpha_{n}$ of $n$-points
and the $n$th conditional constrained quantization error for the uniform
distribution $P$ on the hexagon with respect to the conditional set $\beta$
and the constraint $S$ for any $n\geq 7$, assume that
$\text{card}(\alpha_{n}\cap S_{1})=k$, i.e.,

$\alpha_{n}\cap S_{1}=\\{(r\cos\theta_{j},r\sin\theta_{j}):1\leq j\leq k\\}$

for $k\geq 1$. If $k=1$, then by Remark 5.2, we can assume that
$\alpha_{n}\cap S_{1}$ contains the midpoint of the side $L_{1}$. We assume
that $k\geq 2$. Let the elements in $\alpha_{n}\cap S_{1}$ be represented by
the parameters $\theta_{1}<\theta_{1}<\theta_{2}<\dots<\theta_{k}$, where
$\frac{4\pi}{3}<\theta_{1}<\cdots<\theta_{k}<\frac{5\pi}{3}$. Let the boundary
of the Voronoi regions of the element $A(-\frac{1}{2},-\frac{\sqrt{3}}{2})$
and $\theta_{1}$ intersect the side $L_{1}$ at the element
$(a_{1},-\frac{\sqrt{3}}{2})$, the boundary of the Voronoi regions of the
elements $\theta_{j}$ and $\theta_{j+1}$ intersect the side $L_{1}$ at the
element $(a_{j+1},-\frac{\sqrt{3}}{2})$, where $1\leq j\leq k-1$, and the
boundary of the Voronoi regions of the element $\theta_{k}$ and
$B(\frac{1}{2},-\frac{\sqrt{3}}{2})$ intersect the side $L_{1}$ at the element
$(a_{k+1},-\frac{\sqrt{3}}{2})$. Then, the canonical equations are given by

$\displaystyle\rho((-\frac{1}{2},-\frac{\sqrt{3}}{2}),(a_{1},-\frac{\sqrt{3}}{2}))-\rho((r\cos\theta_{1},r\sin\theta_{1}),(a_{1},-\frac{\sqrt{3}}{2}))=0,$
$\displaystyle\rho((r\cos\theta_{j},r\sin\theta_{j}),(a_{j+1},-\frac{\sqrt{3}}{2}))-\rho((r\cos\theta_{j+1},r\sin\theta_{j+1}),(a_{j+1},-\frac{\sqrt{3}}{2}))=0\text{
for }1\leq j\leq k-1,\text{ and }$
$\displaystyle\rho((\frac{1}{2},-\frac{\sqrt{3}}{2}),(a_{k+1},-\frac{\sqrt{3}}{2}))-\rho((r\cos\theta_{k},r\sin\theta_{k}),(a_{k+1},-\frac{\sqrt{3}}{2}))=0.$

Solving the canonical equations, we obtain the values of
$a_{1},a_{2},\cdots,a_{k+1}$ in terms of
$\theta_{1},\theta_{2},\cdots,\theta_{k}$ for $k\geq 2$. Hence, if
$V(P;\alpha_{n}\cap(S_{1}\cup L_{1}))$ is the distortion error contributed by
the elements in $\alpha_{n}\cap S_{1}$ on $L_{1}$, then we have

$\displaystyle V(P;\alpha_{n}\cap(S_{1}\cup L_{1}))$
$\displaystyle=\frac{1}{6}\Big{(}\int_{-\frac{1}{2}}^{a_{1}}\rho((x,-\frac{\sqrt{3}}{2}),(-\frac{1}{2},-\frac{\sqrt{3}}{2}))\,dx+\sum_{j=1}^{k}\int_{a_{j}}^{a_{j+1}}\rho((x,-\frac{\sqrt{3}}{2}),(\cos\theta_{j},\sin\theta_{j}))\,dx$
$\displaystyle\qquad+\int_{a_{k+1}}^{\frac{1}{2}}\rho((x,-\frac{\sqrt{3}}{2}),(\frac{1}{2},-\frac{\sqrt{3}}{2}))\,dx\Big{)}.$
(5)

Putting the values of $a_{j}$ we obtain the distortion error
$V(P;\alpha_{n}\cap(S_{1}\cup L_{1}))$, which is a function of $\theta_{j}$
for $1\leq j\leq k$. Now, using calculus, we obtain the values of $\theta_{j}$
for $1\leq j\leq k$ for which $V(P;\alpha_{n}\cap(S_{1}\cup L_{1}))$ is
minimum. Upon obtained the values of $\theta_{j}$, we can easily obtain
$\alpha_{n}\cap(S_{1}\cup L_{1})$ and the corresponding distortion error
$V(P;\alpha_{n}\cap(S_{1}\cup L_{1}))$. Due to the affine transformation, we
can also obtain $\alpha_{n}\cap(S_{i}\cup L_{i})$ and the corresponding
distortion error $V(P;\alpha_{n}\cap(S_{i}\cup L_{i}))$ for $2\leq i\leq 6$.
Thus, we have

$\alpha_{n}=\bigcup_{i=1}^{6}(\alpha_{n}\cap(S_{i}\cup L_{i}))\text{ with the
$n$th constrianed quantization error
}V_{n}=\sum_{i=1}^{6}V(P;\alpha_{n}\cap(S_{i}\cup L_{i})).$

∎

$A(-\frac{1}{2},-\frac{\sqrt{3}}{2})$$B(\frac{1}{2},-\frac{\sqrt{3}}{2})$$(\frac{1}{2},\frac{\sqrt{3}}{2})$$(-\frac{1}{2},\frac{\sqrt{3}}{2})$$(1,0)$$(-1,0)$$O$
Figure 4. The regular hexagon with a circle inscribed in it.

Using the above methodology, we obtain the results in the following examples.

######  Example 5.4.

Let $\alpha_{n}$ be a $n$th conditional constrained optimal set with the
conditional constrained quantization error $V_{n}$. Then, we obtain the
following results (see Figure 5):

$\displaystyle\alpha_{6}$ $\displaystyle=\beta\text{ with
}V_{6}=\frac{1}{12};$ $\displaystyle\alpha_{7}$
$\displaystyle=\beta\cup\\{(0,-\frac{\sqrt{3}}{2})\\}\text{ with
}V_{7}=V(P;\alpha_{n}\cap(S_{1}\cup
L_{1}))+\sum_{j=2}^{6}V(P;\alpha_{n}\cap(S_{j}\cup
L_{j}))=\frac{1}{288}+\frac{5}{72};$ $\displaystyle\alpha_{8}$
$\displaystyle=\beta\cup\\{(0,-\frac{\sqrt{3}}{2}),T(0,-\frac{\sqrt{3}}{2})\\}\text{
with }V_{8}=\frac{2}{288}+\frac{4}{72};$ $\displaystyle\alpha_{9}$
$\displaystyle=\beta\cup\\{(0,-\frac{\sqrt{3}}{2}),T(0,-\frac{\sqrt{3}}{2}),T^{2}(0,-\frac{\sqrt{3}}{2})\\}\text{
with }V_{9}=\frac{3}{288}+\frac{3}{72};$ $\displaystyle\alpha_{10}$
$\displaystyle=\beta\cup\\{(0,-\frac{\sqrt{3}}{2}),T(0,-\frac{\sqrt{3}}{2}),T^{2}(0,-\frac{\sqrt{3}}{2}),T^{3}(0,-\frac{\sqrt{3}}{2})\\}\text{
with }V_{10}=\frac{4}{288}+\frac{2}{72};$ $\displaystyle\alpha_{11}$
$\displaystyle=\beta\cup\\{(0,-\frac{\sqrt{3}}{2}),T(0,-\frac{\sqrt{3}}{2}),T^{2}(0,-\frac{\sqrt{3}}{2}),T^{3}(0,-\frac{\sqrt{3}}{2}),T^{4}(0,-\frac{\sqrt{3}}{2})\\}\text{
with }V_{11}=\frac{5}{288}+\frac{1}{72};$ $\displaystyle\alpha_{12}$
$\displaystyle=\beta\cup\\{(0,-\frac{\sqrt{3}}{2}),T(0,-\frac{\sqrt{3}}{2}),T^{2}(0,-\frac{\sqrt{3}}{2}),T^{3}(0,-\frac{\sqrt{3}}{2}),T^{4}(0,-\frac{\sqrt{3}}{2}),T^{5}(0,-\frac{\sqrt{3}}{2})\\}\text{
with }V_{12}=\frac{6}{288}.$

Figure 5. In conditional constrained quantization with the constraint as the
incircle the dots represent the elements in an optimal set of $n$-points for
$6\leq n\leq 13$.

######  Example 5.5.

To obtain the optimal set $\alpha_{13}$ and the corresponding conditional
constrained quantization error $V_{13}$, we proceed as follows (see Figure 5):
By Lemma 5.1, we can assume that $\text{card}(\alpha_{13}\cap(S_{1}\cup
L_{1}))=4$ and $\text{card}(\alpha_{n}\cap(S_{i}\cup L_{i}))=3$ for $2\leq
i\leq 6$. Then, using Methodology 5.3, we obtain

$\alpha_{13}\cap(S_{1}\cup
L_{1})=\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(-0.162514,-0.85064),(0.162514,-0.85064),(\frac{1}{2},-\frac{\sqrt{3}}{2})\\}$

and $V(P;\alpha_{13}\cap(S_{1}\cup L_{1}))=0.00157076.$ Moreover, we have

$\alpha_{13}\cap(S_{i}\cup
L_{i})=T^{i}(\\{(-\frac{1}{2},-\frac{\sqrt{3}}{2}),(0,-\frac{\sqrt{3}}{2}),(\frac{1}{2},-\frac{\sqrt{3}}{2})\\})$

with $V(\alpha_{13}\cap(S_{i}\cup L_{i}))=\frac{1}{288}\text{ for }2\leq j\leq
6.$ Hence,

$\displaystyle\alpha_{13}$
$\displaystyle=\bigcup_{i=1}^{6}\alpha_{13}\cap(S_{i}\cup
L_{i})=\beta\bigcup\\{(-0.162514,-0.85064),(0.162514,-0.85064)\\}\bigcup\bigcup_{i=2}^{6}\\{T^{i}(0,-\frac{\sqrt{3}}{2})\\}\text{
with }$ $\displaystyle V_{13}$ $\displaystyle=V(P;\alpha_{13}\cap(S_{1}\cup
L_{1}))+\sum_{i=2}^{6}V(P;\alpha_{13}\cap(S_{i}\cup
L_{i}))=0.00157076+\frac{5}{288}=0.0189319.$

##  6\. Conditional constrained quantization for the uniform distribution $P$
when the constraint is a diagonal of the hexagon

Notice that the hexagon has nine diagonals: six of the diagonals are of equal
lengths, and we call them as the diagonals of the smaller length; the
remaining three diagonals are of equal lengths, we call them as the diagonals
of the larger length. Let $d$ represent any of the nine diagonals of the
hexagon. By $\text{Int}(d)$, it is meant the interior of the diagonal $d$.
$\beta$ is the conditional set. Then, notice that $\beta\cap d\neq\emptyset$
with $\text{card}(\beta\cap d)=2$, and $\beta\cap\text{Int}(d)=\emptyset$.
Hence, we can assume that in a conditional constrained optimal set
$\alpha_{n}$ of $n$-points with the constraint a diagonal $d$, the set
$\alpha_{n}\setminus\beta$ will contain $n-6$ elements from the
$\text{Int}(d)$, i.e., $\text{card}(\alpha_{n}\cap\text{Int}(d))=n-6$. In the
following two subsections, we give the main results in this section.

###  6.1. When the constraint is a diagonal of the larger length

As depicted in Figure 1, there are three diagonals of the larger length. We
now give the following lemma.

######  Lemma 6.1.1.

There does not exist any conditional constrained optimal set of $n$-points for
any $n\geq 7$, containing exactly $n$ elements, under the conditional set
$\beta$ and the constraint as any of the diagonals of the larger length.

###### Proof.

Without any loss of generality we can choose the diagonal $AD$ of the larger
length as the constraint. For the sake of contradiction, assume that
$\alpha_{n}$ is a conditional constrained optimal set of $n$-points for some
$n\geq 7$, containing exactly $n$ elements, with the conditional set $\beta$
and the constraint as the diagonal $AD$. For any $(x,y)\in L_{2}\cup L_{5}$,
we see that

$\min_{a\in\alpha_{n}\cap AD}\rho((x,y),a)>\min_{a\in\beta}\rho((x,y),a),$

i.e., the Voronoi region of any element in $\alpha_{n}\cap AD$ does not
contain any element from $L_{2}\cup L_{5}$. We now consider the side $L_{6}$.
Notice that $L_{6}$ is given by

$L_{6}=\\{(\frac{t-2}{2},-\frac{\sqrt{3}t}{2}):0\leq t\leq 1\\}.$

The equation of the diagonal $AD$ is $y=\sqrt{3}x$. If
$(x,y)=(\frac{t-2}{2},-\frac{\sqrt{3}t}{2})\in L_{6}$ for $0\leq t\leq
2\sqrt{3}-3$, we see that

$\min_{a\in\alpha_{n}}\rho((x,y),a)=\rho((x,y),(-1,0)),$

i.e., the Voronoi region of any element in $\alpha_{n}\cap AD$ does not
contain any element from $L_{6}$ for $0\leq t\leq 2\sqrt{3}-3$. Next, assume
that $2\sqrt{3}-3<t\leq 1$. Then, for $(x,y)\in L_{6}$, we have

$\min_{a\in\alpha_{n}\cap
AD}\rho((x,y),a)\leq\rho((x,y),(-\frac{1}{2},-\frac{\sqrt{3}}{2}))=\min_{a\in\beta}\rho((x,y),a),$

noticing the fact that the equality holds only if $t=1$. This implies the fact
that $P$-almost surely, the Voronoi region of the element
$(-\frac{1}{2},-\frac{\sqrt{3}}{2})\in\alpha_{n}$ does not contain any element
from $L_{6}$. Due to symmetry, we can say that the Voronoi region of the
element $(-\frac{1}{2},-\frac{\sqrt{3}}{2})\in\alpha_{n}$ also does not
contain any element from $L_{1}$, $P$-almost surely. This yields the fact that
though $(-\frac{1}{2},-\frac{\sqrt{3}}{2})\in\beta$, we have
$P(M((-\frac{1}{2},-\frac{\sqrt{3}}{2})|\alpha_{n}))=0$, which violates the
definition of the conditional optimal set of $n$-points. Thus, we see that a
contradiction arises under the assumption that $\alpha_{n}$ is a conditional
constrained optimal set of $n$-points for some $n\geq 7$, containing exactly
$n$ elements, with the conditional set $\beta$ and the constraint as the
diagonal $AD$. Hence, there is no conditional constrained optimal set of
$n$-points for any $n\geq 7$, containing exactly $n$ elements, with the
conditional set $\beta$ and the constraint as the diagonal $AD$. ∎

The following proposition gives the main result in this subsection.

######  Proposition 6.1.2.

The conditional set $\beta$ is the only conditional constrained optimal set of
$n$-points for any $n\geq 6$ with the conditional constrained quantization
error $V_{6}=\frac{1}{12}.$

###### Proof.

As a consequence of Lemma 6.1.1, we can say that $\beta$ is the only
conditional constrained optimal set of $n$-points for any $n\geq 6$. Due to
symmetry, the conditional constrained quantization error $V_{6}$ is obtained
as

$\displaystyle
V_{6}=6\int_{L_{1}}\min_{a\in\beta}\rho(x,a)\,dP(x)=2\int_{0}^{\frac{1}{2}}\rho((t-\frac{1}{2},-\frac{\sqrt{3}}{2}),(-\frac{1}{2},-\frac{\sqrt{3}}{2}))\,dx=\frac{1}{12}.$

∎

###  6.2. When the constraint is a diagonal of the smaller length

As can be seen from Figure 1, there are six diagonals of the smaller length.
Without any loss of generality we can choose the diagonal $FD$ of the smaller
length as the constraint. The conditional optimal set of six-points is the
conditional set $\beta$.

######  Lemma 6.2.1.

Let $\alpha_{n}$ be a conditional constrained optimal set of $n$-points for
any $n\geq 7$. Then, $\alpha_{n}\cap\text{Int}(FD)$ does not contain any
element from $L_{1}\cup L_{2}\cup L_{3}\cup L_{6}$.

###### Proof.

Let $\alpha_{n}$ be a conditional constrained optimal set of $n$-points for
some $n\geq 7$. Then, $\text{card}(\alpha_{n}\cap\text{Int}(FD))\geq 1$.
Notice that for any $(x,y)\in L_{3}$, we have

$\min_{a\in\alpha_{n}}\rho((x,y),a)=\rho((x,y),(\frac{1}{2},\frac{\sqrt{3}}{2})),$

i.e., the Voronoi region of any element in $\alpha_{n}\cap\text{Int}(FD)$ does
not contain any element from $L_{3}$. Due to symmetry, the Voronoi region of
any element in $\alpha_{n}\cap\text{Int}(FD)$ also does not contain any
element from $L_{6}$. Again, notice that for any $(x,y)\in L_{1}\cup L_{2}$

$\min_{a\in\alpha_{n}\cap FD}\rho((x,y),a)>\min_{a\in\beta}\rho((x,y),a),$

i.e., the Voronoi region of any element in $\alpha_{n}\cap\text{Int}(FD)$ does
not contain any element from $L_{1}\cup L_{2}$. Thus, the proof of the lemma
is complete. ∎

######  Lemma 6.2.2.

For any $n\geq 6$, a conditional constrained optimal set of $n$-points
contains exactly $n$-elements.

###### Proof.

$\beta$ is a conditional constrained optimal set of six-points which contains
exactly six elements. Let $\alpha_{n}$ be a conditional constrained optimal
set of $n$-points for any $n\geq 7$. We now show that
$\alpha_{n}\cap\text{Int}(FD)$ is nonempty and contains exactly $n-6$
elements. The equation of the diagonal $FD$ is $y=\frac{1}{\sqrt{3}}(x+1)$.
The side $L_{5}$ is given by

$L_{5}=\\{(\frac{1}{2}(-t-1),-\frac{1}{2}\sqrt{3}(t-1)):0\leq t\leq 1\\}.$

Let $(x,y)=(\frac{1}{2}(-t-1),-\frac{1}{2}\sqrt{3}(t-1))\in L_{5}$. If $0\leq
t<\frac{1}{3}$, then we see that

$\min_{a\in\alpha_{n}\cap
FD}\rho((x,y),a)>\rho((x,y),(-\frac{1}{2},\frac{\sqrt{3}}{2})),$

and

$\min_{a\in\alpha_{n}\cap
FD}\rho((x,y),a)=\rho((x,y),(-\frac{1}{2},\frac{\sqrt{3}}{2}))\text{ if
}t=\frac{1}{3},$

i.e., $P$-almost surely, the Voronoi region of any element in
$\alpha_{n}\cap\text{Int}(FD)$ does not contain any element from $L_{5}$ for
$0\leq t\leq\frac{1}{3}$. Next, assume that $\frac{1}{3}<t<1$. Then, for
$(x,y)\in L_{5}$, we have

$\min_{a\in\alpha_{n}\cap
FD}\rho((x,y),a)<\rho((x,y),(-1,0))=\min_{a\in\beta}\rho((x,y),a).$

For $t=1$, we have

$\min_{a\in\alpha_{n}\cap
FD}\rho((x,y),a)=\rho((x,y),(-1,0))=\min_{a\in\beta}\rho((x,y),a).$

Hence, the possible elements in $L_{5}$ that can fall within the Voronoi
regions of the elements in $\alpha_{n}\cap\text{Int}(FD)$ are for
$\frac{1}{3}<t<1$. Similarly, the possible elements in $L_{4}$ that can fall
within the Voronoi regions of the elements in $\alpha_{n}\cap\text{Int}(FD)$
are for $0<t<\frac{2}{3}$. Thus, for each $a\in\alpha_{n}\cap\text{Int}(FD)$,
we have

$P(M(a|\alpha_{n}\cap\text{Int}(FD)))>0.$

Hence, we can conclude that $\alpha_{n}\cap\text{Int}(FD)$ is nonempty and
contains exactly $n-6$ elements. Thus, the proof of the lemma is complete. ∎

######  Remark 6.2.3.

In the proof of Lemma 6.2.2, it is mentioned that $P$-almost surely, the
Voronoi region of any element in $\alpha_{n}\cap\text{Int}(FD)$ does not
contain any element from $L_{5}$ for $0\leq t\leq\frac{1}{3}$. Similarly,
$P$-almost surely, the Voronoi region of any element in
$\alpha_{n}\cap\text{Int}(FD)$ does not contain any element from $L_{4}$ for
$\frac{2}{3}\leq t\leq 1$. Putting $t=\frac{1}{3}$ in the representation of
$L_{5}$, we obtain the element as $(-\frac{2}{3},\frac{1}{\sqrt{3}})$. Putting
$t=\frac{2}{3}$ in the representation of $L_{4}$, we obtain the element as
$(-\frac{1}{6},\frac{\sqrt{3}}{2})$. Let $(u,v)$ and $(w,x)$ be the bases of
the perpendiculars from $(-\frac{2}{3},\frac{1}{\sqrt{3}})$ and
$(-\frac{1}{6},\frac{\sqrt{3}}{2})$ on the diagonal $FD$. Then, we have

$(u,v)=(-\frac{1}{2},\frac{1}{2\sqrt{3}})\text{ and
}(w,x)=(0,\frac{1}{\sqrt{3}}).$

Also, notice that

$\alpha_{n}\cap
FD=(\alpha_{n}\cap\text{Int}(FD))\cup\\{(-1,0),(\frac{1}{2},\frac{\sqrt{3}}{2})\\},$
$\alpha_{n}\cap FD\subseteq\\{(x,y)\in FD:-1\leq
x\leq-\frac{1}{2}\\}\cup\\{(x,y)\in FD:0\leq x\leq\frac{1}{2}\\}.$ (6)

######  Remark 6.2.4.

By the expression in (6), we can conclude that for any $a\in\alpha_{n}\cap
FD$, if the Voronoi region of the element $a$ includes elements from $L_{5}$,
then it will not include any element from $L_{4}$. We denote such elements in
$\alpha_{n}\cap FD$ by $(\alpha_{n}\cap FD)^{(1)}$. Similarly, for any
$a\in\alpha_{n}\cap FD$, if the Voronoi region of the element $a$ includes
elements from $L_{4}$, then it will not include any element from $L_{5}$. We
denote such elements in $\alpha_{n}\cap FD$ by $(\alpha_{n}\cap FD)^{(2)}$.
Notice that

$\alpha_{n}\cap FD=(\alpha_{n}\cap FD)^{(1)}\bigcup(\alpha_{n}\cap
FD)^{(2)},\text{ and }(\alpha_{n}\cap FD)^{(1)}\bigcap(\alpha_{n}\cap
FD)^{(2)}=\emptyset.$

Let us now state the following lemma. The proof is similar to Lemma 3.2, in
fact, $P$ being a uniform distribution, and the two sides $L_{4}$ and $L_{5}$
are symmetrically located with respect to the perpendicular bisector of the
segment $FD$, it is not difficult to show the proof.

######  Lemma 6.2.5.

For $n\geq 7$, let $(\alpha_{n}\cap FD)^{(1)}$ and $(\alpha_{n}\cap FD)^{(2)}$
be two sets as defined before. Let $\text{card}((\alpha_{n}\cap
FD)^{(1)}))=n_{1}$ and $\text{card}((\alpha_{n}\cap FD)^{(2)}))=n_{2}$. Then,
$n_{1},n_{2}\geq 1$ with $|n_{1}-n_{2}|=0,\text{ or }1$.

### Affine transformation

Consider the affine transformation $T:\mathbb{R}^{2}\to\mathbb{R}^{2}$ such
that

$T(x,y)=(\frac{\sqrt{3}}{2}x+\frac{y}{2},-\frac{x}{2}+\frac{\sqrt{3}}{2}y-\frac{1}{2}).$

Since $T$ is a bijective function, its inverse transformation is given by

$T^{-1}(x,y):\mathbb{R}^{2}\to\mathbb{R}^{2}\text{ such that
}T^{-1}(x,y)=(\frac{\sqrt{3}}{2}x-\frac{y}{2}-\frac{1}{4},\frac{x}{2}+\frac{\sqrt{3}}{2}y+\frac{\sqrt{3}}{4}).$

Let us now consider a triangle $\triangle GHI$ with vertices
$G(-\frac{\sqrt{3}}{2},0)$, $H(\frac{\sqrt{3}}{2},0)$, and $I(0,\frac{1}{2})$.
Notice that
$T(-1,0)=(-\frac{\sqrt{3}}{2},0),\,T(\frac{1}{2},\frac{\sqrt{3}}{2})=(\frac{\sqrt{3}}{2},0)$,
and $T(-\frac{1}{2},\frac{\sqrt{3}}{2})=(0,\frac{1}{2})$. Hence, we have

$T(\triangle FDE)=\triangle GHI\text{ and }T^{-1}(\triangle GHI)=\triangle
FDE.$ (7)

######  Note 6.2.6.

To calculate the conditional constrained optimal sets of $n$-points for any
$n\geq 7$, for the uniform distribution $P$, we will compare $\triangle FDE$
with $\triangle GHI$ as given by (7). Consequently, $(\alpha_{n}\cap
FD)^{(1)}$ and $(\alpha_{n}\cap FD)^{(2)}$ will be compared, respectively,
with $(T(\alpha_{n})\cap GH)^{(1)}$ and $(T(\alpha_{n})\cap GH)^{(2)}$. Thus,
by Lemma 6.2.5, we see that if $\text{card}((T(\alpha_{n})\cap
GH)^{(1)})=n_{1}$ and $\text{card}((T(\alpha_{n})\cap GH)^{(2)})=n_{2}$, then
$n_{1},n_{2}\geq 1$ with $|n_{1}-n_{2}|=0,\text{ or }1$. Moreover, notice that
after the affine transformation, the expression given by (6), reduces to

$T(\alpha_{n})\cap GH\subseteq\\{(x,y)\in GH:-\frac{\sqrt{3}}{2}\leq
x\leq-\frac{1}{2\sqrt{3}}\\}\cup\\{(x,y)\in GH:\frac{1}{2\sqrt{3}}\leq
x\leq\frac{\sqrt{3}}{2}\\}.$ (8)

From the expression (8), we see that the Voronoi region of any element in
$\\{(x,y)\in GH:-\frac{\sqrt{3}}{2}\leq x\leq-\frac{1}{2\sqrt{3}}\\}$ does not
contain any element from the Voronoi region of any element in $\\{(x,y)\in
GH:\frac{1}{2\sqrt{3}}\leq x\leq\frac{\sqrt{3}}{2}\\}$, and vice versa. Let
$Q$ be the normalized image measure of $P$ under the affine transformation
$T$, i.e., $Q=3T(P)$ such that for any Borel subset
$A\subseteq\mathbb{R}^{2}$, we have $Q(A)=3P(T^{-1}(A))$. Thus, $Q$ can be
considered as a Borel probability measure on $\mathbb{R}^{2}$ which is uniform
on its support $GI\cup HI$. The parametric representations of the sides $GI$,
$HI$ and $GH$ are given as follows:

$\displaystyle GI$
$\displaystyle=\\{(-\frac{\sqrt{3}t}{2},\frac{1-t}{2}):0\leq t\leq 1\\},$
$\displaystyle HI$
$\displaystyle=\\{(\frac{\sqrt{3}(1-t)}{2},\frac{t}{2}):0\leq t\leq
1\\},\text{ and }$ $\displaystyle GH$
$\displaystyle=\\{(t,0):-\frac{\sqrt{3}}{2}\leq t\leq\frac{\sqrt{3}}{2}\\}.$

Let $s$ represent the distance of any point on $\triangle GHI$ starting from
the vertex $G$ tracing along the boundary of the triangle in the
counterclockwise direction. Then, the points $G,H,I$ are, respectively,
represented by $s=0,s=1,s=2$. The probability density function (pdf) $g$ of
the uniform distribution $Q$ is given by $g(s):=g(x,y)=\frac{1}{2}$ for all
$(x,y)\in GI\cup HI$, and zero otherwise. Again,
$dQ(s)=Q(ds)=g(x_{1},x_{2})ds$. Notice that on each of $GI$ and $HI$, we have
$ds=\sqrt{(dx)^{2}+(dy)^{2}}=dt$. For $n\geq 6$, to obtain a conditional
constrained optimal set $\alpha_{n}$ of $n$-points for the uniform
distribution $P$ under the conditional set $\beta$ and the constraint $FD$, we
will first calculate a conditional constrained optimal set $\gamma_{n-3}$ of
$(n-3)$-points for the uniform distribution $Q$ under the conditional set
$\hat{\beta}:=\\{(-\frac{\sqrt{3}}{2},0),(\frac{\sqrt{3}}{2},0),(0,\frac{1}{2})\\}$
and the constraint $GH$, and then will obtain them for the uniform
distribution $P$ as described in Methodology 6.2.13 given below. ∎

######  Notation 6.2.7.

Let $\alpha$ be a discrete set. Then, for a Borel probability measure $\mu$
and a set $A$, by $V(\mu;\\{\alpha,A\\})$, it is meant the distortion error
for $\mu$ with respect to the set $\alpha$ over the set $A$, i.e.,

$V(\mu;\\{\alpha,A\\}):=\int_{A}\mathop{\min}\limits_{a\in\alpha}d(x,a)^{2}\,d\mu(x).$
(9)

Denote the sets $\\{(x,y)\in GH:-\frac{\sqrt{3}}{2}\leq
x\leq-\frac{1}{2\sqrt{3}}\\}$ and $\\{(x,y)\in GH:\frac{\sqrt{3}}{2}\leq
x\leq\frac{1}{2\sqrt{3}}\\}$, metioned in Note 6.2.6, respectively, by
$GH^{(1)}$ and $GH^{(2)}$.

Let us now give the following proposition.

######  Lemma 6.2.8.

For $n\geq 6$, let $\gamma_{n-3}$ be a conditional constrained optimal set of
$(n-3)$-points for the uniform distribution $Q$ under the conditional set
$\hat{\beta}$ and the constraint $GH$. Then, the conditional constrained
optimal set $\alpha_{n}$ of $n$-points for the uniform distribution $P$ under
the conditional set $\beta$ and the constraint $FD$ is given by

$\alpha_{n}=T^{-1}(\gamma_{n-3})\cup\beta.$

The conditional constrained quantization error is given by

$V_{n}(P)=\frac{1}{3}V_{n-3}(Q)+\frac{1}{18}.$

###### Proof.

The proof that $\alpha_{n}=T^{-1}(\gamma_{n-3})\cup\beta$ follows from the
definition of the affine transformation. We now prove the expression for
quantization error. Let $\gamma_{n-3}$ be a conditional constrained optimal
set of $(n-3)$-points for the uniform distribution $Q$. Then,

$\displaystyle V_{n-3}(Q)$ $\displaystyle=\int_{GI\cup
HI}\min_{a\in\gamma_{n-3}}\rho((x,y),a)\,dQ(x)=3\int_{GI\cup
HI}\min_{a\in\gamma_{n-3}}\rho((x,y),a)\,d(TP)(x)$ $\displaystyle=\int_{GI\cup
HI}\min_{a\in\gamma_{n-3}}\rho((x,y),a)\,d(P\circ
T^{-1})(x)=3\int_{T^{-1}(GI\cup
HI)}\min_{a\in\gamma_{n-3}}\rho(T(x,y),a)\,dP(x)$
$\displaystyle=3\int_{L_{4}\cup L_{5}}\min_{a\in
T^{-1}(\gamma_{n-3})}\rho(T(x,y),T(a))\,dP(x)=3\int_{L_{4}\cup
L_{5}}\min_{a\in T^{-1}(\gamma_{n-3})}\rho((x,y),a)\,dP(x)$
$\displaystyle=3V(P;\\{T^{-1}(\gamma_{n-3}),L_{4}\cup L_{5}\\}).$

Due to symmetry, we have

$\displaystyle V(P;\\{\beta,L_{1}\cup L_{2}\cup L_{3}\cup
L_{6}\\})=4\int_{L_{1}}\min_{a\in\beta}\rho((x,y),a)\,dP$
$\displaystyle=\frac{8}{6}\int_{0}^{\frac{1}{2}}\rho((t-\frac{1}{2},-\frac{\sqrt{3}}{2}),(-\frac{1}{2},-\frac{\sqrt{3}}{2}))\,dt=\frac{1}{18}.$

Thus, we obtain

$V_{n}(P)=V(P;\\{T^{-1}(\gamma_{n-3}),L_{4}\cup
L_{5}\\})+V(P;\\{\beta,L_{1}\cup L_{2}\cup L_{3}\cup
L_{6}\\})=\frac{1}{3}V_{n-3}(Q)+\frac{1}{18}.$

Thus, the lemma is yielded. ∎

######  Remark 6.2.9.

Due to (8), we see that if $\gamma_{n}$ is a conditional constrained optimal
set of $n$-points for the uniform distribution $Q$ under the constraint
$GI\cup HI$ and the conditional set $\hat{\beta}$, and $n=2m+1$ for some
$m\in\mathbb{N}$, then $V(Q,\\{\gamma_{n},GI\\})=V(Q,\\{\gamma_{n},HI\\})$ and
hence,

$V_{n}(Q)=2V(Q,\\{\gamma_{n},GI\\}).$

######  Lemma 6.2.10.

The conditional constrained optimal set of four-points for $Q$ is given by
$\gamma_{4}=\hat{\beta}\cup\\{(-\frac{1}{2},0)\\}$ with conditional
constrained quantization error
$V_{4}(Q)=\frac{1}{24}\left(5-2\sqrt{3}\right)$.

###### Proof.

Let $\gamma_{4}:=\hat{\beta}\cup\\{(a,0)\\}$ be a conditional constrained
optimal set of four-points for some
$-\frac{\sqrt{3}}{2}<a<-\frac{1}{2\sqrt{3}}$. Let the boundary of the Voronoi
regions of $(-\frac{\sqrt{3}}{2},0)$ and $(a,0)$ intersect $GH$ at a point
given by the parameter $t=d_{1}$, and let the boundary of the Voronoi regions
of $(a,0)$ and $I(0,\frac{1}{2})$ intersect $GI$ at a point given by the
parameter $t=d_{2}$. Then, notice that $0<d_{2}<d_{1}<1$. Solving the
canonical equations

$\displaystyle\rho((-\frac{\sqrt{3}d_{1}}{2},\frac{1-d_{1}}{2}),(-\frac{\sqrt{3}}{2},0))$
$\displaystyle=\rho((-\frac{\sqrt{3}d_{1}}{2},\frac{1-d_{1}}{2}),(a,0))\text{
and }$ $\displaystyle\rho((-\frac{\sqrt{3}d_{2}}{2},\frac{1-d_{2}}{2}),(a,0))$
$\displaystyle=\rho((-\frac{\sqrt{3}d_{2}}{2},\frac{1-d_{2}}{2}),(0,\frac{1}{2})$

we have

$d_{1}=-\frac{-\frac{\sqrt{3}}{2}+a}{\sqrt{3}}\text{ and
}d_{2}=\frac{4a^{2}+1}{2-4\sqrt{3}a}.$

Now, calculate the distortion error

$\displaystyle V(Q;\\{\gamma_{4},GI\\})$
$\displaystyle=\frac{1}{2}\Big{(}\int_{d_{1}}^{1}\rho((-\frac{\sqrt{3}t}{2},\frac{1-t}{2}),(-\frac{\sqrt{3}}{2},0))\,dt+\int_{d_{2}}^{d_{1}}\rho((-\frac{\sqrt{3}t}{2},\frac{1-t}{2}),(a,0))\,dt$
$\displaystyle\qquad+\int_{0}^{d_{2}}\rho((-\frac{\sqrt{3}t}{2},\frac{1-t}{2}),(0,\frac{1}{2}))\,dt+\Big{)}$
$\displaystyle=\frac{96\sqrt{3}a^{5}+48a^{4}-16\sqrt{3}a^{3}-24a^{2}+6\sqrt{3}a-1}{24\left(2\sqrt{3}a-1\right)^{3}}.$

which is minimum if $a=-\frac{1}{2}$ and then
$V(Q;\\{\gamma_{4},GI\\})=\frac{1}{12}\left(2-\sqrt{3}\right)$. Hence,
$\gamma_{4}=\hat{\beta}\cup\\{(-\frac{1}{2},0)\\}$, and $V_{4}(Q)$ is given by

$V_{4}(Q)=V(Q;\\{\gamma_{4},GI\\})+V(Q;\\{\gamma_{4},HI\\})=V(Q;\\{\gamma_{4},GI\\})+\frac{1}{24}=\frac{1}{24}\left(5-2\sqrt{3}\right)=0.0639958.$

Thus, the lemma is yielded. ∎

######  Remark 6.2.11.

Due to Remark 6.2.9, the conditional constrained optimal set of five-points
for $Q$ is given by
$\gamma_{5}=\hat{\beta}\cup\\{(-\frac{1}{2},0),(\frac{1}{2},0)\\}$ with
conditional constrained quantization error
$V_{5}(Q)=2V(Q;\\{\gamma_{5},GI\\})=\frac{1}{6}\left(2-\sqrt{3}\right).$

######  Proposition 6.2.12.

Let $\alpha_{n}$ be a conditional constrained optimal sets of $n$-points for
$P$ with quantization error $V_{n}$. Then,

$\displaystyle\alpha_{7}$
$\displaystyle=\beta\cup\Big{\\{}\Big{(}\frac{1}{4}(-\sqrt{3}-1),\frac{1}{4}(\sqrt{3}-1)\Big{)}\Big{\\}}\text{
with }V_{7}=\frac{1}{72}\left(9-2\sqrt{3}\right)$ $\displaystyle\alpha_{8}$
$\displaystyle=\beta\cup\Big{\\{}\Big{(}\frac{1}{4}(-\sqrt{3}-1),\frac{1}{4}(\sqrt{3}-1)\Big{)},\Big{(}\frac{1}{4}(\sqrt{3}-1),\frac{1}{4}(\sqrt{3}+1)\Big{)}\Big{\\}}\text{
with }V_{8}=\frac{1}{18}(3-\sqrt{3}).$

###### Proof.

The proof follows by Lemma 6.2.8, Lemma 6.2.10, and Remark 6.2.11 (see Figure
6). ∎

We now give a methodology to obtain the conditional constrained optimal sets
of $n$-points for the uniform distribution $Q$ for any $n\geq 6$.

######  Methodology 6.2.13.

For $n\geq 6$, let $\gamma_{n}$ be a conditional constrained optimal set of
$n$-points such that $\text{card}(\gamma_{n}\cap GH^{(1)})=n_{1}$ and
$\text{card}(\gamma_{n}\cap GH^{(2)})=n_{2}$. Then, we know that
$|n_{1}-n_{2}|=0,\text{ or }1$. Also, $n=n_{1}+n_{2}+1$. If $n=6$, without any
loss of generality, we can assume that $n_{1}=3$ and $n_{2}=2$. If $n\geq 7$,
then always $n_{1},n_{2}\geq 3$. To calculate $\gamma_{n}\cap GH^{(1)}$ we
proceed as follows. Let

$\displaystyle\gamma_{n}\cap GH^{(1)}$ $\displaystyle=\\{(a(j),0):1\leq j\leq
n_{1}\\}\text{ with }a(i)<a(j)\text{ for }1\leq i<j\leq n_{1},$

where $a(1)=-\frac{\sqrt{3}}{2}$. For $1\leq j<n_{1}-1$, let the boundary of
the Voronoi regions of $(a(j),0)$ and $(a(j+1),0)$ intersect the side $GI$ at
a point represented by the parameter $t=d(j)$. For $1\leq j\leq n_{1}-1$
solving the canonical equations

$\rho((-\frac{\sqrt{3}d(j)}{2},\frac{1-d(j)}{2}),(a(j),0))=\rho((-\frac{\sqrt{3}d(j)}{2},\frac{1-d(j)}{2}),(a(j+1),0)),$

we have $d(j)=-\frac{a(j)+a(j+1)}{\sqrt{3}}$. Let the boundary of the Voronoi
regions of $(a(n_{1}),0)$ and $(0,\frac{1}{2})$ intersect the side $GI$ at a
point represented by the parameter $t=d(n_{1})$. Then, solving the canonical
equation

$\rho((-\frac{\sqrt{3}d(n_{1})}{2},\frac{1-d(n_{1})}{2}),(a(n_{1}),0))=\rho((-\frac{\sqrt{3}d(n_{1})}{2},\frac{1-d(n_{1})}{2}),(0,\frac{1}{2})),$

we have $d(n_{1})=\frac{4a(n_{1})^{2}+1}{2-4\sqrt{3}a(n_{1})}$. We now
calculate the distortion error $V(Q;\\{\gamma_{n},GI\\})$ as follows:

$\displaystyle
V(Q;\\{\gamma_{n},GI\\})=\frac{1}{2}\Big{(}\int_{d(1)}^{1}\rho((-\frac{\sqrt{3}t}{2},\frac{1-t}{2}),(a(1),0))\,dt$
$\displaystyle=\sum_{j=2}^{n_{1}-1}\int_{d(j)}^{d(j-1)}\rho((-\frac{\sqrt{3}t}{2},\frac{1-t}{2}),(a(j),0))\,dt+\int_{d(n_{1})}^{d(n_{1}-1)}\rho((-\frac{\sqrt{3}t}{2},\frac{1-t}{2}),(a(n_{1}),0))\,dt$
$\displaystyle\qquad+\int_{0}^{d(n_{1})}\rho((-\frac{\sqrt{3}t}{2},\frac{1-t}{2}),(0,\frac{1}{2}))\,dt\Big{)}.$
(10)

Recall that $a(1)=-\frac{\sqrt{3}}{2}$. After putting the corresponding values
of $d(j)$ for $1\leq j\leq n_{1}$, and then upon simplification, we obtain
$V(Q;\\{\gamma_{n},GI\\})$ as a function of $a(j)$ for $2\leq j\leq n_{1}$.
Then, after solving the partial derivatives

$\frac{\partial}{\partial a(j)}(V(Q;\\{\gamma_{n},GI\\})=0$ (11)

we obtain the values of $a(j)$ for $2\leq j\leq n_{1}$ for which
$V(Q;\\{\gamma_{n},GI\\})$ is minimum. Thus, $\gamma_{n}\cap GH^{(1)}$ and the
corresponding distortion error $V(Q;\\{\gamma_{n},GI\\})$ are obtained for
$n_{1}\geq 3$. If $n_{2}=2$, then by Lemma 6.2.10, we have $\gamma_{n}\cap
GH^{(2)}=\\{(\frac{1}{2},0),(\frac{\sqrt{3}}{2},0)\\}$. If $n_{2}\geq 3$, we
replace $n_{1}$ by $n_{2}$ in the above procedure, and obtain the set
$\gamma_{n}\cap GH^{(1)}$ for $\text{card}(\gamma_{n}\cap GH^{(1)})=n_{2}$,
and then reflect it with respect to the $y$-axis to obtain the set
$\gamma_{n}\cap GH^{(2)}$ with $\text{card}(\gamma_{n}\cap GH^{(2)})=n_{2}$.
Likewise, we obtain the distortion error $V(Q;\\{\gamma_{n},HI\\})$ as
$V(Q;\\{\gamma_{n},HI\\})=V(Q;\\{\gamma_{n},GI\\})$ with
$\text{card}(\gamma_{n}\cap GH^{(1)})=\text{card}(\gamma_{n}\cap
GH^{(2)})=n_{2}$. ∎

Using Methodology 6.2.13, we obtain the following examples.

######  Example 6.2.14.

To obtain $\gamma_{6}(Q)$ and the corresponding constrained quantization error
$V_{6}(Q)$ for the uniform distribution $Q$, we proceed as follows. Let $n=6$
and choose $n_{1}=3$ and $n_{2}=2$. Putting $n_{1}=3$ in Expression (6.2.13)
and then upon simplification, we have

$\displaystyle V(Q;\\{\gamma_{6},GI\\})$
$\displaystyle=\frac{1}{48(2\sqrt{3}a(3)-1)^{3}}\Big{(}-2+15\sqrt{3}a(3)-96a(3)^{2}+40\sqrt{3}a(3)^{3}+96a(3)^{4}+48\sqrt{3}a(3)^{5}$
$\displaystyle+a(2)\Big{(}4a(3)^{2}-3\Big{)}\Big{(}-72a(3)^{3}+36\sqrt{3}a(3)^{2}-18a(3)+\sqrt{3}\Big{)}$
$\displaystyle+2a(2)^{2}\Big{(}144a(3)^{4}-72a(3)^{2}+16\sqrt{3}a(3)-3\Big{)}\Big{)}.$

Now, solving the partial derivatives $\frac{\partial}{\partial
a(j)}(V(Q;\\{\gamma_{n},GI\\})=0$ for $j=2,3$, we have $a(2)=-0.639488$ and
$a(3)=-0.41295$. Thus, we have

$\gamma_{6}\cap
GH^{(1)}=\\{(-\frac{\sqrt{3}}{2},0),(-0.639488,0),(-0.41295,0)\\}\text{ with
}V(Q;\\{\gamma_{6},GI\\})=0.0199575.$ (12)

Moreover, as $n_{2}=2$, using the properties of reflection by Lemma 6.2.10 as
mentioned in Methodology 6.2.13, we have

$\gamma_{6}\cap GH^{(2)}=\\{(\frac{1}{2},0),(\frac{\sqrt{3}}{2},0)\\}\text{
with }V(Q;\\{\gamma_{6},HI\\})=\frac{1}{12}(2-\sqrt{3}).$

Thus, we have

$\gamma_{6}=\hat{\beta}\bigcup\\{(-0.639488,0),(-0.41295,0),(\frac{1}{2},0)\\},$

with
$V_{6}(Q)=V(Q;\\{\gamma_{6},GI\\})+V(Q;\\{\gamma_{6},HI\\})=0.0199575+\frac{1}{12}(2-\sqrt{3})=0.0422866$.

######  Example 6.2.15.

To obtain $\gamma_{7}(Q)$ and the corresponding constrained quantization error
$V_{7}(Q)$ for the uniform distribution $Q$, we proceed as follows. Let $n=7$
and choose $n_{1}=3$ and $n_{2}=3$. Then, by (12), we have

$\displaystyle\gamma_{7}\cap GH^{(1)}$ $\displaystyle=\gamma_{6}\cap
GH^{(1)}=\\{(-\frac{\sqrt{3}}{2},0),(-0.639488,0),(-0.41295,0)\\}\text{ with
}$ $\displaystyle V(Q;\\{\gamma_{7},GI\\})$
$\displaystyle=V(Q;\\{\gamma_{6},GI\\})=0.0199575.$

Moreover, as $n_{2}=3$, using the properties of reflection as mentioned in
Methodology 6.2.13, we have

$\displaystyle\gamma_{7}\cap GH^{(2)}$
$\displaystyle=\\{(0.41295,0),(0.639488,0),(\frac{\sqrt{3}}{2},0)\\}\text{
with }$ $\displaystyle V(Q;\\{\gamma_{7},HI\\})$
$\displaystyle=V(Q;\\{\gamma_{7},GI\\})=0.0199575.$

Thus, we have

$\gamma_{7}=\hat{\beta}\bigcup\\{(-0.639488,0),(-0.41295,0),(0.41295,0),(0.639488,0)\\}$

with
$V_{7}(Q)=V(Q;\\{\gamma_{7},GI\\})+V(Q;\\{\gamma_{7},HI\\})=0.0199575+0.0199575=0.039915$.

$D(\frac{1}{2},\frac{\sqrt{3}}{2})$$E(-\frac{1}{2},\frac{\sqrt{3}}{2})$$F(-1,0)$

$D(\frac{1}{2},\frac{\sqrt{3}}{2})$$E(-\frac{1}{2},\frac{\sqrt{3}}{2})$$F(-1,0)$

$D(\frac{1}{2},\frac{\sqrt{3}}{2})$$E(-\frac{1}{2},\frac{\sqrt{3}}{2})$$F(-1,0)$

$D(\frac{1}{2},\frac{\sqrt{3}}{2})$$E(-\frac{1}{2},\frac{\sqrt{3}}{2})$$F(-1,0)$

Figure 6. In conditional constrained quantization with the constraint as the
diagonal $FD$ the dots represent the elements in an optimal set of $n$-points
for $7\leq n\leq 10$.

######  Proposition 6.2.16.

Let $\alpha_{n}$ be a conditional constrained optimal set of $n$-points for
$P$ with conditional constrained quantization error $V_{n}$. Then,

$\displaystyle\alpha_{9}$
$\displaystyle=\beta\cup\Big{\\{}(-0.803813,0.113269),(-0.607625,0.226538),(0.183013,0.683013)\Big{\\}}$
$\displaystyle\qquad\text{ with
}V_{9}=\frac{0.0422866}{3}+\frac{1}{18}=0.0696511,$ $\displaystyle\alpha_{10}$
$\displaystyle=\beta\cup\Big{\\{}(-0.803813,0.113269),(-0.607625,0.226538),(0.107625,0.639488),(0.303813,0.752757)\Big{\\}}$
$\displaystyle\qquad\text{ with
}V_{10}=\frac{0.039915}{3}+\frac{1}{18}=0.0688606$

###### Proof.

The proof follows by Lemma 6.2.8, Example 6.2.14, and Example 6.2.15 (see
Figure 6). ∎

######  Main result 6.2.17.

Recall that the main result of this subsection is to obtain the conditional
constrained optimal sets $\alpha_{n}:=\alpha_{n}(P)$ of $n$-points and the
corresponding conditional constrained quantization errors $V_{n}(P)$ for all
$n\geq 6$ for the uniform distribution $P$ under the constraint as the smaller
diagonal $FD$ and the conditional set $\beta$. As shown in Example 6.2.14 and
Example 6.2.15, using Methodology 6.2.13, we obtain $\gamma_{n-3}(Q)$ and
$V_{n-3}(Q)$ for the uniform distribution $Q$. Then, using Lemma 6.2.8, we
obtain the sets $\alpha_{n}$ and the corresponding conditional constrained
quantization errors $V_{n}(P)$ for all $n\geq 6$.

## References

  * [BW] J.A. Bucklew and G.L. Wise, _Multidimensional asymptotic quantization theory with $r$th power distortion measures_, IEEE Transactions on Information Theory, 1982, Vol. 28 Issue 2, 239-247.
  * [BCDRV] P. Biteng, M. Caguiat, D. Deb, M.K. Roychowdhury, and B. Villanueva, _Constrained quantization for a uniform distribution_ , arXiv:2312:16615 [math.PR].
  * [DFG] Q. Du, V. Faber and M. Gunzburger, _Centroidal Voronoi Tessellations: Applications and Algorithms_ , SIAM Review, Vol. 41, No. 4 (1999), pp. 637-676.
  * [DR] C.P. Dettmann and M.K. Roychowdhury, _Quantization for uniform distributions on equilateral triangles_ , Real Analysis Exchange, Vol. 42(1), 2017, pp. 149-166.
  * [GG] A. Gersho and R.M. Gray, _Vector quantization and signal compression_ , Kluwer Academy publishers: Boston, 1992.
  * [GL] S. Graf and H. Luschgy, _Foundations of quantization for probability distributions_ , Lecture Notes in Mathematics 1730, Springer, Berlin, 2000.
  * [GL1] A. György and T. Linder, _On the structure of optimal entropy-constrained scalar quantizers_ , IEEE transactions on information theory, vol. 48, no. 2, February 2002.
  * [GL2] S. Graf and H. Luschgy, _The Quantization of the Cantor Distribution_ , Math. Nachr., 183 (1997), 113-133.
  * [GL3] S. Graf and H. Luschgy, _Quantization for probability measures with respect to the geometric mean error_ , Math. Proc. Camb. Phil. Soc. (2004), 136, 687-717.
  * [GN] R.M. Gray and D.L. Neuhoff, _Quantization_ , IEEE Transactions on Information Theory, Vol. 44, No. 6, October 1998, 2325-2383.
  * [H] J. Hutchinson, _Fractals and self-similarity_ , Indiana Univ. J., 30 (1981), 713-747.
  * [KNZ] M. Kesseböhmer, A. Niemann and S. Zhu, _Quantization dimensions of compactly supported probability measures via Rényi dimensions_ , Trans. Amer. Math. Soc. (2023).
  * [P] D. Pollard, _Quantization and the Method of $k$-Means_, IEEE Transactions on Information Theory, 28 (1982), 199-205.
  * [P1] K. Pötzelberger, _The quantization dimension of distributions_ , Math. Proc. Cambridge Philos. Soc., 131 (2001), 507-519.
  * [PR1] M. Pandey and M.K. Roychowdhury, _Constrained quantization for probability distributions_ , arXiv:2305.11110 [math.PR].
  * [PR2] M. Pandey and M.K. Roychowdhury, _Constrained quantization for the Cantor distribution_ , arXiv:2306.16653 [math.DS].
  * [PR3] M. Pandey and M.K. Roychowdhury, _Constrained quantization for a uniform distribution with respect to a family of constraints_ , arXiv:2309:11498 [math.PR].
  * [PR4] M. Pandey and M.K. Roychowdhury, _Constrained quantization for the Cantor distribution with a family of constraints_ , arXiv:
  * [PR5] M. Pandey and M.K. Roychowdhury, _Conditional constrained and unconstrained quantization for probability distributions_ , arXiv:2312:02965 [math.PR].
  * [RR] J. Rosenblatt and M.K. Roychowdhury, _Uniform distributions on curves and quantization_ , Commun. Korean Math. Soc. 38 (2023), No. 2, pp. 431-450.
  * [R1] M.K. Roychowdhury, _Quantization and centroidal Voronoi tessellations for probability measures on dyadic Cantor sets_ , Journal of Fractal Geometry, 4 (2017), 127-146.
  * [R2] M.K. Roychowdhury, _Least upper bound of the exact formula for optimal quantization of some uniform Cantor distributions_ , Discrete and Continuous Dynamical Systems- Series A, Volume 38, Number 9, September 2018, pp. 4555-4570.
  * [R3] M.K. Roychowdhury, _Optimal quantization for the Cantor distribution generated by infinite similitudes_ , Israel Journal of Mathematics 231 (2019), 437-466.
  * [Z1] P.L. Zador, _Asymptotic Quantization Error of Continuous Signals and the Quantization Dimension_ , IEEE Transactions on Information Theory, 28 (1982), 139-149.
  * [Z2] R. Zam, _Lattice Coding for Signals and Networks: A Structured Coding Approach to Quantization, Modulation, and Multiuser Information Theory_ , Cambridge University Press, 2014.


11institutetext:  Politecnico di Milano, Milan Italy
22institutetext: Dip. di Informatica e Sistemistica Università di Roma ”La
Sapienza”, Rome Italy.
33institutetext: International Telematic University Uninettuno, Rome, Italy
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Complexity-based partitioning of CSFI problem instances with Transformers

L. Benedetto 11 P. Fantozzi and L. Laura 2233

###### Abstract

In this paper, we propose a two-steps approach to partition instances of the
Conjunctive Normal Form (CNF) Syntactic Formula Isomorphism problem (CSFI)
into groups of different complexity. First, we build a model, based on the
Transformer architecture, that attempts to solve instances of the CSFI
problem. Then, we leverage the errors of such model and train a second
Transformer-based model to partition the problem instances into groups of
different complexity, thus detecting the ones that can be solved without using
too expensive resources. We evaluate the proposed approach on a pseudo-
randomly generated dataset and obtain promising results. Finally, we discuss
the possibility of extending this approach to other problems based on the same
type of textual representation.

###### Keywords:

Artificial Intelligence Natural Language Processing CNF Computational
Complexity

##  1 Introduction

In most domains, from theoretical ones to practical ones, there is the need to
cope with tasks of high computational complexity. Even if computers can help
to automatize many activities, some of these activities cannot be solved
easily using an algorithm, because a subset of their instances (if not all)
require computational resources that are not available or too expensive.
Usually, the solution to this issue consists of avoiding automation at all,
even when most of the problem instances are easily solvable, and only few of
them are computationally unfeasible. A better solution could be to classify
the instances of the problem, partitioning them depending on the complexity of
their solution, which would enable to tackle the feasible ones.

To provide this type of partitioning for a given problem, we propose a
supervised machine learning approach made of two phases. The first step
consists in training a neural network model to (try to) solve the problem. At
this stage, the choice of the neural architecture to use is a critical point,
because the complexity of the architecture will correspond to the boundary of
the partitioning. Indeed, since a neural network is just an algorithm with a
certain computational complexity, it is not possible to solve instances that
require higher computational complexity with respect to the neural network.
The output of the first step is made of instances of the problem that are
correctly solved and instances that are not solved by the model. We then label
the instances that were not solved as “hard” and the other instances as
“easy”. Finally, in the second phase, we use these new labels as target values
to train another model, whose architecture is identical to the model trained
in the first phase. After training, the second model will be able to identify
– with a certain amount of confidence – if an instance of the original problem
is either easy or hard to be solved.

To evaluate the proposed approach, we experiment on the Conjunctive Normal
Form (CNF) Syntactic Formula Isomorphism problem (CSFI), trying to build a
model to classify the complexity of the isomorphism checking on a pair of CNF.
An example of a CNF is the following:

$(a\vee b)\wedge(\neg a\vee c\vee\neg b)\wedge(\neg c\vee c)$

As for the models, we use the Transformer architecture [21], which is one of
the most complex neural network architectures available. Specifically, since
the Transformer has a $O(n^{2})$ complexity, we know that it cannot solve
problems more complex than that.

##  2 Related work

The _CNF Syntactic Formula Isomorphism_ (CSFI) problem is the task of stating
whether two CNF Boolean formulas are semantically isomorphic [1, 2]. This
problem is also related to the formula equivalence problem: indeed, if two
formulas are semantically isomorphic then they are also semantically
equivalent, but not the opposite. Furthermore, Thierauf [20] showed that the
Graph Isomorphism problem (GI) is polynomial time reducible to Formula
Isomorphism problem (FI), thus showing that FI is in the GI class. Ausiello et
al. [3] proved that CSFI belongs to GI as well.

The relation between CSFI and GI is interesting also because GI has been
studied in depth in the literature. Some important papers about Graph
Isomorphism are, for instance: the classic work of McKay [12], the work from
McKay and Piperno [13] and the work from Babai [4] that shows a quasi-
polynomial time algorithm for GI.

In [9], the authors define two classes of non-isomorphic formulas (i.e.
trivial and non-trivial) based on the properties of the formulas. This
classification is useful to partition CNFs in different complexity classes,
since the paper describes a technique to check the non-isomorphism of two
formulas (under some conditions) that has different complexity depending on
the class of the formulas.

In the literature, there are some attempts to build neural network models to
solve classical theoretical computer science problems. In [18] the authors try
to train a Message Passing Neural Network (as defined in [10]) to solve
instances of the Boolean satisfiability problem. Also, in [16], the authors
train a Graph Neural Network to solve instances of the Traveling Salesperson
Problem. To the best of our knowledge, no previous work proposed the usage of
Transformers (nor other types of neural networks) to estimate the complexity
of the instances of a given problem.

###  2.1 Transformers

The Transformer is an architecture originally proposed for sequence to
sequence tasks in Natural Language Processing (NLP). An example of a sequence
to sequence task is machine translation, where sentences from one language are
converted to sentences in another language. Since its introduction in 2017
[21], the Transformer enabled a fast-paced improvement of the state of the art
performance in several NLP tasks (not only sequence to sequence), and many
powerful models are based on this architecture (e.g. BERT [8], XLNet [22],
GPT-3 [6]). The main technological innovation of Transformers was the usage of
a self-attention mechanism, which enables the model to extract features for
each word to figure out how important all the other words in the sentence are
with respect to the aforementioned word, and this capability enables the
Transformer to more accurately model natural language and the relationships
between different words. Currently, Transformer-based models are commonly used
in NLP tasks in many different domains – such as education [5], and
recommender systems [15] – and successfully applied in computer vision [14,
7].

In this paper, we take inspiration from previous research and use Transformers
for a task not related to NLP, proposing a model capable of partitioning CNF
in complexity classes. Specifically, we implement a modified version of
RoBERTa [11], which is a model originally built upon BERT with some key
modifications to the pretraining objective and the hyperparameters, which make
it more adequate to the task we have at hand. Crucially, RoBERTa uses BPE
[19], a byte-level tokenizer, to convert the input sequences into tokens while
BERT uses the WordPiece tokenizer [17]. Since we are not really dealing with
language but CNFs (made of literals) a byte-level tokenizer is more
appropriate. As for the architecture, the original RoBERTa model is a multi-
layer transformer model which is pre-trained on the task of Masked Language
Modelling and can later be fine-tuned on several downstream tasks. Masked
Language Modelling consists in masking one of the input tokens with a special
token and asking the model to fill the blank. Fine-tuning on a downstream task
consists in adding one or more layers on top of the network in order to adapt
it to the task at hand. In this paper, we deal with a sentence classification
task, therefore we add a fully connected classification layer on top of the
original network. Also, since the task of MLM is not adequate for CNFs, we
directly train the whole model on the sentence classification task, in order
to leverage the attention mechanisms of the original RoBERTa model.

##  3 A Neural Network approach for complexity partitioning

As described in the introduction, the proposed approach is made of two steps.
First, i) we train a model to classify pairs of CNF as isomorphic or non-
isomorphic (separately considering trivial and non-trivial non-isomorphism),
then ii) we train a separate model – with the same architecture – to predict
the complexity a given pair of CNF, using as gold standard the correctness of
the prediction of the first model. The output of the second model indicates,
with a given confidence, whether that specific instance of the original
problem (i.e. CSFI for the given pair of CNF) is either easy or hard to solve.

In the CSFI problem, each instance is made of a pair of CNF, which are given
as input sequence to the model. Since our models cannot directly work on the
CNF, the input sequence must be tokenized. Tokenizing a sequence, in our case
a CNF, consists of splitting it into smaller components, which are then
converted to ids through a look-up table. As an example, a way of tokenizing a
natural language sentence is to split it in words and associate an id to each
word. As we are not dealing with words but rather with CNF, we use a byte-
level tokenizer: specifically, we use the Byte Level BPE Tokenizer, in its
implementation from HuggingFace 111huggingface.co/docs/tokenizers/python. In
practice, the tokenizer separates all the literals and the operators, as in
the following example: $a\vee c\wedge c\vee b$ is tokenized into [$<$s$>$, $a$
$\vee$, $c$, $\wedge$, $c$, $\vee$, $b$, $<$/s$>$], where “$<$s$>$” and
“$<$/s$>$” are two special tokens that indicate the beginning and the end of
the CNF, and then converted into a list of IDs. We use 100 as vocabulary size
(vocab_size=100), which is sufficient for the CNFs considered in this study,
and min_frequency=1, meaning that all the literals are considered (even if
they appear only once) and no “unknown” token is used. The same tokenizer is
used in both phases of the proposed approach.

###  3.1 Model

For the two phases of our approach – i) CSFI and ii) complexity partitioning
of instances of CSFI – we use two different models. However, these two models
have the same architecture, since in both phases the task is sequence
classification; the only difference (but a crucial one) is the inner weights
of the neural networks, which are learned at training time.

Both models are based on RoBERTa [11], and we do not perform any modification
to its. That is, it is made of 6 hidden layers, we use 12 attention heads, and
we set 512 as maximum input length222we use the RobertaConfig and
RobertaForSequenceClassification classes from the HuggingFace transformers
library (https://huggingface.co/transformers).

However, we add a dense layer and a linear output layer on top of that, in
order to adapt RoBERTa to the task of sequence classification. Also, since
each model receives as input pairs of CNF (namely $\alpha$ and $\beta$) and we
do not want the ordering of the pair to influence the outcome of the
classification, we consider in parallel the two possible concatenations
($\alpha\beta$ and $\beta\alpha$). In practice, we retrieve the output of the
RoBERTa model for the two sequences, concatenate it into a unique array, and
give it as input to the classification layers (i.e. dense layer and linear
output layer).

##  4 Experimental results

In this section we present and analyse the experimental results obtained to
evaluate the proposed architecture. The hardware configuration used for the
experiments is the following: Intel i7-9700k with 8 cores with frequency of
3.60 Ghz, 32 GB of DDR4 RAM, a NVIDIA Titan Xp graphic card with 12 GB of RAM
and CUDA libraries version 11.3.

###  4.1 Dataset

All the datasets used for the experiments have been generated using the
algorithms defined in [9], implemented with the python library presented in
the same work. All the pairs of isomorphic CNFs are composed by i) a randomly
generated formula and ii) a formula built by applying a random isomorphism to
the first one. All the pairs of non-isomorphic formulas are composed by i) a
randomly generated CNF $\alpha$ and ii) a formula $\gamma$ obtained by
applying a first step to transform $\alpha$ to another CNF $\beta$ that is not
isomorphic to $\alpha$, and then a second step to build $\gamma$ as isomorphic
with respect to $\beta$. Since, by definition, the syntactic isomorphism
property is transitive, in each pair defined as before, $\gamma$ is not
isomorphic to $\alpha$.

The random generation of all the CNFs in the datasets respects the following
parameters:

  * •

the number of symbols in each formula is in the range $[15,25]$;

  * •

all the symbols in the datasets are randomly chosen from same set of 25
symbols;

  * •

the number of clauses in each formula is in the range $[10,15]$;

  * •

all the clauses have the same cardinality (8);

  * •

all the formulas are monotone (there are no negated literals).

Given a CNF, the trivial non-isomorphic generation is performed by using one
random modification between the following:

  * •

adding a new clause with the same cardinality randomly choosing symbols from
the ones in the CNF;

  * •

adding a symbol (from the ones in the CNF) to an existing clause, thus
changing its cardinality;

  * •

adding a symbol that is not present in the CNF.

The dataset used to train the first model is composed of $50^{\cdot}000$ pairs
of CNFs, belonging to three categories: 50% pairs are syntactically
isomorphic, 25% are trivially non-isomorphic, and 25% are non-trivially non-
isomorphic. The pairs have been labeled with 0 or 1 for non-isomorphic and
isomorphic pairs, respectively. The evaluation and test datasets have been
generated using the same parameters of the train dataset, with the only
difference that they are made of $10^{\cdot}000$ pairs each.

The train dataset for the second model is built with the following steps.
First, we build a dataset which has the same characteristics of the datasets
used to train and evaluate the first model. Then, we use the first model to
classify the samples of this dataset, and compare the true label with the
predicted class, creating a new label that indicates whether the first model
correctly classified each pair of CNFs (0 indicating correct classification
and 1 wrong classification). After that, we randomly select a subset of the
samples such that 50% of the samples are correctly classified and 50% are
wrongly classified. The actual size of this dataset will depend on the size of
the smallest subset between the classified samples.

Both the evaluation and test datasets for the second model are generated
following the same guidelines of the previous datasets to obtain
$10^{\cdot}000$ pairs for each dataset, 50% of the trivially non-isomorphic
and 50% non-trivially non-isomorphic. Since we use these datasets to test the
second model, which has been trained to classify the samples that are
difficult to solve, we can use only non-isomorphic pairs, because we have no
information about the difficulties of the isomorphic pairs.

###  4.2 First phase results

Accuracy | Precision | Recall | F1
---|---|---|---
0.730 | 0.669 | 1.0 | 0.801
Table 1: Evaluation metrics for the first model on the test dataset.

Table 1 shows the results obtained on the test set with the first model; we
use accuracy, precision, recall, and f1-score as evaluation metrics. The
training lasted 10 hours and 30 minutes.

Figure 1: Training loss and evaluation loss for the training of the model for
the 1st phase. Figure 2: Evaluation accuracy and F1 score for the training of
the model for the 1st phase.

As shown in the loss plot in the Figure 1, the model starts to learn very well
in the first epoch. Then in the second epoch something changes in its ability
to generalise, as if it was starting to learn from scratch again. Finally, at
the end of the sixth epoch, there is a major learning step, and the loss
stabilises, reaching lower loss values than at the beginning.

Both the evaluation accuracy and the evaluation F1-score follow the same trend
as well, as shown in Figure 2. Indeed, the two curves have the same
discontinuities at the end of the second and the sixth epoch, reaching, after
that, the best results.

| iso. | trivial non-iso. | non-trivially non-iso.
---|---|---|---
right label | 4986 | 1704 | 0
wrong label | 0 | 0 | 2462
Table 2: Number of samples that are correctly labeled by the first phase
model.

After training the first model, the training dataset for the second model was
created, performing the classification of each pair of CNFs and comparing it
with the ground truth values. From the results shown in Table 2, we can notice
that the only misclassified samples are the samples generated as non-trivial
non-isomorphic, which are the most complex ones.

###  4.3 Second phase results

Threshold | Accuracy | Precision | Recall | F1
---|---|---|---|---
0.50 | 0.993 | 0.989 | 1.0 | 0.994
0.66 | 0.976 | 0.962 | 1.0 | 0.980
0.51 | 0.993 | 0.989 | 1.0 | 0.994
Table 3: Results of the model for the 2nd phase applied to the test dataset.
The column threshold contains the probability threshold of consider a sample
“easy to solve”. The first value is just the majority, the second is chosen to
indicate a threshold that is largely bigger than the majority, while the last
one is the best threshold that could be picked for this dataset (used only to
compare the results).

In the second phase we assign to each sample of the second training dataset 1
if they are misclassified from the first model and 0 otherwise. This model
should be able to recognize if a sample is “easy to solve”, so, after the
training, we used a test dataset composed by 50% of “easy” samples and 50% of
”hard“ samples. The results from the linear output layer of the model are
transformed using a softmax to have a probability distribution over the two
labels that sum to 1. The results, after a training of 5 hours and 38 minutes,
with respect to the test dataset are shown in table 3.

We tried to apply different thresholds to the probabilities returned from the
model. Indeed, in our idea, the model should be very confident before
classifying a sample as “easy”. So we don’t want to use just the higher
probability between 0 and 1, and we think that the probability to be an easy
sample should be at least the double with respect to the opposite
classification. Since that the probabilities sum to 1, then it is equivalent
to say that the probability of the “easy” classification should be greater
than 0.66. In the table of results we show: the results for just the majority
in probabilities, the results for a threshold of 0.66 and also the best
results obtainable moving the threshold.

Figure 3: Training loss and evaluation loss for the training of the model for
the 2nd phase

In the loss curve plot shown in figure 3 we can see that the model learns
quickly since that from the second epoch the training loss remains more or
less stable. The evaluation loss, instead, shows much more variance, but it
becomes more stable during the epochs to become, eventually, comparable with
the training loss.

Figure 4: Evaluation F1 score for the training of the model for the 2nd phase

The same evaluation performed on the results on the test dataset, is also
performed continuously on the evaluation dataset during the training. In the
figure 4 can be seen the F1 score for the 3 different thresholds described
before. It is easy to notice that the gap between them tends to be more stable
with the epochs. At the end, the gap seems to be small, and this is also
confirmed in the results shown before.

Figure 5: Minimum evaluation F1 score, in the range [0.5,1.0] for the training
of the model for the 2nd phase Figure 6: Plot of the difference between the
maximum F1 score (obtained with the best threshold) and the minimum F1 score
(obtained with a different threshold) during the training of the 2nd model.

We also show, in the figure 5, the curve of the F1 score that is the mininum
between the scores obtained by using the 3 different thresholds during the
training. We can see that the trend of the minimum F1 score is a slowly
increasing. At the same time, the gap between the minimum and the maximum F1
score given by the different thresholds, decrease quickly during the epochs as
shown in figure 6.

Figure 7: Plot of the threshold on probabilities that gives the best results
on the evaluation dataset during the training.

It is also interesting to analyse the trend of the thresholds computed during
the training. They are computed looking for the threshold on the probabilities
that returns the best results overt the evaluation dataset. It can be seen in
the figure 7 that the threshold tends to decrease, and so the model becomes
more accurate to estimate the probabilities.

##  5 Conclusion

In this paper, we proposed a neural network-based approach to partition
instances of the CNF Syntactic Formula Isomorphism problem (CSFI) into
different complexity classes. From this categorization, it is also possible to
get a complexity threshold, which separates the easy instances (under the
threshold) and the instances for which it is hard to find a solution (above
the threshold).

The proposed approach is made of two neural models – both based on the
Transformer architecture – which serve different purposes. The first one is
trained to attempt to solve instances of the problem; however, rather than
using its predictions as solutions to the instances, we leverage them to build
a training dataset. Specifically, we build a dataset made of two classes (easy
and hard), and use it to train the second model, which then learns to
partition CNFs in the two complexity groups.

The advantage of this approach is that it can be used to identify the
instances of a problem whose solution could be automatized without needing too
expensive hardware resources, allowing the planning of different solution
strategies depending on the cost of the solution itself.

Finally, it is worth noting that in this paper we only experimented on CNFs
and instances of the CSFI problem, but this approach could most likely be
extended to different problems. Indeed, we only leverage the textual
representation of the CNFs and other problems (such as the Boolean
satisfiability problem) have similar representations. Future research will
work towards that direction.

Acknowledgements Luigi Laura gratefully acknowledges the support of NVIDIA
Corporation with the donation of the Titan Xp used for this research.

## References

  * [1] Agrawal, M., Thierauf, T.: The boolean isomorphism problem. In: Proceedings of 37th Conference on Foundations of Computer Science (FOCS). pp. 422–430. IEEE (1996)
  * [2] Agrawal, M., Thierauf, T.: The formula isomorphism problem. SIAM Journal on Computing 30(3), 990–1009 (2000)
  * [3] Ausiello, G., Cristiano, F., Fantozzi, P., Laura, L.: Syntactic isomorphism of CNF boolean formulas is graph isomorphism complete. In: Cordasco, G., Gargano, L., Rescigno, A.A. (eds.) Proceedings of the 21st Italian Conference on Theoretical Computer Science, Ischia, Italy, September 14-16, 2020. CEUR Workshop Proceedings, vol. 2756, pp. 190–201. CEUR-WS.org (2020), http://ceur-ws.org/Vol-2756/paper\\_23.pdf
  * [4] Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. ACM Press, New York, New York, USA (2016)
  * [5] Benedetto, L., Aradelli, G., Cremonesi, P., Cappelli, A., Giussani, A., Turrin, R.: On the application of transformers for estimating the difficulty of multiple-choice questions from text. In: Proceedings of the 16th Workshop on Innovative Use of NLP for Building Educational Applications. pp. 147–157 (2021)
  * [6] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J.D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., Amodei, D.: Language models are few-shot learners. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M.F., Lin, H. (eds.) Advances in Neural Information Processing Systems. vol. 33, pp. 1877–1901. Curran Associates, Inc. (2020), https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf
  * [7] Carion, N., Massa, F., Synnaeve, G., Usunier, N., Kirillov, A., Zagoruyko, S.: End-to-end object detection with transformers. In: European Conference on Computer Vision. pp. 213–229. Springer (2020)
  * [8] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 4171–4186 (2019)
  * [9] Fantozzi, P., Laura, L., Nanni, U., Villa, A.: Non-isomorphic cnf generation. In: Submitted to the 18th International Conference on Distributed Computing and Artificial Intelligence, Salamanca, Spain, 6-8 October 2021 (2021)
  * [10] Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. In: Precup, D., Teh, Y.W. (eds.) Proceedings of the 34th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 70, pp. 1263–1272. PMLR (06–11 Aug 2017)
  * [11] Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., Stoyanov, V.: Roberta: A robustly optimized bert pretraining approach. arXiv e-prints pp. arXiv–1907 (2019)
  * [12] McKay, B.D., Others: Practical graph isomorphism (1981)
  * [13] McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symbolic Comput. 60, 94–112 (Jan 2014)
  * [14] Parmar, N., Vaswani, A., Uszkoreit, J., Kaiser, L., Shazeer, N., Ku, A., Tran, D.: Image transformer. In: International Conference on Machine Learning. pp. 4055–4064. PMLR (2018)
  * [15] Penha, G., Hauff, C.: What does bert know about books, movies and music? probing bert for conversational recommendation. In: Fourteenth ACM Conference on Recommender Systems. pp. 388–397 (2020)
  * [16] Prates, M., Avelar, P.H., Lemos, H., Lamb, L.C., Vardi, M.Y.: Learning to solve np-complete problems: A graph neural network for decision tsp. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 33, pp. 4731–4738 (2019)
  * [17] Schuster, M., Nakajima, K.: Japanese and korean voice search. In: 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 5149–5152. IEEE (2012)
  * [18] Selsam, D., Lamm, M., Bünz, B., Liang, P., de Moura, L., Dill, D.L.: Learning a sat solver from single-bit supervision. arXiv preprint arXiv:1802.03685 (2018)
  * [19] Sennrich, R., Haddow, B., Birch, A.: Neural machine translation of rare words with subword units. In: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1715–1725 (2016)
  * [20] Thierauf, T.: The computational complexity of equivalence and isomorphism problems. Springer-Verlag, Berlin, Heidelberg (2000)
  * [21] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. pp. 6000–6010 (2017)
  * [22] Yang, Z., Dai, Z., Yang, Y., Carbonell, J., Salakhutdinov, R.R., Le, Q.V.: Xlnet: Generalized autoregressive pretraining for language understanding. Advances in Neural Information Processing Systems 32, 5753–5763 (2019)