$\displaystyle\leq\frac{\max_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})}{\alpha_{K}^{\zeta_{\mu}}\cdot\min_{c\in\mathcal{C}}n_{c}^{\zeta_{\mu}}}\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}.$

By the local data size scaling assumption in Assumption 2, for any
$c\in\mathcal{C}$, we have that $n_{c}=\Omega(\nu_{c}(n))$ where $\nu_{c}$ is
an increasing function. In other words, there exists a constant $\tau>0$ such
that $n_{c}\geq\tau\nu_{c}(n)$ for sufficiently large $n$. Then, since $g_{c}$
is decreasing, $g_{c}(\alpha_{K}n_{c})<g_{c}(\tau\alpha_{K}\nu_{c}(n))$ for
sufficiently large $n$. Moreover, since $\nu_{c}$ is increasing and
$\tau\alpha_{K}>0$, $\tilde{\nu}_{c}=\tau\alpha_{K}\nu_{c}$ is also
increasing, and since $g_{c}$ is decreasing, the composition
$\tilde{g}_{c}=g_{c}\circ\tilde{\nu}_{c}$ is decreasing. Therefore,
$g_{c}(\alpha_{K}n_{c})$ is asymptotically bounded by a decreasing function
$\tilde{g}_{c}$ of $n$. This observation and the fact that the maximum of a
set of decreasing functions is itself decreasing imply that
$\max_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})$ is asymptotically bounded by
the decreasing function $\tilde{g}$ defined by
$\tilde{g}(n)=\max_{c\in\mathcal{C}}\tilde{g}_{c}(n)$. In other words,

$\displaystyle\max_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})\leq\tilde{g}(n)\leq
o(1).$

Additionally, since $n_{c}=\Omega(\nu_{c}(n))$ and ${\zeta_{\mu}}>0$, we also
have that

$\displaystyle\frac{1}{\min_{c\in\mathcal{C}}n_{c}^{\zeta_{\mu}}}\leq o(1).$

These two observations imply

$\displaystyle\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}}\operatorname{\mathbb{E}}\left[||\hat{\mu}_{c}^{-k_{c}(i)}(X_{i}^{c})-\mu_{c}(X_{i}^{c})||^{2}\mid\hat{\mu}_{c}^{-k_{c}(i)}\right]$
$\displaystyle\leq\frac{\max_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})}{\alpha_{K}^{\zeta_{\mu}}\cdot\min_{c\in\mathcal{C}}n_{c}^{\zeta_{\mu}}}\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}\leq
o\left(\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}\right).$

Therefore,

$\displaystyle\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{1}^{k}(\pi_{a},\pi_{b})\right|$
$\displaystyle\leq
C_{\Pi,\delta}\left(1/\eta-1\right)\sqrt{\frac{2}{K}\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}}\operatorname{\mathbb{E}}\left[||\hat{\mu}_{c}^{-k_{c}(i)}(X_{i}^{c})-\mu_{c}(X_{i}^{c})||_{2}^{2}\mid\hat{\mu}_{c}^{-k_{c}(i)}\right]}+o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right)$
$\displaystyle\leq C_{\Pi,\delta}\left(1/\eta-1\right)\sqrt{\frac{2}{K}\cdot
o\left(\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}\right)}+o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right)\leq
o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right),$

and

$\displaystyle\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{1}(\pi_{a},\pi_{b})\right|$
$\displaystyle\leq\sum_{k=1}^{K}\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{1}^{k}(\pi_{a},\pi_{b})\right|\leq
o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right).$

Bounding $S_{2}$: The bound for
$\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{2}(\pi_{a},\pi_{b})\right|$ follows the
same argument as that of $S_{1}$. We first bound
$\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{2}^{k}(\pi_{a},\pi_{b})\right|$ for any
$k\in[K]$.

First, note that since $\hat{w}_{c}^{-k_{c}(i)}$ is estimated using data
outside fold $k_{c}(i)$, when we condition on the data outside fold
$k_{c}(i)$, $\hat{w}_{c}^{-k_{c}(i)}$ is fixed and each term in
$S_{2}(\pi_{a},\pi_{b})$ is independent. This allows us to compute

$\displaystyle\operatorname{\mathbb{E}}\left[\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{a\in\mathcal{A}}\left(\pi_{a}(X_{i}^{c};a)-\pi_{b}(X_{i}^{c};a)\right)\left(Y_{i}^{c}(a)-\mu_{c}(X_{i}^{c};a)\right)\left(\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c};a)-w_{c}(X_{i}^{c};a)\right)\mathbf{1}\\{A_{i}^{c}=a\\}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\left(\pi_{a}(X_{i}^{c};A_{i}^{c})-\pi_{b}(X_{i}^{c};A_{i}^{c})\right)\left(Y_{i}^{c}(A_{i}^{c})-\mu_{c}(X_{i}^{c};A_{i}^{c})\right)\left(\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c};a)-w_{c}(X_{i}^{c};a)\right)\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\operatorname{\mathbb{E}}\left[\left(\pi_{a}(X_{i}^{c};A_{i}^{c})-\pi_{b}(X_{i}^{c};A_{i}^{c})\right)\left(Y_{i}^{c}(A_{i}^{c})-\mu_{c}(X_{i}^{c};A_{i}^{c})\right)\left(\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c};a)-w_{c}(X_{i}^{c};a)\right)\
\Big{|}\ X_{i}^{c},A_{i}^{c}\right]\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\left(\pi_{a}(X_{i}^{c};A_{i}^{c})-\pi_{b}(X_{i}^{c};A_{i}^{c})\right)\operatorname{\mathbb{E}}\Big{[}Y_{i}^{c}(A_{i}^{c})-\mu_{c}(X_{i}^{c};A_{i}^{c})\mid
X_{i}^{c},A_{i}^{c}\Big{]}\left(\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c};a)-w_{c}(X_{i}^{c};a)\right)\right]=0$

Therefore, we can follow the exact same argument as above, eliciting
Proposition 2, to obtain that with probability at least $1-\delta$,

$\displaystyle
K\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{2}^{k}(\pi_{a},\pi_{b})\right|$
$\displaystyle\leq\sup_{\pi_{a},\pi_{b}\in\Pi}\Bigg{|}\sum_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}/K}\sum_{\\{i|k_{c}(i)=k\\}}\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))\Bigg{|}$
$\displaystyle=\sup_{\pi_{a},\pi_{b}\in\Pi}\Bigg{|}\sum_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}/K}\sum_{\\{i|k_{c}(i)=k\\}}\big{(}\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))\big{)}-\operatorname{\mathbb{E}}\left[\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))\right]\Bigg{|}$
$\displaystyle\leq\sup_{\pi_{a},\pi_{b}\in\Pi}\bigg{|}\sum_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}/K}\sum_{\\{j|k_{i}(j)=k\\}}\big{(}\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))\big{)}-\operatorname{\mathbb{E}}\left[\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))\right]\bigg{|}$
$\displaystyle\leq
C_{\Pi,\delta}\sqrt{\frac{\sup_{\pi_{a},\pi_{b}\in\Pi}\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{\bar{n}_{c}}\operatorname{\mathbb{E}}\left[\big{(}\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))\big{)}^{2}\mid\hat{w}_{c}^{-k_{c}(i)}\right]}{n/K}}+o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n/K}}\,\right)$
$\displaystyle\leq
C_{\Pi,\delta}\sqrt{K\sup_{\pi_{a},\pi_{b}\in\Pi}\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}}\operatorname{\mathbb{E}}\left[\big{(}\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))\big{)}^{2}\mid\hat{w}_{c}^{-k_{c}(i)}\right]}+o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right)$
$\displaystyle\leq
C_{\Pi,\delta}\sqrt{4BK\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}}\operatorname{\mathbb{E}}\left[||\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c})-w_{c}(X_{i}^{c})||_{2}^{2}\mid\hat{w}_{c}^{-k_{c}(i)}\right]}+o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right),$

where $C_{\Pi,\delta}=c_{1}\kappa(\Pi)+\sqrt{c_{2}\log(c_{2}/\delta)}$ for
some universal constants $c_{1}$ and $c_{2}$, and
$B=\max_{c\in\mathcal{C}}B_{c}$ for the bounds $B_{c}$ on the outcomes defined
in Assumption 1. The last inequality follows from a uniform bound on
$\Gamma_{i}^{c\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime}(\pi_{b}(X_{i}^{c}))$.

We follow the exact same argument as above to get

$\displaystyle\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}}\operatorname{\mathbb{E}}\left[||\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c})-w_{c}(X_{i}^{c})||^{2}\mid\hat{w}_{c}^{-k_{c}(i)}\right]$
$\displaystyle\leq o\left(\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}\right).$

Therefore,

$\displaystyle\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{2}^{k}(\pi_{a},\pi_{b})\right|$
$\displaystyle\leq
C_{\Pi,\delta}\sqrt{\frac{4B}{K}\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}}\operatorname{\mathbb{E}}\left[||\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c})-w_{c}(X_{i}^{c})||_{2}^{2}\mid\hat{w}_{c}^{-k_{c}(i)}\right]}+o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right)$
$\displaystyle\leq C_{\Pi,\delta}\sqrt{\frac{4B}{K}\cdot
o\left(\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}\right)}+o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right)$
$\displaystyle\leq
o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right),$

and

$\displaystyle\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{2}(\pi_{a},\pi_{b})\right|$
$\displaystyle\leq\sum_{k=1}^{K}\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{2}^{k}(\pi_{a},\pi_{b})\right|\leq
o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right).$

Bounding $S_{3}$: Next, we bound the contribution from $S_{3}$. We have that

$\displaystyle\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{3}(\pi_{a},\pi_{b})\right|$
$\displaystyle=\sup_{\pi_{a},\pi_{b}\in\Pi}\left|\sum_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}}\sum_{i=1}^{n_{c}}\Gamma_{i}^{c\prime\prime\prime}(\pi_{a}(X_{i}^{c}))-\Gamma_{i}^{c\prime\prime\prime}(\pi_{b}(X_{i}^{c}))\right|$
$\displaystyle\leq
2\left|\sum_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}}\sum_{i=1}^{n_{c}}\sum_{a\in\mathcal{A}}\left(\mu_{c}(X_{i}^{c};a)-\hat{\mu}_{c}^{-k_{c}(i)}(X_{i}^{c};a)\right)\left(\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c};a)-w_{c}(X_{i}^{c};a)\right)\right|$
$\displaystyle\leq
2\sqrt{\sum_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}}\sum_{i=1}^{n_{c}}\big{\lVert}\mu_{c}(X_{i}^{c})-\hat{\mu}_{c}^{-k_{c}(i)}(X_{i}^{c})\big{\rVert}_{2}^{2}}\sqrt{\sum_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}}\sum_{i=1}^{n_{c}}\big{\lVert}\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c})-w_{c}(X_{i}^{c})\big{\rVert}_{2}^{2}}$
$\displaystyle\leq
2\sqrt{\sum_{c\in\mathcal{C}}\lambda_{c}\frac{g_{c}(\alpha_{K}n_{c})}{(\alpha_{K}n_{c})^{\zeta_{\mu}}}}\sqrt{\sum_{c\in\mathcal{C}}\lambda_{c}\frac{g_{c}(\alpha_{K}n_{c})}{(\alpha_{K}n_{c})^{\zeta_{w}}}}$
$\displaystyle\leq\frac{2}{\alpha_{K}^{({\zeta_{\mu}}+{\zeta_{w}})/2}}\sqrt{\max_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}^{\zeta_{\mu}}}\sum_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})}\sqrt{\max_{c\in\mathcal{C}}\frac{\lambda_{c}}{n_{c}^{\zeta_{w}}}\sum_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})}$
$\displaystyle=\frac{2}{\alpha_{K}^{({\zeta_{\mu}}+{\zeta_{w}})/2}}\sum_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})\sqrt{\max_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}^{{\zeta_{\mu}}+{\zeta_{w}}}}}$
$\displaystyle\leq\frac{2}{\alpha_{K}^{({\zeta_{\mu}}+{\zeta_{w}})/2}}\sum_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})\sqrt{\max_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}}}$
$\displaystyle\leq\frac{2}{\alpha_{K}^{({\zeta_{\mu}}+{\zeta_{w}})/2}}\sum_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})\sqrt{\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{n_{c}}}$
$\displaystyle\leq\frac{2}{\alpha_{K}^{({\zeta_{\mu}}+{\zeta_{w}})/2}}\sum_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}.$

As discussed earlier, $g_{c}(\alpha_{K}n_{c})$ is asymptotically bounded by a
decreasing function of $n$. Since the sum of decreasing functions is
decreasing, $\sum_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})$ is asymptotically
bounded by a decreasing function $\tilde{g}$ in $n$. In other words,
$\sum_{c\in\mathcal{C}}g_{c}(\alpha_{K}n_{c})\leq\tilde{g}(n)\leq o(1)$.
Therefore,

$\displaystyle\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{3}(\pi_{a},\pi_{b})\right|\leq\frac{2}{\alpha_{K}^{({\zeta_{\mu}}+{\zeta_{w}})/2}}\cdot
o(1)\cdot\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\leq
o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right).$

Putting all the above bounds together, we have

$\displaystyle\sup_{\pi_{a},\pi_{b}\in\Pi}|\tilde{\Delta}_{\lambda}(\pi_{a},\pi_{b})-\hat{\Delta}_{\lambda}(\pi_{a},\pi_{b})|$
$\displaystyle\leq\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{1}(\pi_{a},\pi_{b})+S_{2}(\pi_{a},\pi_{b})+S_{3}(\pi_{a},\pi_{b})\right|$
$\displaystyle\leq\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{1}(\pi_{a},\pi_{b})\right|+\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{2}(\pi_{a},\pi_{b})\right|+\sup_{\pi_{a},\pi_{b}\in\Pi}\left|S_{3}(\pi_{a},\pi_{b})\right|$
$\displaystyle\leq
o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right).$

∎

###  C.5 Proof of Theorem 5.2

*

###### Proof.

Let $\pi^{*}_{\lambda}=\operatorname*{arg\,max}_{\pi\in\Pi}Q_{\lambda}(\pi)$.
Using the results of Propositions 2 and 3, with probability at least
$1-\delta$, we have

$\displaystyle R_{\lambda}(\hat{\pi}_{\lambda})$
$\displaystyle=Q_{\lambda}(\pi^{*}_{\lambda})-Q_{\lambda}(\hat{\pi}_{\lambda})$
$\displaystyle=\big{(}Q_{\lambda}(\pi^{*}_{\lambda})-Q_{\lambda}(\hat{\pi}_{\lambda})\big{)}-\big{(}\hat{Q}_{\lambda}(\pi^{*}_{\lambda})-\hat{Q}_{\lambda}(\hat{\pi}_{\lambda})\big{)}+\big{(}\hat{Q}_{\lambda}(\pi^{*}_{\lambda})-\hat{Q}_{\lambda}(\hat{\pi}_{\lambda})\big{)}$
$\displaystyle=\Delta_{\lambda}(\pi^{*}_{\lambda},\hat{\pi}_{\lambda})-\hat{\Delta}_{\lambda}(\pi^{*}_{\lambda},\hat{\pi}_{\lambda})+\big{(}\hat{Q}_{\lambda}(\pi^{*}_{\lambda})-\hat{Q}_{\lambda}(\hat{\pi}_{\lambda})\big{)}$
$\displaystyle\leq\Delta_{\lambda}(\pi^{*}_{\lambda},\hat{\pi}_{\lambda})-\hat{\Delta}_{\lambda}(\pi^{*}_{\lambda},\hat{\pi}_{\lambda})$
$\displaystyle\leq\sup_{\pi_{a},\pi_{b}\in\Pi}|\Delta_{\lambda}(\pi_{a},\pi_{b})-\hat{\Delta}_{\lambda}(\pi_{a},\pi_{b})|$
$\displaystyle\leq\sup_{\pi_{a},\pi_{b}\in\Pi}|\Delta_{\lambda}(\pi_{a},\pi_{b})-\tilde{\Delta}_{\lambda}(\pi_{a},\pi_{b})|+\sup_{\pi_{a},\pi_{b}\in\Pi}|\tilde{\Delta}_{\lambda}(\pi_{a},\pi_{b})-\hat{\Delta}_{\lambda}(\pi_{a},\pi_{b})|$
$\displaystyle\leq\left(\left(c_{1}\kappa(\Pi)+\sqrt{c_{2}\log(c_{2}/\delta)}\right)\sqrt{\frac{V_{\lambda,n_{\mathcal{C}}}}{n}}+o\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right)\right)+o_{p}\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right)$
$\displaystyle\leq\left(c_{1}\kappa(\Pi)+\sqrt{c_{2}\log(c_{2}/\delta)}\right)\sqrt{\frac{V_{\lambda,n_{\mathcal{C}}}}{n}}+o_{p}\left(\sqrt{\frac{\mathfrak{s}(\lambda\|\bar{n})}{n}}\,\right),$

where $c_{1}$ and $c_{2}$ are universal constants. Lastly, we decompose the
weighted variance term by

$\displaystyle V_{\lambda,n_{\mathcal{C}}}$
$\displaystyle=\sup_{\pi_{a},\pi_{b}\in\Pi}\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{\bar{n}_{c}}\operatorname*{\mathbb{E}}_{Z^{c}\sim\bar{\mathcal{D}}_{c}}\big{[}\big{(}\Gamma^{c}(\pi_{a}(X^{c}))-\Gamma^{c}(\pi_{b}(X^{c}))\big{)}^{2}\big{]}$
$\displaystyle\leq\max_{c\in\mathcal{C}}\sup_{\pi_{a},\pi_{b}\in\Pi}\operatorname*{\mathbb{E}}_{Z^{c}\sim\bar{\mathcal{D}}_{c}}\big{[}\big{(}\Gamma^{c}(\pi_{a}(X^{c}))-\Gamma^{c}(\pi_{b}(X^{c}))\big{)}^{2}\big{]}\cdot\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{\bar{n}_{c}}$
$\displaystyle\leq
4\cdot\max_{c\in\mathcal{C}}\sup_{\pi\in\Pi}\operatorname*{\mathbb{E}}_{Z^{c}\sim\bar{\mathcal{D}}_{c}}[{\Gamma^{c}(\pi(X^{c}))}]\cdot\sum_{c\in\mathcal{C}}\frac{\lambda_{c}^{2}}{\bar{n}_{c}}$
$\displaystyle=4V\cdot\mathfrak{s}(\lambda\|\bar{n}).$

We absorb the factor of $\sqrt{4}$ into the universal constants to get the
desired result. ∎

##  Appendix D Bounding Local Regret

###  D.1 Proof of Theorem 5.3

*

###### Proof.

Let $\pi^{*}_{c}=\operatorname*{arg\,max}_{\pi\in\Pi}Q_{c}(\pi)$. Then,

$\displaystyle R_{c}(\hat{\pi}_{\lambda})$
$\displaystyle=Q_{c}(\pi^{*}_{c})-Q_{c}(\hat{\pi}_{\lambda})$
$\displaystyle=Q_{c}(\pi^{*}_{c})-Q_{c}(\hat{\pi}_{\lambda})\mp
Q_{\lambda}(\pi^{*}_{c})\pm Q_{\lambda}(\hat{\pi}_{\lambda})$
$\displaystyle=\big{(}Q_{c}(\pi^{*}_{c})-Q_{\lambda}(\pi^{*}_{c})\big{)}+\big{(}Q_{\lambda}(\hat{\pi}_{\lambda})-Q_{c}(\hat{\pi}_{\lambda})\big{)}+\big{(}Q_{\lambda}(\pi^{*}_{c})-Q_{\lambda}(\hat{\pi}_{\lambda})\big{)}$
$\displaystyle\leq
2\sup_{\pi\in\Pi}\left|Q_{c}(\pi)-Q_{\lambda}(\pi)\right|+\big{(}Q_{\lambda}(\pi^{*}_{c})-Q_{\lambda}(\hat{\pi}_{\lambda})\big{)}$
$\displaystyle\leq
2\sup_{\pi\in\Pi}\left|Q_{c}(\pi)-Q_{\lambda}(\pi)\right|+\big{(}Q_{\lambda}(\pi^{*}_{\lambda})-Q_{\lambda}(\hat{\pi}_{\lambda})\big{)}$
$\displaystyle=2\sup_{\pi\in\Pi}\left|Q_{c}(\pi)-Q_{\lambda}(\pi)\right|+R_{\lambda}(\hat{\pi}_{\lambda}).$

By Lemma 6, we can express the the local policy value as

$\displaystyle
Q_{c}(\pi)=\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{c}}\left[\Gamma(\pi(X))\right]$

where $(\Gamma(a_{1}),\dots,\Gamma(a_{d}))$ are the constructed AIPW scores
from a context-action-outcomes sample
$Z=(X,A,Y(a_{1}),\dots,Y(a_{d}))\sim\bar{\mathcal{D}}_{c}$. In addition, the
global policy value can be expressed as

$\displaystyle
Q_{\lambda}(\pi)=\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{\lambda}}\left[\Gamma(\pi(X))\right].$

where $(\Gamma(a_{1}),\dots,\Gamma(a_{d}))$ are the constructed AIPW scores
from a context-action-outcomes sample $Z=(X,A,Y(a_{1}),\dots,Y(a_{d}))$ such
that $c\sim\lambda$ and then $Z\sim\bar{\mathcal{D}}_{c}$. Therefore,

$\displaystyle\sup_{\pi\in\Pi}\left|Q_{c}(\pi)-Q_{\lambda}(\pi)\right|$
$\displaystyle=\sup_{\pi\in\Pi}\Big{|}\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{c}}[\Gamma(\pi(X))]-\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{\lambda}}[\Gamma(\pi(X))]\Big{|}$
(31)

By the boundedness and overlap assumption in Assumption 1, one can easily
verify the uniform bound

$\left|\Gamma^{c}(a)\right|\leq B_{c}+2B_{c}/\eta_{c}\leq 3B_{c}/\eta_{c}\leq
3B/\eta\eqqcolon U$

for any constructed AIPW score $\Gamma^{c}(a)$ for any $a\in\mathcal{A}$ and
any client $c\in\mathcal{C}$. Therefore, Equation (31) is equivalent to the
integral probability metric distance [Sriperumbudur et al., 2009] between
$\bar{\mathcal{D}}_{c}$ and $\bar{\mathcal{D}}_{\lambda}$ under uniformly
bounded test functions

$\displaystyle\\{Q(T(\cdot);\pi)\mid\pi\in\Pi\\}\subset\mathcal{F}_{\infty}^{U}\coloneqq\\{f\mid\lVert
f\rVert_{\infty}\leq U\\},$

where $T(X,A,Y(a_{1}),\dots,Y(a_{d}))=(X,\Gamma(a_{1}),\dots,\Gamma(a_{d}))$.
Thus,

$\displaystyle\sup_{\pi\in\Pi}\left|Q_{c}(\pi)-Q_{\lambda}(\pi)\right|$
$\displaystyle=\sup_{\pi\in\Pi}\Big{|}\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{c}}\big{[}Q(T(Z);\pi)\big{]}-\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{\lambda}}\big{[}Q(T(Z);\pi)\big{]}\Big{|}$
$\displaystyle\leq\sup_{f\in\mathcal{F}_{\infty}^{U}}\Big{|}\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{c}}\big{[}f(Z)\big{]}-\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{\lambda}}\big{[}f(Z)\big{]}\Big{|}$
$\displaystyle=U\cdot\operatorname{TV}(\bar{\mathcal{D}}_{c},\bar{\mathcal{D}}_{\lambda}).$

The last equality holds by the definition of the total variation distance as
an integral probability metric with uniformly bounded test functions. ∎

###  D.2 Distribution Shift Bound

First, we state some important properties of the KL divergence.

######  Lemma 8.

The KL divergence has the following properties.

  * •

Tensorization Property: Let $\mathcal{P}=\prod_{i=1}^{m}\mathcal{P}_{i}$ and
$\mathcal{Q}=\prod_{i=1}^{m}\mathcal{Q}_{i}$ be two product distributions.
Then,

$\operatorname{KL}(\mathcal{P}||\mathcal{Q})=\sum_{i=1}^{m}\operatorname{KL}(\mathcal{P}_{i}||\mathcal{Q}_{i}).$

  * •

Chain Rule: Let $\mathcal{P}_{XY}=\mathcal{P}_{X}\mathcal{P}_{Y|X}$ and
$\mathcal{Q}_{XY}=\mathcal{Q}_{X}\mathcal{Q}_{Y|X}$ be two distributions for a
pair of random variables $X,Y$. Then,

$\operatorname{KL}(\mathcal{P}_{XY}||\mathcal{Q}_{XY})=\operatorname{KL}(\mathcal{P}_{X}||\mathcal{Q}_{X})+\operatorname{KL}(\mathcal{P}_{Y|X}||\mathcal{Q}_{Y|X}\mid\mathcal{P}_{X})$

where

$\operatorname{KL}(\mathcal{P}_{Y|X}||\mathcal{Q}_{Y|X}\mid\mathcal{P}_{X})=\operatorname*{\mathbb{E}}_{X\sim\mathcal{P}_{X}}\left[\operatorname{KL}(\mathcal{P}_{Y|X}||\mathcal{Q}_{Y|X})\right].$

Then, we can use these properties to additively separate the sources of
distribution shift in our local regret bound.

*

###### Proof.

For any $c\in\mathcal{C}$, the joint probability density function of
$\bar{\mathcal{D}}_{c}$ factorizes as

$\displaystyle
p_{X^{c},A^{c},\vec{Y}^{c}}(x,a,y)=p_{X^{c}}(x)e_{c}(a|x)p_{\vec{Y}^{c}|X^{c},A^{c}}(y|x,a)=p_{X^{c}}(x)e_{c}(a|x)p_{\vec{Y}^{c}|X^{c}}(y|x)$

for any $(x,a,y)\in\mathcal{X}\times\mathcal{A}\times\mathcal{Y}^{d}$, where
the last equality holds by the unconfoundedness property stated in Assumption
1. Next, let $\Sigma$ be the $\sigma$-field over
$\mathcal{X}\times\mathcal{A}\times\mathcal{Y}^{d}$ on which the
$\bar{\mathcal{D}}_{c}$ are defined. We have that

$\displaystyle\operatorname{TV}(\bar{\mathcal{D}}_{c},\bar{\mathcal{D}}_{\lambda})$
$\displaystyle=\sup_{A\subset\Sigma}\big{|}\bar{\mathcal{D}}_{c}(A)-\bar{\mathcal{D}}_{\lambda}(A)\big{|}$
$\displaystyle=\sup_{A\in\Sigma}\big{|}\bar{\mathcal{D}}_{c}(A)-\sum_{c\in\mathcal{C}}\lambda_{c}\bar{\mathcal{D}}_{k}(A)\big{|}$
$\displaystyle=\sup_{A\in\Sigma}\big{|}\sum_{c\in\mathcal{C}}\lambda_{c}\left(\bar{\mathcal{D}}_{c}(A)-\bar{\mathcal{D}}_{k}(A)\right)\big{|}$
$\displaystyle\leq\sup_{A\in\Sigma}\sum_{c\in\mathcal{C}}\lambda_{c}\big{|}\bar{\mathcal{D}}_{c}(A)-\bar{\mathcal{D}}_{k}(A)\big{|}$
$\displaystyle\leq\sum_{c\in\mathcal{C}}\lambda_{c}\sup_{A\in\Sigma}\big{|}\bar{\mathcal{D}}_{c}(A)-\bar{\mathcal{D}}_{k}(A)\big{|}$
$\displaystyle=\operatorname*{\mathbb{E}}_{k\sim\lambda}\left[\operatorname{TV}(\bar{\mathcal{D}}_{c},\bar{\mathcal{D}}_{k})\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{k\sim\lambda}\left[\sqrt{\operatorname{KL}(\bar{\mathcal{D}}_{c}||\bar{\mathcal{D}}_{k})}\,\right],$

where the last inequality holds by Pinsker’s inequality. Moreover,

$\displaystyle\operatorname{KL}(\bar{\mathcal{D}}_{c}||\bar{\mathcal{D}}_{k})$
$\displaystyle=\operatorname{KL}(p_{X^{c},A^{c},\vec{Y}^{c}}||p_{X_{k},A_{k},\vec{Y}_{k}})$
$\displaystyle=\operatorname{KL}(p_{X^{c}}||p_{X^{k}})+\operatorname{KL}(e_{c}p_{\vec{Y}^{c}|X^{c}}||e_{k}p_{\vec{Y}^{k}|X^{k}}\mid
p_{X^{c}})$
$\displaystyle=\operatorname{KL}\big{(}p_{X^{c}}||p_{X^{k}}\big{)}+\operatorname{KL}\big{(}e_{c}||e_{k}\mid
p_{X^{c}}\big{)}+\operatorname{KL}\big{(}p_{\vec{Y}^{c}|X^{c}}||p_{\vec{Y}^{k}|X^{k}}\mid
p_{X^{c}}\big{)},$

where the first equality holds by the chain rule of the KL divergence and the
second equality holds by the tensorization property of KL divergence. ∎

###  D.3 Alternative Local Regret Bound

We provide an alternative local regret bound that is applicable in scenarios
where the AIPW score variance is significantly less than the AIPW score range.

######  Theorem 1.

Suppose Assumption 1 holds. Then, for any $c\in\mathcal{C}$,

$R_{c}(\hat{\pi}_{\lambda})\leq\sqrt{\smash[b]{4V\cdot\chi^{2}(\bar{\mathcal{D}}_{c}||\bar{\mathcal{D}}_{\lambda})}}+R_{\lambda}(\hat{\pi}_{\lambda}),$

where
$V=\max_{c\in\mathcal{C}}\sup_{\pi\in\Pi}\operatorname{\mathbb{E}}_{\bar{\mathcal{D}}_{c}}[\Gamma^{c}(\pi(X^{c}))]$.

###### Proof.

As shown in Theorem 5.3,

$\displaystyle R_{c}(\hat{\pi}_{\lambda})\leq
2\sup_{\pi\in\Pi}|Q_{c}(\pi)-Q_{\lambda}(\pi)|+R_{\lambda}(\hat{\pi}_{\lambda}).$

Thus, we seek a new bound on the first term due to distribution shift.

Let $p_{c}(z)$ and $p_{\lambda}(z)$ for any
$z\in\mathcal{X}\times\mathcal{A}\times\mathcal{Y}^{d}$ be the joint
probability density functions of $\bar{\mathcal{D}}_{c}$ and
$\bar{\mathcal{D}}_{\lambda}$, respectively. Additionally, for any
$c\in\mathcal{C}$ and any $Z\sim\bar{\mathcal{D}}_{c}$, let
$f(Z;\pi)=\Gamma^{c}(\pi(X^{c}))$. Then, we can do the following calculations
to get

$\displaystyle\sup_{\pi\in\Pi}\left|Q_{c}(\pi)-Q_{\lambda}(\pi)\right|$
$\displaystyle=\sup_{\pi\in\Pi}\left|\operatorname*{\mathbb{E}}_{Z^{c}\sim\bar{\mathcal{D}}_{c}}[\Gamma^{c}(\pi(X^{c}))]-\operatorname*{\mathbb{E}}_{c\sim\lambda}\operatorname*{\mathbb{E}}_{Z^{c}\sim\bar{\mathcal{D}}_{c}}[\Gamma^{c}(\pi(X^{c}))]\right|$
$\displaystyle=\sup_{\pi\in\Pi}\left|\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{c}}[f(Z;\pi)]-\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{\lambda}}[f(Z;\pi)]\right|$
$\displaystyle=\sup_{\pi\in\Pi}\left|\int f(z;\pi)p_{c}(z)dz-\int
f(z;\pi)p_{\lambda}(z)dz\right|$ $\displaystyle=\sup_{\pi\in\Pi}\left|\int
f(z;\pi)\sqrt{p_{\lambda}(z)}\left(\frac{p_{c}(z)-p_{\lambda}(z)}{\sqrt{p_{\lambda}(z)}}\right)dz\right|$
$\displaystyle\leq\sup_{\pi\in\Pi}\sqrt{\int
f(z;\pi)^{2}p_{\lambda}(z)dz\cdot\int\frac{(p_{c}(z)-p_{\lambda}(z))^{2}}{p_{\lambda}(z)}dz}$
$\displaystyle=\sup_{\pi\in\Pi}\sqrt{\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{\lambda}}[f(Z;\pi)^{2}]\cdot\chi^{2}(\bar{\mathcal{D}}_{c}||\bar{\mathcal{D}}_{\lambda})}$
$\displaystyle\leq\sup_{\pi\in\Pi}\sqrt{\max_{c\in\mathcal{C}}\operatorname*{\mathbb{E}}_{Z\sim\bar{\mathcal{D}}_{c}}[\Gamma^{c}(\pi(X^{c}))^{2}]\cdot\chi^{2}(\bar{\mathcal{D}}_{c}||\bar{\mathcal{D}}_{\lambda})}$
$\displaystyle=\sqrt{V\cdot\chi^{2}(\bar{\mathcal{D}}_{c}||\bar{\mathcal{D}}_{\lambda})}.$

Thus, we get the desired result. ∎

Compare the distribution shift term in this alternate result to the
distribution shift term
$U\cdot\operatorname{TV}(\bar{\mathcal{D}}_{c},\bar{\mathcal{D}}_{\lambda})$
in the local regret bound we established in Theorem 5.3. The alternate bound
is useful in that it does not rely on bounded AIPW scores, and instead is
scaled by the maximum variance of the AIPW scores, which may be smaller than
the range and it also appears in our global regret bound. Therefore, it is a
more natural bound in this sense. However, the chi-squared divergence does not
have a chain rule that would allow us to additively separate the sources of
distribution shift in this bound, as we did in Proposition 5.3. The reason for
this limitation is that the chi-squared divergence cannot be bounded by the KL
divergence to leverage its chain rule as we did for the TV distance. In this
sense, this alternate bound is not useful for elucidating the contributions of
distribution shift in the local regret bound.

##  Appendix E Value of Information

The local regret bound result in Theorem 5.3 is useful to capture the value of
information provided by the central server. Suppose a given client
$c\in\mathcal{C}$ has agency to decide whether to participate in the federated
system including all other clients. If we consider the client as a local
regret-minimizing agent, we can use the dominant terms in the appropriate
local regret bounds to model the expected utility of the client. In
particular, using prior results of standard offline policy learning [Zhou et
al., 2022] and our findings in Theorems 5.2 and 5.3, the value of information
provided by the central server can be modeled as the comparison of the
client’s utility (as captured by the negative local regret) with and without
participation

$\mathcal{V}_{c}(\lambda)=C_{0}\kappa(\Pi)\sqrt{V_{c}/n_{c}}-C_{1}\kappa(\Pi)\sqrt{V\mathfrak{s}(\lambda\|\bar{n})/n}-U\cdot\operatorname{TV}(\bar{\mathcal{D}}_{c},\bar{\mathcal{D}}_{\lambda}),$

where $C_{0},C_{1}$ are universal constants and
$V_{c}=\sup_{\pi\in\Pi}\operatorname{\mathbb{E}}[\Gamma^{c}(\pi(X^{c}))^{2}]$
is the local AIPW variance.

Then, we say it is more valuable for client $c$ to participate in federation
if $\mathcal{V}_{c}(\lambda)>0$. One can easily show that this condition is
satisfied if and only if

$\operatorname{TV}(\bar{\mathcal{D}}_{c},\bar{\mathcal{D}}_{\lambda})<\alpha
r_{c}/U\quad\land\quad\mathfrak{s}(\lambda\|\bar{n})<\beta^{2}r_{c}^{2}/r^{2}$

for some $\alpha+\beta\leq 1$, where
$r_{c}=C_{0}\kappa(\Pi)\sqrt{\smash[b]{V_{c}/n_{c}}}$ is the local regret
bound of the locally trained model and
$r=C_{1}\kappa(\Pi)\sqrt{\smash[b]{V/n}}$ is the global regret bound of the
globally trained model under no skewness. The $\alpha$ and $\beta$ factors
indicate a trade-off between distribution shift and skewness of the two
conditions. If there is low distribution shift, the skewness can be large.

Thus, we see how the design choice on the client distribution must balance a
scaled trade-off to achieve relative low skewness and relative low expected
distribution shift. Indeed, in the experiments in Section 7 we see how a
skewed client distribution can help improve the local regret guarantees of a
heterogeneous client. We observe from the first condition that the client
distribution shift must must be smaller than the local regret of the locally
trained model relative to a scaled range of the data. Intuitively, this states
that the client will not benefit from federation if the regret they suffer due
to their distribution shift from the global mixture distribution is greater
than the relative local regret from just training locally. The second
condition states that the skewness must be less than the local regret relative
to the global regret. Large relative variance or small relative sample size
are the primary factors that can lead small relative regret and therefore
tight limitations on skewness budget. Overall, all of these conditions can be
satisfied under sufficiently low expected distribution shift from the global
distribution, low client distribution skewness, comparable AIPW variance
across clients, and large global sample size relative to the local sample
size.

However, it should be noted that this analysis simplifies the setting by
considering only a single client that unilaterally decides to participate in
the federation, without considering the choices of other clients. A more
comprehensive analysis would assess the value of information provided by the
central server in an equilibrium of clients with agency to participate. Game-
theoretic aspects are crucial in this context, necessitating an understanding
of client behavior and incentives in federated settings. Recent research has
started to delve into game-theoretic considerations in federated supervised
learning. Donahue and Kleinberg [2021] provided valuable insights into the
behavior of self-interested, error-minimizing clients forming federated
coalitions to learn supervised models. Moreover, designing incentive
mechanisms in federated learning has been identified as a significant research
area [Zhan et al., 2021b]. This work aims to understand the optimal ways to
incentivize clients to share their data. Applying these concepts to our
setting would offer valuable insights on the incentives and behavior that
motivate clients to participate in federated policy learning systems.

##  Appendix F Additional Algorithm Details

###  F.1 Nuisance Parameter Estimation

Our results rely on efficient estimation of $Q_{\lambda}(\pi)$ for any policy
$\pi$, which in turn relies on efficient estimation of $Q_{c}(\pi)$. We
leverage ideas of double machine learning [Chernozhukov et al., 2018] to
guarantee efficient policy value estimation given only high-level conditions
on the predictive accuracy of machine learning methods on estimating the
nuisance parameters of doubly robust policy value estimators. In this work, we
use machine learning and cross-fitting strategies to estimate the nuisance
parameters locally. The nuisance parameter estimates must satisfy the
conditions of Assumption 3. Under these conditions, extensions of the results
of [Chernozhukov et al., 2018, Athey and Wager, 2021] would imply that the
doubly robust local policy value estimates $\hat{Q}_{c}(\pi)$ for any policy
$\pi$ are asymptotically efficient for estimating $Q_{c}(\pi)$.

The conditions and estimators that guarantee these error assumptions have been
extensively studied in the estimation literature. These include parametric or
smoothness assumptions for non-parametric estimation. The conditional response
function
$\mu_{c}(x;a)=\operatorname{\mathbb{E}}_{\bar{\mathcal{D}}_{c}}[Y^{c}(a)|X^{c}=x]$
can be estimated by regressing observed rewards on observed contexts. The
inverse conditional propensity function
$w_{c}(x;a)=1/\operatorname{\mathbb{P}}_{\bar{\mathcal{D}}_{c}}(A^{c}=a|X^{c}=x)$
can be estimated by estimating the conditional propensity function
$e_{c}(x;a)=\operatorname{\mathbb{P}}_{\bar{\mathcal{D}}_{c}}(A^{c}=a|X^{c}=x)$
and then taking the inverse. Under sufficient regularity and overlap
assumptions, this gives accurate estimates. We can take any flexible approach
to estimate these nuisance parameters. We could use standard parametric
estimation methods like logistic regression and linear regression, or we could
use non-parametric methods like classification and regression forests to make
more conservative assumptions on the true models. Lastly, we note that if it
is known that some clients have the same data-generating distribution, it
should be possible to learn the nuisance parameters across similar clients.

In our experiments, we decided to estimate the $\mu_{c}$ with linear
regression and $e_{c}$ with logistic regression. We used the sklearn Python
package to fit the nuisance parameters. The true expected rewards are non-
linear but the propensities are simple uniform probabilities. So our
experiments emulate the scenario where accurate estimation of $\mu_{c}$ is not
perfectly possible but accurate estimation of $e_{c}$ is easy, thus leveraging
the properties of double machine learning for policy value estimation.

###  F.2 Cross-fitted AIPW Estimation

Once the nuisance parameters are estimated, they can be used for estimating
AIPW scores. Refer to Algorithm 3 for the pseudocode on how we conduct the
cross-fitting strategy for AIPW score estimation. Under this strategy, each
client $c\in\mathcal{C}$ divides their local dataset into $K$ folds, and for
each fold $k$, the client estimates $\mu_{c}$ and $w_{c}$ using the rest $K-1$
folds. During AIPW estimation for a single data point, the nuisance parameter
estimate that is used in the AIPW estimate is the one that was not trained on
the fold that contained that data point.

Algorithm 3 Cross-fitted AIPW: Client-Side

0: local data $\\{(X_{i}^{c},A_{i}^{c},Y_{i}^{c})\\}_{i=1}^{n_{c}}$, number of
folds $K$

1: Partition local data into $K$ folds

2: Define surjective mapping $k_{c}:[n_{c}]\to[K]$ of point index to
corresponding fold index

3: for $k=1,\dots,K$ do

4: Fit estimators $\hat{\mu}_{c}^{-k}$ and $\hat{w}_{c}^{-k}$ using rest of
data not in fold $k$

5: end for

6: for $i=1,\dots,n_{c}$ do

7: for $a\in\mathcal{A}$ do

8:
$\hat{\Gamma}_{i}^{c}(a)\leftarrow\hat{\mu}_{c}^{-k_{c}(i)}(X_{i}^{c};a)+\big{(}Y_{i}^{c}-\hat{\mu}_{c}^{-k_{c}(i)}(X_{i}^{c};a)\big{)}\cdot\hat{w}_{c}^{-k_{c}(i)}(X_{i}^{c};a)\cdot\mathbf{1}\\{A_{i}^{c}=a\\}$

9: end for

10: end for

###  F.3 Implementation Details

The local optimization problems we face in our formulation in Section 6 are
equivalent to cost-sensitive multi-class classification (CSMC). There are many
off-the-shelf methods available for such problem. We rely on implementations
that can do fast online learning for parametric models in order to be able to
do quick iterated updates on the global models at each local client and send
these models for global aggregation. So we make use of the cost-sensitive one-
against-all (CSOAA) implementation for cost-sensitive multi-class
classification in the Vowpal Wabbit library [Langford et al., 2023]. This
implementation performs separate online regressions of costs on contexts for
each action using stochastic gradient descent updates. At inference time, to
make an action prediction, the action whose regressor gives the lowest
predicted cost is chosen.

The idea behind this method is that if the classifiers admit regression
functions that predict the costs, i.e.,
$\pi_{\theta}(x)=\operatorname*{arg\,max}_{a\in\mathcal{A}}f_{\theta}(x;a)$
for some $f_{\theta}\in\mathcal{F}_{\Theta}$ such that
$f^{*}(x;a)\in\mathcal{F}_{\Theta}$ where
$f^{*}(x;a)=\operatorname{\mathbb{E}}[\smash[t]{\Gamma^{c}(a)}|X^{c}=x]$, then
efficient regression oracles will return an (near) optimal model [Agarwal et
al., 2017]. If realizability does not hold one may need to use more
computationally expensive CSMC optimization techniques [Beygelzimer et al.,
2009]. For example, we could use the weighted all pairs (WAP) algorithm
[Beygelzimer et al., 2008] that does $\binom{d}{2}$ pairwise binary
classifications and predicts the action that receives majority predictions.
Unlike the CSOAA implementation, the WAP method is always consistent in that
an optimal model for the reduced problem leads to an optimal cost-sensitive
prediction classifier. In our experiments, the rewards are non-linear so
realizability does not exactly hold. Yet, we still observe good performance
with the CSOAA regression-based algorithm.

##  Appendix G Additional Experimental Results

We follow up on the simulations with heterogeneous clients in Section 7. Here,
we observe the regret performance for one of the other clients that have less
distribution shift from the average. Figure 3(a) plots the local regret for
client 2 of the globally trained policy (green) and the global regret of the
globally trained policy (orange), all using the empirical mixture
$\lambda=\bar{n}$. For comparison, we also plot the local regret for client 2
of the locally trained policy (blue). The bands show the one standard
deviation from the regrets over five different runs. As expected, we see that
the other clients have less distribution shift so the local regret of the
global policy nearly matches the global regret, similar to what was observed
in the homogeneous experiments but with some level of degradation. Indeed, the
local distributions nearly match the global distribution, by construction. In
Figure 3(b) we plot the same type of regret curves, but instead with the
global policy trained with the skewed mixture. We see that their performance
degrades. This is in contrast to what we observe for client 1 where the skewed
mixture improved performance. This is because, we are increasing distribution
shift as measured by
$\operatorname{TV}(\bar{\mathcal{D}}_{c},\bar{\mathcal{D}}_{\lambda})$. This
is another indicator that our theoretical regret guarantees may be tight.

(a) Heterogeneous Clients, $\lambda=\bar{n}$

(b) Heterogeneous Clients, $\lambda=\bar{n}+\bar{\varepsilon}$

Figure 3: Empirical regret curves for simulation experiments. Local regrets
are for client 2.

##  Appendix H Additional Discussion

###  H.1 Policy Value Estimation

One may ask why we need efficient policy value estimation, especially under
realizability assumptions, when we can just estimate the conditional response
function over the class of regressors. One of the issues is the fact that the
data was collected under the historical policy which may not necessarily be
the target optimal policy so the estimating the reward function may lead to
policies that are optimal for locations in the decision space where the reward
function was able to have been well estimated given the historical data, but
the guarantees on data sampled on the optimal target policy may not be as
robust.

However, there is another another practical reason. [Kitagawa and Tetenov,
2018, Athey and Wager, 2021] provide a good discussion on why separating the
assumptions for the nuisance parameters and the class of policies is helpful,
and in some cases necessary, component of a comprehensive analysis of policy
learning. For one, since the nuisance components are inherent quantities of
the distributions are not in control by the central learner, it is a prudent
choice to make the least functional form assumptions on these parameters. In
contrast, the class of policies $\Pi$ is specified by the central learner and
can be used to impose restrictions on the type of policies. For example, for
privacy reasons, the central server can impose restrictions on what covariates
can be used to learn a policy, such as personally identifiable information.
This used in conjunction with federated learning strategies can leverage the
use of high-capacity flexible models to learn nuisance parameters locally
under no restrictions, but then the central server can impose restrictions on
the type of models used for policy evaluation and learning.

###  H.2 Limitations & Future Work

There are various limitations to our present work that require further
consideration. We discuss some of these limitations in the main paper. We
provide a slightly more exhaustive list here.

  * •

We make certain assumptions on the data-generating process which may not
always be satisfied. Throughout the paper, we discussed how some of these
assumptions may be relaxed with additional investigations, such as relaxing
the boundedness and strict overlap assumption in the data-generating
distributions.

  * •

In this work, nuisance parameters are estimated locally. If it is known that
some clients have the same data-generating distribution, it should be possible
to learn the nuisance parameters across similar clients.

  * •

Although our framework offers a great leap towards privacy-preserving policy
learning, we did not consider additional differential privacy considerations
in this work. It would be worthwhile to explore the effects of differential
privacy on our regret analysis and empirical results.

  * •

Our optimization procedure depended on access to efficient online cost-
sensitive classification methods. There are many fast implementations that are
widely available, but these are restricted to particular parametric classes.
However, in many policy learning scenarios, especially in public policy where
decisions must be audited, simple tree-based policy classes are preferable.
Research on developing efficient federated tree-based policy learning
algorithms would be highly valuable for this problem setting. In general,
further research needs to be conducted on developing federated methods for
learning on general policy classes beyond simple parametric policies,
including tree-based policies, finite policies, and neural policies.

  * •

We assumed the mixture distribution $\lambda$ is known. We could extend our
work to a more agnostic setting where this mixture distribution is optimized.
This would also have implications on robustness and fairness of the global
policy.

  * •

The local regret bounds for each client were found to depend on an irreducible
term due to distribution shift. Can this irreducible regret be quantified in a
federated manner to allow servers to determine if any given client benefits
from federation?

  * •

In Section E, we discussed the value of information provided by the central
server to an individual client in the scenario where all clients are assumed
to be participating in federation. A more complete analysis would consider the
value of information in an equilibrium where all clients have agency to
participate, rather than just one client.

  * •

Lastly, we leave open the question of whether the bounds we establish are
regret optimal. Mohri et al. [2019] discuss how similar skewness-based bounds
for distributed supervised learning are optimal. Moreover, in the homogeneous
setting, our results immediately reduce to the regret optimal results obtained
in [Athey and Wager, 2021, Zhou et al., 2022]. Thus, there is an indication
that our bounds are regret optimal. We leave lower bounds for future work.

###  H.3 Broader Impact

The growing availability of user-specific data has enabled the era of
individualized services. This paradigm has found applications in a wide
variety of user-facing domains in healthcare, advertising, content
recommendation, online education, public policy, etc. One the one hand,
personalized service decisions can lead to improved outcomes for users. On the
other, it can lead to higher privacy risks, where adversarial agents can
exploit high-fidelity data and personalized services to target specific
individuals. Therefore, with the rise of personalized decision-making systems,
there needs to be commensurate development of frameworks and methods to
mitigate such privacy risks. Since offline policy learning has emerged as an
efficient method for learning personalized policies, it is essential that this
paradigm is introduced in more privacy-preserving frameworks. Our work
introduces an approach to make offline policy learning amenable to federated
learning, one of the most popular frameworks to supports personal data
ownership and privacy. Thus, the impact of our work is to enable the
development of personalized policy learning systems for the benefit of
stakeholders that are facing data ownership and privacy issues.


Department of Computer Science, ETH Zürich,
<EMAIL_ADDRESS>Nicolas Grelier [100]computational
geometry Research supported by the Swiss National Science Foundation within
the collaborative DACH project _Arrangements and Drawings_ as SNSF Project
200021E-171681.

###### Acknowledgements.

The author thanks Michael Hoffmann for his helpful advice.John Q. Open and
Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT
2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Hardness and Approximation of Minimum Convex Partition

Nicolas Grelier

###### Abstract

We consider the Minimum Convex Partition problem: Given a set $P$ of $n$
points in the plane, draw a plane graph $G$ on $P$, with positive minimum
degree, such that $G$ partitions the convex hull of $P$ into a minimum number
of convex faces. We show that Minimum Convex Partition is NP-hard, and we give
a $\mathcal{O}(\sqrt{n}\log n)$-approximation algorithm running in quadratic
time. The latter result is obtained by relating the problem to another
geometric problem: Given a set of points $P$, cover $P$ with a minimum number
of lines.

A constant-factor approximation algorithm was shown for Minimum Convex
Partition by Knauer and Spillner, for point sets where no three points are on
a line (SWAT 2006). This restriction is crucial for the algorithm to work. The
complexity of the problem under this restriction remains open.

###### keywords:

computational geometry, points covering, non-crossing segments

###### category:

##  1 Introduction

The CG Challenge 2020 organised by Demaine, Fekete, Keldenich, Krupke and
Mitchell [6], is about solving instances of _Minimum Convex Partition_ (MCP).

######  Definition 1.1 (Demaine et al. [6]: Minimum Convex Partition problem).

Given a set $P$ of $n$ points in the plane. The objective is to compute a
plane graph with vertex set $P$ (with each point in $P$ having positive
degree) that partitions the convex hull of $P$ into the smallest possible
number of convex faces. Note that collinear points are allowed on face
boundaries, so all internal angles of a face are at most $\pi$.

As explained by Bose et al., this problem has applications in routing [2].
They showed that a routing algorithm named _Random-Compass_ that works for
triangulations can be extended to convex partitions. Having a convex partition
with few faces reduces the amount of data to store. From now on, we always
refer to $P$ as a set of $n$ points in the plane.

###  1.1 Exact and approximation algorithms

In the literature, the problem is usually studied in a restricted setting,
where no three points are on a line. If additionally one assumes that the
points lie on the boundaries of a fixed number of nested convex hulls, Fevens,
Meijer and Rappaport gave a polynomial time algorithm for solving MCP [10].

Keeping only the assumption that no three points are collinear, Knauer and
Spillner have shown in 2006 a $\frac{30}{11}$-approximation algorithm [14]. As
a lower bound on the number of convex faces for one particular point set, they
rely on the observation that each point not on the convex hull has degree at
least $3$. This gives a lower bound on the number of edges, and therefore on
the number of faces, by Euler’s formula. Note that the restriction that no
three points are on a line is necessary, as shown in Figure 1. There are only
two faces in a minimum convex partition of this point set, and all the inner
points have degree $2$.

•••••••••••• Figure 1: There are point sets with arbitrary many inner points
that can be partitioned in two convex faces.

Additionally, Knauer and Spillner showed how to adapt any constructive upper
bound in the number of faces into an approximation algorithm. More explicitly,
they showed that if one can compute in polynomial time a convex partition with
at most $\lambda n$ convex faces, then there exists a $2\lambda$-approximation
algorithm running in polynomial time. The best result to date is a proof by
Sakai and Urrutia that one can partition, in quadratic time, any point set
using at most $\frac{4}{3}n$ convex faces [21]. Although they do no mention
it, combining this result with the one by Knauer and Spillner gives a
quadratic time $\frac{8}{3}$-approximation algorithm.

Concerning previous results, Neumann-Lara, Rivero-Campo and Urrutia first
showed in 2004 how to construct in quadratic time a partition of any point set
with at most $\frac{10}{7}n$ convex faces [20]. In 2006, Knauer and Spillner
improved this to $\frac{15}{11}n$ convex faces [14]. As said above, the best
known upper bound is $\frac{4}{3}n$, as proven by Sakai and Urrutia in 2009.

Relatedly for lower bounds, García-Lopez and Nicolás have given in 2013 a
construction for point sets for which any convex partition has at least
$\frac{35}{32}n-\frac{3}{2}$ faces [11]. An integer linear programming
formulation of the problem, along with experimental results, has been recently
introduced by Barboza, Souza and Rezende [1].

All these results concerning upper bounds hold for all point sets, even where
many points are on a line. However, as mentioned above, the lower bound used
by Knauer and Spillner does not extend to our setting. They say a constant-
approximation algorithm would be desirable for unrestricted point sets, but so
far not even a $\mathcal{O}(n^{1-\varepsilon})$-approximation is known. In
this paper, we prove the following:

######  Theorem 1.2.

There exists a $\mathcal{O}(\sqrt{n}\log n)$-approximation algorithm for MCP
running in quadratic time.

Allowing several points to be on a line does not simply create some
technicalities to deal with. The crux of the matter is to find, for a fixed
point set, an exploitable lower bound on the number of faces in a minimum
convex partition. As said above, when no three points are on a line, the
number of inner points in $P$ gives a linear lower bound on the number of
faces in any convex partition. In this paper, we consider point sets with no
restriction. We show that finding a good approximation algorithm for MCP boils
down to finding one for _Covering Points with Non-Crossing Segments_ (CPNCS).
First, we define what _non-crossing segments_ are.

######  Definition 1.3 (Non-Crossing Segments).

We call _segment_ a part of a line bounded by two points, referred to as
_endpoints_ of the segment. Note that we do not force the endpoints to be
distinct, therefore we consider a point $p$ as being a segment. The endpoint
of $p$ is $p$ itself. Two segments are _non-crossing_ if the intersection of
their relative interior is empty.

######  Definition 1.4 (Covering Points with Non-Crossing Segments).

Given a set $P$ of $n$ points, find a minimum number of non-crossing segments
such that each point of $P$ is contained in at least one segment.

As mentioned, we introduce the CPNCS problem as it pinpoints where the
difficulty of finding a constant-approximation algorithm for MCP is and makes
the problem easier to study.

######  Theorem 1.5.

For any function $\phi$, if there exists a polynomial time
$\phi(n)$-approximation algorithm for MCP, then there exists a polynomial time
$48\phi(n+3)$-approximation algorithm for CPNCS. Reciprocally, the existence
of a $\phi(n)$-approximation algorithm for CPNCS implies the existence of a
$24\phi(n)$-approximation algorithm for MCP.

We believe that CPNCS is interesting in itself. Note that CPNCS is not a so-
called _set cover problem_ nor an _exact cover problem_. We call _greedy_
algorithm for CPNCS the algorithm that iteratively picks a new segment among
the valid ones that cover as many points not yet covered as possible, until
all points in $P$ are covered. As we consider points to be potential segments,
the algorithm terminates.

The CPNCS problem bears a resemblance with _Covering Points with Lines_ (CPL),
defined below, that we use in our algorithm.

######  Definition 1.6 (Covering Points with Lines).

Given a set $P$ of $n$ points, find a minimum number of lines such that each
point of $P$ is contained in at least one line.

The _greedy_ algorithm for CPL iteratively picks a line that covers as many
points not yet covered as possible. Note that in a solution to CPL, the lines
may intersect. Also, CPL is a _set cover problem_ , and can therefore be
approximated by the greedy algorithm within a factor of $\log n$, as shown by
Johnson and Lovász [12, 19].

The idea of our $\mathcal{O}(\sqrt{n}\log n)$-approximation algorithm is as
follows: For a point set $P$, compute a $\mathcal{O}(\log n)$-approximation
for CPL, transform it into a $\mathcal{O}(\sqrt{n}\log n)$-approximation for
CPNCS, and finally use Theorem 1.5 to compute from it a
$\mathcal{O}(\sqrt{n}\log n)$-approximation for MCP.

###  1.2 Concerning NP-hardness results

Fevens, Meijer and Rappaport first considered the MCP problem in 2001, and its
complexity was explicitly asked by Knauer and Spillner in 2006. It has
remained open since then [1, 6]. In this paper, we show that MCP is NP-hard.
To do this, we use the decision version of the problem, as stated below:

######  Definition 1.7 (MCP - decision version).

Given a set $P$ of points in the plane and a natural number $k$, is it
possible to find at most $k$ closed convex polygons whose vertices are points
of $P$, with the following properties:

  * •

The union of the polygons is the convex hull of $P$,

  * •

The interiors of the polygons are pairwise disjoint,

  * •

No polygon contains a point of $P$ in its interior.

We also show NP-hardness of a similar problem, which we call _Minimum Convex
Tiling_ problem (MCT). The problem is exactly as in Definition 1.7, but the
constraint about the vertices of the polygons is removed (i.e. they need not
be points of $P$). This can make a difference as shown in Figure 2.
Equivalently, the MCT problem corresponds to the MCP problem when Steiner
points are allowed. A _Steiner point_ is a point that does not belong to the
point set given as input, and which can be used as a vertex of some polygons.
The MCT problem has been studied in 2012 by Dumitrescu, Har-Peled and Tóth,
who showed a constant-approximation algorithm for point sets with no three
collinear points, and asked about the complexity of the problem [8]. We answer
their question, and our proofs are very similar for MCP and MCT.

•••••••••• Figure 2: A minimum partition with three convex polygons and a
tiling with two.

Our proof builds upon gadgets introduced by Lingas [18]. He used them to prove
NP-hardness of several decision problems, including _Minimum Convex Partition
for Polygons with Holes_ and _Minimum Rectangular Partition for Rectilinear
Polygons with Holes_. In the second problem, Steiner points are allowed.
However, as noted by Keil [13], one can easily adapt Lingas’ proof to not use
Steiner points. We use a similar idea to prove NP-hardness of the MCP problem.
Lingas’ proofs for the two problems are similar, and consist in a reduction
from the following variation of planar $3$-SAT. The instances are a CNF
formula $F$ with set of variables $X$ and set of clauses $C$, and a planar
bipartite graph $G=(X\cup C,E)$, such that there is an edge between a variable
$x\in X$ and a clause $c\in C$ if and only if $x$ or $\bar{x}$ is a literal of
$c$. Moreover, each clause contains either two literals or three, and if it
contains three, the clause must contain at least one positive and one negative
literal. Lingas refers to this decision problem as the _Modified Planar
$3$-SAT_ (MPLSAT). Lingas claims that planar satisfiability can easily be
reduced to MPLSAT by adding new variables. As planar satisfiability was shown
to be NP-complete by Lichtenstein [17], this would imply that MPLSAT is NP-
complete too. For the sake of completeness, we remark that it is not clear why
adding these new variables would not break the planarity of the graph. This
can be solved by considering the following lemma of Lichtenstein:

######  Lemma 1.8 (Lichtenstein [17]).

Planar satisfiability is still NP-complete even when, at every variable node,
all the arcs representing positive instances of the variable are incident to
one side of the node and all the arcs representing negative instances are
incident to the other side.

This lemma can easily be strengthened to the case of planar $3$-SAT as noted
by Lichtenstein, and explicitly done by Tippenhauer [22] in his Master’s
thesis. From here a reduction to MPLSAT becomes indeed straightforward.

######  Theorem 1.9.

MPLSAT can be reduced in polynomial time to MCP, and to MCT.

As it is easy to see that MCP is in NP, Theorem 1.9 implies that MCP is NP-
complete. The question whether MCT is in NP is still open. Let $P$ be a point
set, and let us consider the set $\mathcal{L}$ of all lines going through at
least two points in $P$. Let $P^{\prime}$ be the set of points at the
intersection of at least two lines in $\mathcal{L}$. One might think that
there exists a minimum convex tiling, such that all Steiner points belong to
$P^{\prime}$. We show in Figure 3 that this is not the case.

•••••••••••••••••• Figure 3: Points in black are the input point set $P$. The
points in red are Steiner points in the unique minimum convex tiling of $P$.
The point in red to the right does not belong to the set $P^{\prime}$.

Tight hardness results are known for the general set cover problem, since
Dinur and Steurer proved that there is no $((1-o(1))\log n)$-approximation
algorithm unless P=NP [7]. For CPL, no better algorithm than greedy is known.
Dumitrescu and Jiang gave a lower bound of $\Omega(\log n)$ for the
approximation ratio of the greedy algorithm for CPL [9], however, only APX-
hardness for the problem is known [3, 16].

Note that combining Theorem 1.9 with Theorem 1.5 is not enough to show NP-
hardness of CPNCS (one would have to show that there is no $24$-approximation
algorithm for MCP unless P=NP). We show in Section 4 that CPNCS is NP-hard,
even for some constrained point sets, using a reduction from _Maximum
Independent Set in Intersection Graphs of Segments_. This problem is NP-hard
[15], but no APX-hardness result is known. To show APX-hardness of CPNCS, one
might try to mimic the proofs for CPL. However, the proof by Brodén, Hammar
and Nilsson uses duality [3]. The dual problem of CPL is simply _Hitting Lines
with Points_ , but it is not clear how to use duality for CPNCS. The proof by
Anil Kumar, Arya and Ramesh is by a reduction from MAX-3SAT [16]. However in
our case, the segments in a solution must be non-crossing, and so using the
same point set does not work. Furthermore Planar MAX-3SAT admits a PTAS [5].
Therefore the question whether CPNCS is APX-hard is still open.

As for CPL, there is a huge gap between the the best approximation ratios
known (which are obtained with the greedy algorithm or some slight improvement
of it), and the hardness results. For CPL, the only partial results toward
showing tightness are by Dumitrescu and Jiang, who gave a tight lower bound on
how the greedy algorithm performs in the worst case [9]. Likewise, and in
order to motivate why it may be hard to improve on our
$\mathcal{O}(\sqrt{n}\log n)$-approximation algorithms for CPNCS and MCP, we
prove the following in Section 5.

######  Theorem 1.10.

There exist point sets for which the greedy algorithm for solving CPNCS
realises a $\Omega(\sqrt{n})$-approximation.

To say the least, it is not clear whether CPNCS, and also MCP by Theorem 1.5,
allow a constant-factor approximation algorithm. Before going into the proofs,
we want to make a remark that we deem interesting. In [16], Anil Kumar, Arya
and Ramesh mention that CPL was motivated by the problem of _Covering a
Rectilinear Polygon with Holes using Rectangles_. They say that getting a
$o(\log n)$-approximation for this problem seems to require a better
understanding of CPL. However, they are “not sure of the exact nature of this
relationship”. In this paper, we show the hardness of MCP by using tools
developed by Lingas to show NP-hardness of _Minimum Rectangular Partition for
Rectilinear Polygons with Holes_ [18]. The difference between a covering and a
partition is that, in the latter, objects are interior-disjoint. Moreover, we
prove that obtaining a constant-approximation algorithm for MCP is equivalent
to finding one for CPNCS. Again, CPNCS is the non-crossing version of CPL. We
hope this paper helps to better understand the relationship between these
problems.

##  2 Approximation algorithm

Let $P$ be a point set. The points not lying on the boundary of the convex
hull are called _inner points_. We denote by $P_{i}$ the set of inner points.
Let $p$ be in $P$. If $P$ and $P\setminus\\{p\\}$ do not have the same convex
hull, we say that $p$ is an _extreme point_. Note that a point might lie on
the boundary of the convex hull without being an extreme point. We say that
$P$ is _special_ if there are at most two extreme points in the point set
$P_{i}$ (considered in itself). In particular if $|P_{i}|\leq 2$, then $P$ is
special.

Now let us consider a point set $P$ that is not special. We denote by
$P^{\prime}$ the set of extreme points in $P_{i}$. As done by Knauer and
Spillner, we classify the vertices in $P^{\prime}$ into two types [14]. Let
$p$ be in $P^{\prime}$. Notice that $p$ determines two closed half-planes
$\mathcal{H}_{1}$ and $\mathcal{H}_{2}$, such that their respective interiors
contain no points in $P_{i}$, but their respective bounding lines $\ell_{1}$
and $\ell_{2}$ cover at least two points in $P_{i}$, and $\ell_{1}$ and
$\ell_{2}$ intersect at $p$. We say that $p$ is of _type (a)_ if the interior
of $\mathcal{H}_{1}\cap\mathcal{H}_{2}$ contains at least one point in $P$
(which therefore lies on the boundary of the convex hull of $P$). Otherwise,
$p$ is of _type (b)_. As noted by Knauer and Spillner, in any convex
partition, for any point $p$ of type (a), there is at least one edge
connecting $p$ to a point not in $P_{i}$. For any point $p$ of type (b), there
are at least two edges connecting $p$ to points not in $P_{i}$. Being
consistent with their notations, we denote by $a$ the number of points of type
(a), and by $b$ the number of points of type (b).

######  Lemma 2.1.

Let $P$ be a set of $n$ points that is not special. Given a covering of
$P_{i}$ with $s$ non-crossing segments, one can compute in
$\mathcal{O}(n^{2})$-time a convex partition of $P$ with at most $4s+a+2b$
faces.

######  Proof 2.2.

Let $P^{\prime}\subseteq P_{i}$ be the set of the endpoints of segments in the
covering. Note that $|P^{\prime}|$ is at most $2s$. We compute a constrained
triangulation (for example Delaunay) of $P^{\prime}$ with respect to the
segments of the covering. This can be done in $\mathcal{O}(n\log n)$-time [4],
and there are at most $2|P^{\prime}|$ faces. We observe that the triangulation
of $P^{\prime}$ is a convex partition of $P_{i}$. Moreover, we can partition
the remaining region into $a+2b$ convex polygons in $\mathcal{O}(n^{2})$-time,
see Lemma 3 in [14]. In total, we have found a convex partition with at most
$4s+a+2b$ faces.

######  Lemma 2.3.

Let $P$ be a set of $n$ points that is not special. Given a convex partition
of $P$ with $f$ faces, one can compute in $\mathcal{O}(n)$-time a covering of
$P_{i}$ with at most $6f-3a-6b$ non-crossing segments.

######  Proof 2.4.

Let us denote by $G=(P,E)$ the plane graph corresponding to the convex
partition. We denote by $Q$ the set of inner points that are of degree at
least $3$ in $G$. We set $k:=|Q|$. Following the remark of Knauer and
Spillner, let us count a lower bound on the number of edges in $G$. Each point
not in $Q$ has degree at least $2$, and the points on the boundary of the
convex hull are incident to at least $a+2b$ additional edges. We have
$2|E|=\sum_{v\in P}\deg(v)\geq 3k+2(n-k)+a+2b=k+2n+a+2b$. By Euler’s formula,
we have $f=|E|-n+1\geq\frac{k}{2}+\frac{a}{2}+b+1$.

We denote by $E^{\prime}$ the set of edges not incident to a point lying on
the convex hull of $P$. Let us consider all pairs of edges in $E^{\prime}$
that are incident to some inner point of degree $2$, such that the edges of
any pair are aligned. We can merge them into one segment, in linear time, to
obtain a plane graph on the point set $Q$. Indeed, by assumption two edges in
$E$ do not cross, and the segments we obtain by merging the edges may
intersect only at points in $Q$. Note that the segments cover all points in
$P_{i}\setminus Q$. For the covering of $P_{i}$ with non-crossing segments, we
consider all segments we have obtained, plus one segment reduced to a point
for each point in $Q$ not covered yet. Let us denote by $s$ the number of
segments we have obtained. As we have a plane graph on $Q$, it holds $s\leq
3k\leq 6f-3a-6b$.

It is now possible to combine Lemmas 2.1 and 2.3 to prove Theorem 1.5.

######  Proof 2.5 (Proof of Theorem 1.5).

Assume we are given polynomial time $\phi(n)$-approximation algorithm for MCP,
for some function $\phi$. Let us use it for approximating a solution to CPNCS.
Let $P$ be the input point set. If all points in $P$ are on a line, we can
compute a covering of $P$ with one segment. Otherwise, we create a new point
set $Q$ by adding three points such that the inner points of $Q$ are $P$. We
apply our algorithm to $Q$, and obtain a partition with $f\leq f_{m}\phi(n+3)$
convex faces. By Lemma 2.3, we can compute a covering of $P$ with at most
$6f-3a-6b$ non-crossing segments. Let us denote by $f_{m}$ and $s_{m}$ a
solution to MCP in $Q$ and CPNCS in $P$ respectively. From Lemma 2.1, we know
that from a covering of $P$ with $s$ non-crossing segments, we can compute a
convex partition of $Q$ with at most $4s+a+2b$ faces. Therefore there are at
least $\frac{f_{m}-a-2b}{4}$ segments in any valid covering, which means
$s_{m}\geq\frac{f_{m}-a-2b}{4}$. We have found a covering with at most
$6f-3a-6b\leq 6\phi(n+3)f_{m}-3a-6b\leq 24\phi(n+3)s_{m}+(a+2b)(6\phi(n+3)-3)$
non-crossing segments. Now notice that a segment can only cover up to two
extreme points in $Q$. Therefore we have $s_{m}\geq\frac{a+b}{2}$. We have
obtained a $48\phi(n+3)$-approximation for the CPNCS problem.

Conversely, if one has $\phi(n)$-approximation algorithm for CPNCS, it is
possible to compute a convex partition with at most $4s+a+2b\leq
4\phi(n)s_{m}+a+2b\leq 24\phi(n)f_{m}+(a+2b)(1-4\phi(n))$ faces, by doing the
same analysis. As for any $n$, $\phi(n)$ is greater than $1$, this gives a
$24\phi(n)$-approximation.

######  Lemma 2.6.

Let $P$ be a set of $n$ points that is not special. If there are $\ell_{m}$
lines in a minimum covering with lines of $P_{i}$, then there are at least
$\frac{\ell_{m}}{6}+\frac{a}{2}+b$ convex faces in a convex partition of $P$.

######  Proof 2.7.

Let us consider a convex partition of $P$ with $f$ faces. By Lemma 2.3, there
exists a covering of $P_{i}$ with at most $6f-3a-6b$ elements. Recall that the
elements of the covering are non-trivial segments and points. We are going to
define a covering of $P_{i}$ with lines. For each non-trivial segment in the
covering, we add the line on which it lies. If there is a pair of remaining
points, we add the line going through them. We iterate until at most one point
is not covered. If one does remain uncovered, we add any line through it.
Therefore we have found a covering of $P_{i}$ with at most $6f-3a-6b$ lines.
By assumption, we have $6f-3a-6b\geq\ell_{m}$, so there are at least
$\frac{\ell_{m}}{6}+\frac{a}{2}+b$ convex faces in any convex partition of
$P$.

Now we are ready to prove Theorem 1.2.

######  Proof 2.8 (Proof of Theorem 1.2).

Let $P$ be a set of $n$ vertices. First we test if all points are on a line.
If so, we return that there is no convex partition. Let us now assume that not
all points are on a line. If $P$ is a special point set, then it is easy to
compute a convex partition with at most four faces. Let us assume that $P$ is
not a special point set. Using the greedy algorithm for set cover problems, we
can compute a covering of $P_{i}$ with $\ell$ lines, where
$2\leq\ell\leq\log(n)\ell_{m}$ [12, 19]. The greedy algorithm runs in
quadratic time. Indeed, it is folklore that the greedy algorithm for covering
a set $X$ with the family of subsets $\mathcal{F}\subseteq 2^{X}$ can be
implemented in $\mathcal{O}(Z)$ time, where $Z=\sum_{F\in\mathcal{F}}|F|$. In
our situation, $Z$ is the number of point-line incidences, and so
$Z=\mathcal{O}(n^{2})$ because each point lies on at most $n-1$ lines.

We distinguish two cases, according to the value of $\ell$. We denote by
$\phi(n)$ a threshold function, that will be determined later. In the first
case, we assume $\ell\geq\phi(n)$. According to Lemma 2.6, there are at least
$\frac{\ell_{m}}{6}+\frac{a}{2}+b\geq\frac{\phi(n)}{6\log(n)}+\frac{a}{2}+b$
convex faces in any convex partition. As shown by Sakai and Urrutia [21], we
can compute in quadratic time a convex partition of $P_{i}$ with at most
$\frac{4n}{3}$ faces. From it, using the method of Knauer and Spillner, we can
compute a convex partition of $P$ with at most $\frac{4n}{3}+a+2b$ faces.
Therefore the approximation ratio is at most $\frac{8n\log(n)}{\phi(n)}+2$.

Now let us assume $\ell<\phi(n)$. Each line of the covering can be partitioned
into two half-lines and some segments, such that the interiors of these half-
lines and segments contain no point of $P$. We create a list $L$ of all the
segments. If $L$ contains a pair of segments whose intersection of relative
interiors is not empty, we remove both segments from $L$. We iterate until we
obtain a list of pairwise non-crossing segments. Finally, while $L$ contains a
pair of segments on the same line that share an endpoint, we remove the two
segments from $L$, and add the segment that is the union of both. There were
$\ell$ lines, so at most $\frac{\ell^{2}}{2}$ pairs of crossing segments,
therefore in the end we have at most $\ell+\ell^{2}\leq 2\ell^{2}$ segments in
$L$. By Lemma 2.1, one can compute a convex partition with at most
$8\ell^{2}+a+2b$ convex faces. By combining Lemma 2.6 and the assumption, we
know that the approximation ratio is at most
$\frac{48\ell^{2}}{\ell_{m}}+2\leq 48\phi(n)\log(n)+2$. It is clear that the
total running time of the algorithm is $\mathcal{O}(n^{2})$.

Let us finally compute $\phi$ as to minimise both approximation ratios. we
have $\frac{8n\log(n)}{\phi(n)}+2=48\phi(n)\log(n)+2$, and therefore we set
$\forall n,\phi(n)=\sqrt{\frac{n}{6}}$. The algorithm is realising a
$(48\sqrt{\frac{n}{6}}\log(n)+2)$-approximation, which is the claim.

##  3 NP-hardness proof

In this section we prove Theorem 1.9 for the MCT problem. We do the reduction
from MPLSAT to MCT by constructing a point set in three steps. First we
construct a non-simple polygon, in a similar way as in Lingas’ proof, with
some more constraints. Secondly, we add some line segments to build a grid
around the polygon, and finally we discretise each line segment into evenly
spaced collinear points. The idea of the first part is to mimic Lingas’ proof.
The second part makes the correctness proof easier, and the last part
transforms the construction into our setting. The aim of the grid is to force
the polygons in a minimum convex tiling to be rectangular.

We use the gadgets introduced by Lingas, namely cranked wires and junctions
[18]. A wire is shown in Figure 4. It consists of a loop delimited by two
polygons, one inside the other. In Lingas’ construction, the two polygons are
simple, and a wire is therefore a polygon with one hole. Moreover in his proof
the dimensions of the cranks do not matter. In our case, the polygon inside is
not simple, and each line segment has unit length. Each wire is bent several
times with an angle of $90^{\circ}$, as shown in Figure 4, in order to close
the loop.

Figure 4: A cranked wire, edges are in black and its interior is in grey. The
wire follows the whole red loop, but for sake of simplicity, only a section of
the wire at a bend is drawn.

The wires are used to encode the values of the variables, with one wire for
each variable. We are interested in two possible tilings of a wire, called
vertical and horizontal, which are shown in Figure 5.

Figure 5: A section of a wire and its optimal tilings: vertical (left) and
horizontal (right).

As in Lingas’ proof, we interpret the vertical tiling as setting the variable
to _true_ , and the horizontal as _false_. Lingas proved the following:

######  Lemma 3.1 (Lingas [18]).

A minimum tiling with convex sets of a wire uses either vertical or horizontal
rectangles but not both. Any other tiling requires at least one more convex
set.

The second tool is called a junction, and it serves to model a clause. Figure
6 depicts a junction corresponding to a clause of three literals. A junction
has three arms, represented as dashed black line segments. A junction for a
clause of two literals is obtained by blocking one of the arms of the
junction. The blue line segments have length $1+\varepsilon$, for a fixed
$\varepsilon$ arbitrarily small. Therefore, the red line segments are not
aligned with the long black line segment to their right. A junction can be in
four different orientations, which can be obtained successively by making
rotations of $90^{\circ}$. Let us consider the orientation of the junction in
Figure 6. One wire is connected from the left, one from above, and one from
the right. A wire can only be connected to a junction at one of its bends (see
Figure 4). We then remove the line segment corresponding to the arm of the
junction, as illustrated in Figure 6.

Figure 6: A junction for the MCT problem.

If the tiling of the wire connected from the left is horizontal, then one of
the rectangles can be prolonged into the junction. The same holds for the wire
connected from the right. On the contrary, a rectangle can be prolonged from
the wire connected from above only if the tiling is vertical. If a rectangle
can be prolonged, we say that the wire _sends true_ , otherwise it _sends
false_. If a clause contains two negative literals $\bar{x},\bar{y}$ and one
negative $z$, the corresponding junction is as in Figure 6, or the
$180^{\circ}$ rotation of it. The wire corresponding to $z$ is connected from
above or below, and the wires corresponding to $x$ and $y$ are connected from
the left and from the right, or vice versa. Therefore, the wire corresponding
to $z$ sends _true_ if and only if $z$ is set to _true_. On the contrary, the
wire corresponding to $x$ (respectively $y$) sends _true_ if and only if $x$
(respectively $y$) is set to _false_. If the clause has two positive literals,
then the junction is vertical, and the junction behaves likewise.

Lingas proved that when minimising the number of convex polygons in a tiling,
for each junction at least one adjacent wire sends _true_. Before stating
Lingas’ lemma exactly, we need to explain the first step of the construction
of the point set.

###  3.1 Construction of the polygon with holes

Let us consider one instance $(F,G)$ of MPLSAT. Lingas states that the
planarity of $G$ implies that the junctions and the wires can be embedded as
explained above, and so that they do not overlap [18]. Thus we obtain a
polygon with holes, that we denote by $\Pi$. He adds without proof that the
dimensions of $\Pi$ are polynomially related to $|V|$, where $V$ denotes the
vertex set of $G$. We show in the following paragraph how to embed the polygon
with holes into a grid $\Lambda$, such that each edge consists of line
segments of $\Lambda$. Actually, some parts of edges are not exactly line
segments of $\Lambda$, but are shifted orthogonally by distance $\varepsilon$
(recall the red segments in Figure 6). However, as $\varepsilon$ is
arbitrarily small, this does not impact our proof. Thus, for sake of
simplicity, we will from now on do as if the edges entirely consisted of
segments of $\Lambda$. Moreover, we show how to construct $\Lambda$ in
$\Theta(|V|^{2})$ size.

Let us consider an instance $(F,G)$ of MPLSAT. Recall that the vertex set of
$G$ is the union of $X$ and $C$, where $X$ denotes the set of variables and
$C$ the set of clauses. We define a new graph
$G^{\prime}=(V^{\prime},E^{\prime})$ as follow: For each vertex $x\in X$ of
degree $\delta$, we have $\delta$ vertices $x_{1},\dots,x_{\delta}$ in
$V^{\prime}$. Moreover for each $c\in C$ we have one vertex $c$ in
$V^{\prime}$. Now for each edge $(x,c)\in E$, we have one edge between $c\in
V^{\prime}$ and one of the $x_{i}\in V^{\prime}$. We do so such that each
vertex $x_{i}$ in $V^{\prime}$ corresponding to some $x\in V$ has degree $1$.
Then we add edges between the vertices $x_{1},\dots,x_{\delta}$ so that they
induce a path. We can do this such that the graph we obtain, $G^{\prime}$, is
still planar. Moreover, since a clause contains at most three vertices, the
maximal degree of $G^{\prime}$ is at most $3$. The number of vertices we have
added is at most the number of edges in $G$, therefore
$|V^{\prime}|=\Theta(|V|)$. Following the result of Valiant [23], we can embed
$G^{\prime}$ in a grid of size $\Theta(|V|^{2})$, such that the edges consist
of line segments of the grid. Let $s$ be the line segment incident to $c$ in
the edge $\\{x_{i},c\\}$, where $x_{i}$ corresponds a variable $x\in X$ and
$c$ is a clause. Our constraint is that $x$ appears positively in $c$ if and
only if $s$ is vertical. Moreover we impose $s$ to be of length at least $10$,
so that we have enough space later to replace $c$ by a junction. We claim that
we can find an embedding of $G$ on another grid, still of size
$\Theta(|V|^{2})$, that satisfies our constraint. We first scale the embedding
by $3$. Then we can change the path of each edge adjacent to $c$ as
illustrated in Figure 7, so that the embedding satisfies our first constraint.
The line segments in red (respectively blue) correspond to edges $\\{x,c\\}$
where $x$ appears positively (respectively negatively) in $c$. By assumption,
at most two variables appear positively, and at most two appear negatively.
Therefore it is possible to adapt the paths of the edges so that the red line
segments are vertical and the blue ones horizontal. Finally, we scale the grid
by $10$ to satisfy the second constraint.

•$c$•$c$ Figure 7: How to adapt the embedding to satisfy the constraint. On
the left, before adaptation, on the right, after adaptation

Now we replace each clause by a junction. Let $x_{1},\dots,x_{\delta}$ be the
vertices corresponding to a variable $x\in X$. Observe that the set of line
segments $\bigcup_{1\leq i\leq\delta}\\{e\in E^{\prime}\mid x_{i}\in e\\}$ is
a tree. Let us take a constant sufficiently big, and scale the grid so that we
can replace each tree corresponding to some variable $x\in X$ by a simple
polygon that is as close as possible to the tree. Then, after a new scaling,
we can replace each polygon by a wire, in a grid which is still of size
$\Theta(|V|^{2})$. As $\varepsilon$ introduced in the definition of the
junctions is arbitrarily small, we can consider that all line segments of
junctions and wires are segments of a grid. For sake of simplicity, we will
from now on omit to mention that some line segments are not exactly on the
grid. Again, it is possible to find an embedding in a grid of size
$\Theta(|V|^{2})$, such that wires do not intersect, and a wire is connected
to a junction if and only the variable corresponding to the wire is contained
in the clause corresponding to the junction.

We can now state Lingas’ lemma:

######  Lemma 3.2 (Lingas [18]).

In a minimum tiling with convex sets of $\Pi$, a junction contains wholly at
least three convex sets. The junction contains wholly exactly three if and
only if at least one of the wires connected to the junction sends _true_.

###  3.2 Discretisation of the line segments

To construct the point set, we first construct a collection of line segments.
We then discretise this collection by replacing each line segment by a set of
collinear points.

Let us consider our polygon with holes $\Pi$ that lies in the grid $\Lambda$.
The grid consists of points with integer coordinates, and line segments
between points that are at distance $1$. We consider the collection of line
segments consisting of $\Pi$ union each line segment of $\Lambda$ whose
relative interior is not contained in the interior of $\Pi$. Notice that
therefore we have line segments outside $\Pi$, but also inside its holes.
Moreover, the collection of line segments that we obtain, denoted by $\Phi$,
is a subgraph of the grid graph $\Lambda$.

Now we define $K$ as twice the number of unit squares in $\Lambda$ plus $1$.
Finally, we replace each line segment in $\Phi$ by $K$ points evenly spaced.
We denote this point set by $P$.

###  3.3 Proof of correctness

We have constructed $P$ in order to have the following property:

######  Lemma 3.3.

In a minimum convex tiling $\Sigma$ of $P$, for each convex set $S\in\Sigma$,
the interior of $S$ does not intersect $\Phi$.

Let $K^{\prime}$ denote the number of unit squares in $\Phi$, plus the minimum
number of rectangles in a partition of the wires, plus three times the number
of clauses. Using Lemmas 3.1 and 3.2 shown by Lingas coupled with Lemma 3.3,
we immediately obtain the following theorem:

######  Theorem 3.4.

The formula $F$ is satisfiable if and only if there exists a convex tiling of
$P$ with $K^{\prime}$ polygons.

Since $P$ and $K^{\prime}$ can be computed in polynomial time, Theorem 3.4
implies Theorem 1.9 for the MCT problem. We use a packing argument, and claim
that in a convex tiling $\Sigma$ of $P$, if a convex set $S\in\Sigma$ has
large area, then most of its area is contained in a unique cell of $\Phi$.
Then we show that in a minimum convex tiling, all convex sets have large area,
and that each of them fills the cell that contains it. For a set $S$, let
$\mathrm{A}(S)$ be the area of $S$.

######  Lemma 3.5.

Let $L$ and $L^{\prime}$ be two squares in $\Lambda$, and $S$ be a convex
polygon whose interior does not contain any point in $P$. If $\mathrm{A}(S\cap
L)>1/K$, and the boundary of $S$ crosses a line segment of $\Phi$ between $L$
and $L^{\prime}$, then $\mathrm{A}(S\cap L^{\prime})\leq 1/K$.

######  Proof 3.6.

The proof is illustrated in Figure 8. By assumption, $S$ goes between two
points $p$ and $q$ at distance $1/K$. Let us consider the two line segments
$s$ and $s^{\prime}$ of the boundary of $S$ that intersect the line $\ell$
spawned by $p$ and $q$. Assume for contradiction that the lines spawned by $s$
and $s^{\prime}$ do not intersect, or intersect on the side of $\ell$ where
$L$ lies. This implies that $S\cap L$ is contained in a parallelogram that has
area $1/K$, as illustrated in Figure 9. Indeed such a parallelogram has base
$1/K$ and height $1$, therefore $\mathrm{A}(S\cap L)\leq 1/K$. This shows that
the lines spawned by $s$ and $s^{\prime}$ intersect on the side of $\ell$
where $L^{\prime}$ lies. Using the same arguments as above, this implies
$\mathrm{A}(S\cap L^{\prime})\leq 1/K$.

••••••••••••••••$L$$S$$s$$s^{\prime}$$p$$q$ Figure 8: If $A(S\cap L)>1/K$, the
two lines spawned by $s$ and $s^{\prime}$ intersect on the left side.
••$p$$q$$L$ Figure 9: The area of the parallelograms is $1/K$.

######  Lemma 3.7.

Let $R$ be a rectilinear polygon on $\Lambda$ whose interior does not contain
any point in $P$. Let $\Psi$ be a set of squares of $\Lambda$ contained in
$R$, such that no two of them are on the same line or same column. Let
$\Sigma$ be a minimum convex tiling of $P$. Let $S$ be an element of $\Sigma$,
such that for each $L_{i}\in\Psi$, we have $\mathrm{A}(S\cap L_{i})>1/K$. Then
there exist $|\Psi|-1$ squares $\\{L_{i}\\}$ in $\Psi$ and $|\Psi|-1$ convex
sets $\\{S_{i}\\}$ in $\Sigma$, such that for any $i$: $\mathrm{A}(S_{i}\cap
L_{i})>1/K$.

######  Proof 3.8.

We assume $|\Psi|\geq 2$, otherwise there is nothing to prove. Using Lemma
3.5, we know that if such a $S$ exists, then there are no line segment of
$\Phi$ between any two squares in $\Psi$. We can observe thanks to how wires
and junctions are defined that $|\Psi|$ is at most three. Moreover for the
same reason, there are $|\Psi|-1$ squares in $\Psi$ such that the area of
their intersection with $S$ is at most $1/2$, as illustrated in Figure 10. As
$K$ is bigger than twice the number of squares in $\Lambda$, there exists a
set $\tilde{S}\in\Sigma$ for each such square $L\in\Psi$, with
$\mathrm{A}(\tilde{S}\cap L)>1/K$. Moreover by iterating this process we can
choose these convex sets so that they are distinct.

$L_{1}$$L_{2}$$L_{3}$$S$ Figure 10: If $A(S\cap L_{1})\geq 1/2$, then $A(S\cap
L_{2})\leq 1/2$ and $A(S\cap L_{3})\leq 1/2$.

######  Proof 3.9 (Proof of Lemma 3.3).

We define a map $f_{0}$ that associates each square $L$ in $\Lambda$ to a
convex set $S\in\Sigma$ such that $\mathrm{A}(S\cap L)>1/K$. Such a set exists
since otherwise we would need more than $K$ sets only to fill the square $L$.
Now we define a map $f$ in several steps. We start from $f_{0}$. At step
$i+1$, find $L$ and $L^{\prime}$ on the same line or the same column, and
$L^{\prime\prime}$ between them, such that $f_{i}(L)=f_{i}(L^{\prime})\neq
f_{i}(L^{\prime\prime})$. If this is not possible then stop. Otherwise define
$f_{i+1}$ as identically equal to $f_{i}$, except for all square between $L$
and $L^{\prime}$, that are mapped to $f_{i}(L)$. Notice that $f_{i+1}$ keeps
the property that for each square $\tilde{L}$, we have
$\mathrm{A}(f_{i}(\tilde{L})\cap\tilde{L})>1/K$. Moreover, this procedure must
stop eventually because the interiors of the convex sets are non-overlapping.
We denote by $f$ the map obtained after the last iteration.

We denote by $f^{-1}$ the function that maps a set $S\in\Sigma$ to
$\\{L\in\Lambda\mid f(L)=S\\}$. By Lemmas 3.5 and 3.7, if for some $S$ there
are $m$ squares in $f^{-1}(S)\geq 2$ such that no pair of squares are on a
line nor on a column, then there exists at least $m-1$ convex sets $S_{i}$
such that for each $S_{i}$, $f^{-1}(S_{i})=\emptyset$. Moreover, such a
$S_{i}$ cannot appear when considering another element of $\Sigma$: If Lemma
3.7 when applied to $S$ gives the existence of the $\\{S_{i}\\}$, and when
applied to $S^{\prime}\neq S$ gives the existence of the
$\\{S^{\prime}_{j}\\}$, then all these convex sets are distinct. We denote by
$M$ the number of such sets, taken over all sets $S\in\Sigma$ with
$f^{-1}(S)\geq 2$.

We are going to partition $P$ into at most $|\Sigma|-M$ rectilinear polygons
(not necessarily convex). We denote by $T$ the partition. For each set
$S\in\Sigma$ such that $|f^{-1}(S)|=1$, we add in $T$ the square in
$f^{-1}(S)$. For each $S\in\Sigma$ such that $|f^{-1}(S)|\geq 1$, we add in
$T$ the rectilinear polygon consisting of the union of the squares in
$f^{-1}(S)$. We know thanks to Lemma 3.5 that the boundary of this rectilinear
polygon does not cross any line segment in $\Phi$. Following what was argued
above, there are at most $|\Sigma|-M$ sets in $T$. We now construct a new
convex tiling $\Sigma^{\prime}$, that we claim to be minimum. We replace each
set in $T$ that is not convex by rectangles. From the construction of wires
and junctions, there exists a partition of the sets in $T$ into rectangles
that will add $N$ new sets. Looking at the construction of $T$ and then
$\Sigma^{\prime}$, we can observe that the convex tiling $\Sigma$ was minimum
if and only if there were no set $S$ such that its interior intersects $\Phi$.

###  3.4 How to adapt the proof to MCP

Let us explain how to adapt the proof to the case of the MCP problem. Notice
that the only lemma for which it makes a difference is Lemma 3.2. Indeed, if
in Figure 6 the wire connected from below sends _true_ , then one can prolong
a rectangle of this wire so that it contains the small rectangle in the
junction. Therefore only three rectangles are wholly contained in the
junction. However, the vertex on the top left of the prolonged rectangle is
not a point of $P$. This can be solved by adding a line segment to the
construction, coloured in red in Figure 11. With this construction, the
rectangle is prolonged into a trapezoid (delimited above by the dashed red
line segment). The convex set above remains a rectangle, and the one to the
left becomes a convex quadrilateral with a right angle. Now one can adapt the
proof by taking into account this new triangular hole that has been inserted
in each junction. The proof can then be done similarly to the one of the MCT
problem.

Figure 11: A junction for the MCP problem.

##  4 NP-hardness of CPNCS

Let us consider the CPNCS problem with additional constraints on the input
point set $P$. Let us denote by $L$ the set of lines that contain at least
three points in $P$. We consider the CPNCS problem on $P$ such that there are
no five collinear points, the lines in $L$ are in three possible directions,
and a point $p\in P$ is contained in at most one line in $L$. We show that
CPNCS is NP-hard, even for such constrained point sets.

Kratochvíl and Nešetřil have shown that _Maximum Independent Set in
Intersection Graphs of Segments_ is NP-hard, even when the segments lie in
only three possible directions [15]. The problems corresponds to finding a
maximum set of pairwise non-intersecting segments. There is an additional
constraint that no two parallel segments intersect. We do a reduction from
this problem to CPNCS with the additional constraints. Let us consider a set
of such line segments. We shift the segments such that no three endpoints are
on a line, and each segment does not contain an endpoint of another segment,
without changing the corresponding intersection graph. We replace each of them
by four collinear points, that lie on the segment. There is a pair of points
close to one endpoint of the segment, and the other pair close the other
endpoint. We do it such that three points are collinear only if they lie on
the same segment of the input set. Also, the pair of points $p,q$ on one end
of a segment $t$ are so close that no other segment crosses the segment
between $p$ and $q$. Moreover, every segments that intersects with $s$ crosses
it between the two pairs of points. It is clear that the point set satisfies
our constraints.

We denote by $n$ the number of segments. We claim that there is an independent
set of $s$ segments if and only if there is a covering of the points with
$2n-s$ non-crossing segments. Assume there is an independent set of $s$
segments, and let us show the existence of a covering with $2n-s$ elements.
For each segment in the independent set, we take it in the covering. For the
other segments, we take two segments to cover the four points: one for each
pair of close points. Therefore we have covered the points with $s+2(n-s)$
segments, which are non-crossing by assumption.

Let us now assume that there is a covering of the point set with $2n-s$ non-
crossing segments. Let us denote by $x$ the number of segments that cover more
than two points. Such a segment covers at most four points, and there are $4n$
points to cover. Hence, we have $4x+2(2n-s-x)\geq 4n$, which implies $x\geq
s$. By construction, each segment that covers more than two points is a
segment of the input set, thus there exists an independent set of $s$
segments.

##  5 Proof of Theorem 1.10

Consider the set of $2k(2k+1)$ points $P:=\\{(x,y)\mid x,y\in\mathbb{N},1\leq
x\leq 2k+1,1\leq y\leq 2k\\}$. Now we perturb slightly the points such that
any line that covers at least three points is either vertical or horizontal.
Actually, after perturbation, the lines might not be exactly vertical or
horizontal, but we keep referring to them as such for simplicity. Moreover, we
perturb again the points such that only $k$ horizontal lines cover at least
three points. We do so such that, for any pair of consecutive horizontal lines
that covers at least three points, there are $k+1$ points in between (which
correspond to the points of the former horizontal line). In the end, a
vertical line covers at least three points if and only if it covers exactly
$2k$ points. Similarly, a horizontal line covers at least three points if and
only if it covers exactly $2k+1$ points. We denote this new point set by
$P^{\prime}$, and denote by $n$ the cardinality of $P^{\prime}$. It is clear
that one can cover all points using $2k+1$ vertical segments (which are thus
non-crossing). However, the greedy algorithm will first pick the $k$
horizontal segments with even $y$-coordinate. Then it remains to cover the
$k(2k+1)=\frac{n}{2}$ remaining points, but there is no line covering three of
these points. Therefore the greedy algorithm picks at least
$\frac{k(2k+1)}{2}$ more segments. Hence, the approximation ratio is at least
$\frac{k(2k+1)/2}{2k+1}=k/2=\Omega(\sqrt{n})$.

Recall that in Theorem 1.2, we introduce another algorithm whose approximation
ratio is $\mathcal{O}(\sqrt{n}\log n)$ for solving CPNCS. The algorithm first
computes a minimum covering with lines of the point set, and then divides
these lines into non-crossing segments. By the same reasoning, this algorithm
will also have an approximation ratio of at least $\Omega(\sqrt{n})$ on the
point set $P^{\prime}$.

##  6 Open problems

It would be interesting to have approximation algorithms for MCP and CPNCS
with better ratio than $\mathcal{O}(\sqrt{n}\log n)$. Conversely, one could
try to prove better inapproximability results, for instance APX-hardness. It
would also be nice to determine the worst-case approximation ratio of the
greedy algorithm for CPNCS. A natural question to ask for MCP is whether it is
fixed-parameter tractable in the number of faces in an optimal convex
partition. This question only makes sense when having several points on a line
is allowed, since otherwise the minimum number of convex faces is linear in
the number of inner points.

It is still open whether MCT is in NP. It may be that the coordinates of a
vertex of a polygon require exponentially many bits. We also do not know the
complexity of MCP and MCT when it is assumed that no three points are
collinear. A key property used in our proof can be summarised as follows: When
a rectangle with large area is delimited by a lot of points, it is optimal to
take this rectangle in the convex tiling or partition. But this cannot be
achieved when no three points are on a line, as illustrated in Figure 12. In
any convex partition the red edges are forced. Even in a convex tiling, one
can observe that they are needed for the tiling to be minimum. This implies
that three convex sets are necessary. But adding the convex set consisting of
the black points in convex position would add one unnecessary convex set.
Adding more points to delimit the convex set cannot change the fact that
taking this convex set in the tiling would not be optimal. The construction
can easily be adapted for the MCP problem. Therefore it is not clear how one
could force some convex sets to be in the partition or tiling.

••••••••••• Figure 12: An optimal tiling splits the area delimited by points
in convex position.

## References

  * [1] Allan S. Barboza, Cid C. de Souza, and Pedro J. de Rezende.  Minimum convex partition of point sets.  In Proceedings of International Conference on Algorithms and Complexity, pages 25–37. Springer, 2019.  doi:/10.1007/978-3-030-17402-6_3.
  * [2] Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D Demaine, Rudolf Fleischer, Alejandro López-Ortiz, Pat Morin, and J Ian Munro.  Online routing in convex subdivisions.  International Journal of Computational Geometry & Applications, 12(04):283–295, 2002.  doi:10.1142/S021819590200089X.
  * [3] Björn Brodén, Mikael Hammar, and Bengt J Nilsson.  Guarding lines and 2-link polygons is APX-hard.  Proc. 13th Canadian Conference on Computational Geometry, 2001.  Available at http://hdl.handle.net/2043/6645.
  * [4] L Paul Chew.  Constrained delaunay triangulations.  Algorithmica, 4(1-4):97–108, 1989.  doi:10.1007/BF01553881.
  * [5] Pierluigi Crescenzi and Luca Trevisan.  Max NP-completeness made easy.  Theoretical Computer Science, 225(1-2):65–79, 1999.  doi:10.1016/S0304-3975(98)00200-X.
  * [6] Erik Demaine, Sándor Fekete, Phillip Keldenich, Dominik Krupke, and Joseph S. B. Mitchell.  CG:SHOP 2020.  https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2020.  Accessed: 12/02/2020.
  * [7] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing, pages 624–633, 2014.  doi:10.1145/2591796.2591884.
  * [8] Adrian Dumitrescu, Sariel Har-Peled, and Csaba D Tóth.  Minimum convex partitions and maximum empty polytopes.  In Proceedings of Scandinavian Workshop on Algorithm Theory, pages 213–224. Springer, 2012.  doi:10.1007/978-3-642-31155-0_19.
  * [9] Adrian Dumitrescu and Minghui Jiang.  On the approximability of covering points by lines and related problems.  Computational Geometry, 48(9):703–717, 2015.  doi:10.1016/j.comgeo.2015.06.006.
  * [10] Thomas Fevens, Henk Meijer, and David Rappaport.  Minimum convex partition of a constrained point set.  Discrete Applied Mathematics, 109(1-2):95–107, 2001.  doi:10.1016/S0166-218X(00)00237-7.
  * [11] Jesús García-López and Carlos M Nicolás.  Planar point sets with large minimum convex decompositions.  Graphs and Combinatorics, 29(5):1347–1353, 2013.  doi:10.1007/s00373-012-1181-z.
  * [12] David S Johnson.  Approximation algorithms for combinatorial problems.  In Proceedings of the fifth annual ACM Symposium on Theory of Computing, pages 38–49, 1973.  doi:10.1145/800125.804034.
  * [13] J Mark Keil.  Decomposing a polygon into simpler components.  SIAM Journal on Computing, 14(4):799–817, 1985.  doi:10.1137/0214056.
  * [14] Christian Knauer and Andreas Spillner.  Approximation algorithms for the minimum convex partition problem.  In Proceedings of Scandinavian Workshop on Algorithm Theory, pages 232–241. Springer, 2006.  doi:10.1007/11785293_23.
  * [15] Jan Kratochvíl and Jaroslav Nešetřil.  Independent set and clique problems in intersection-defined classes of graphs.  Commentationes Mathematicae Universitatis Carolinae, 31(1):85–93, 1990.  Available at http://eudml.org/doc/17810.
  * [16] VS Anil Kumar, Sunil Arya, and Hariharan Ramesh.  Hardness of set cover with intersection 1.  In Proceedings of International Colloquium on Automata, Languages, and Programming, pages 624–635. Springer, 2000.  doi:10.1007/3-540-45022-X_53.
  * [17] David Lichtenstein.  Planar formulae and their uses.  SIAM Journal on Computing, 11(2):329–343, 1982.  doi:10.1137/0211025.
  * [18] Andrzej Lingas.  The power of non-rectilinear holes.  In Proceedings of International Colloquium on Automata, Languages, and Programming, pages 369–383. Springer, 1982.  doi:10.1007/BFb0012784.
  * [19] László Lovász.  On the ratio of optimal integral and fractional covers.  Discrete Mathematics, 13(4):383–390, 1975.  doi:10.1016/0012-365X(75)90058-8.
  * [20] Víctor Neumann-Lara, Eduardo Rivera-Campo, and Jorge Urrutia.  A note on convex decompositions of a set of points in the plane.  Graphs and Combinatorics, 20(2):223–231, 2004.  doi:10.1007/s00373-004-0555-2.
  * [21] Toshinori Sakai and Jorge Urrutia.  Convex decompositions of point sets in the plane.  arXiv preprint arXiv:1909.06105, 2019.
  * [22] Simon Tippenhauer and Wolfgang Muzler.  On planar 3-SAT and its variants.  Master Thesis, Fachbereich Mathematik und Informatik der Freien Universitat Berlin, 2016.
  * [23] Leslie G. Valiant.  Universality considerations in VLSI circuits.  IEEE Transactions on Computers, 30(2):135–140, 1981.  doi:10.1109/TC.1981.6312176.