# Approximating Median Points in a Convex Polygon

Reyhaneh Mohammadi  Raghuveer Devulapalli  E-mail address:
<EMAIL_ADDRESS>Mehdi Behroozi 111Corresponding author:
<EMAIL_ADDRESS>Phone (617) 373-2032; Address: 449 Snell Engineering
Center, 360 Huntington Ave, Boston, MA 02115. M.B. gratefully acknowledges the
support of Northeastern University for this research.

###### Abstract

We develop two simple and efficient approximation algorithms for the
continuous $k$-medians problems, where we seek to find the optimal location of
$k$ facilities among a continuum of client points in a convex polygon $C$ with
$n$ vertices in a way that the total (average) Euclidean distance between
clients and their nearest facility is minimized. Both algorithms run in
$\mathcal{O}(n+k+k\log n)$ time. Our algorithms produce solutions within a
factor of 2.002 of optimality. In addition, our simulation results applied to
the convex hulls of the State of Massachusetts and the Town of Brookline, MA
show that our algorithms generally perform within a range of 5% to 22% of
optimality in practice.

Keywords: Continuous Location Optimization; $k$-Medians Problem; Approximation
Algorithms; Geometric Optimization; Computational Geometry

###  1 Introduction

The $k$-medians problem is a well-known geometric optimization problem in
which the aim is to select $k$ median points in a way to minimize the total
distance of clients to their nearest median points with respect to some
measure. The most studied setting for this problem is considering the client
set as a discrete set. Papadimitriou [1] showed that the $k$-medians problem
in the Euclidean plane is NP-Complete. The first constant-factor approximation
algorithm for the $k$-medians problem in the plane was proposed by Arora [2].
Bartal gave a randomized approximation algorithm in [3] to approximate
distances on a graph with $n$ vertices with distances on a tree with
approximation ratio of $\mathcal{O}(\log^{2}n)$. This made it possible for
many optimization problems, including $k$-medians problem, where the objective
function is some function of edge length to be solved on a tree, which is much
easier to solve exactly or approximately due to the structure of a tree, while
losing only a factor of $\mathcal{O}(\log^{2}n)$. The $k$-medians problem on a
general graph is NP-hard, but there are optimal algorithms for solving it on a
tree with $n$ vertices in time $\mathcal{O}(k^{2}n^{2})$ [4] and time
$\mathcal{O}(kn^{2})$ [5]. Later, Bartal improved the ratio to
$\mathcal{O}(\log n\>\log\log n)$, therefore providing a randomized
approximation algorithm for the $k$-medians problem with the same
approximation ratio [6]. Then Charikar et al. [7] by subsequently
derandomizing and refining this algorithm obtained the first deterministic
approximation algorithm with ratio $\mathcal{O}(\log k\>\log\log k)$ of
optimality. Charikar and Guha [8] proposed a factor $6\frac{2}{3}$
approximation algorithm for this problem and improved the bound. Then, Jain
and Vazirani [9] proposed a 3-approximation algorithm for the uncapacitated
facility location problem based on the primal-dual schema and used that as a
sub-routine for the $k$-medians problem and proposed a 6-approximation
algorithm. Then Jain et al. [10] improved the bound for the uncapacitated
facility location problem to 1.61 leading to a 4-approximation algorithm for
the $k$-medians problem. Li and Svensson [11] presented an approximation
algorithm for the $k$-medians problem and via a 2-step proof showed that the
approximation guarantee is $1+\sqrt{3}+\epsilon$. In the first step, they
showed that to give an $\alpha$-approximation algorithm for the $k$-medians
problem, it suffices to have a pseudo-approximation algorithm that generates
an $\alpha$-approximate solution by opening $k+O(1)$ facilities and in the
second step, they designed a pseudo-approximation algorithm with
$\alpha=1+\sqrt{3}+\epsilon$. This bound was slightly improved to
$2.675+\epsilon$ by Byrka et al. [12].
In the other setting of this problem, the number of clients are so large that
we could consider the client set as a continuous region. This setting makes
the corresponding discrete $k$-medians problem intractable. However, assuming
a continuous distribution of clients could help us in modeling and solving it
in an easier way. The first attempt for solving this problem was made by
Fekete et al. in [13], which provides polynomial-time algorithms for different
versions of the 1-median (Fermat-Weber) problem using $L_{1}$ norm. They also
showed that the multiple-center version of this problem which is the
$k$-median problem with $L_{1}$ distance, is NP-hard for large $k$. Later,
Carlsson et al. [14] developed a simple factor 2.74 approximation algorithm
for the continuous $k$-medians problem in a convex polygon using $L_{2}$ norm.

In this work, we propose two simple constant-factor approximation algorithms
for the continuous $k$-medians problem in a convex polygon $C$ with $n$
vertices under the $L_{2}$ norm. Our theoretical analysis shows that our
algorithms always produces solutions within a factor of 2.002 of optimality in
$\mathcal{O}(n+k+k\log n)$ time. To the best of our knowledge, this provides a
significant improvement to the previous best results for this problem. We have
also proposed a modification to our algorithms in order to improve the average
practical performance of the algorithms. Our simulation results applied to the
convex hulls of the State of Massachusetts and the Town of Brookline, MA show
that in practice, our algorithms generally perform much better than the worst
case analysis and their solutions are within a range of 5% to 22% of
optimality.

####  1.1 Notational Conventions

We define the Fermat-Weber value of a region $C$ relative to the point $p\in
C$ as

$\mathop{\rm FW}(C,p)=\iint_{C}{\|x-p\|\,dA},$

and Fermat-Weber value of region $C$ as

$\mathop{\rm FW}(C)=\min_{p}\iint_{C}{\|x-p\|\,dA}\,.$

We also define

$\mathop{\rm FW}(C,k)=\min_{P:|P|=k}\iint_{C}{\;\min_{p_{i}\in
P}\|x-p_{i}\|\,dA}\,,$

to be the Fermat-Weber objective function that we try to minimize, where
$\|\cdot\|$ denotes the Euclidean norm and we are looking for a set $P$ of $k$
points. Note that $\mathop{\rm FW}(C)=\mathop{\rm FW}(C,1)$. When the region
is a rectangle $R$ with dimensions $w$ and $h$, for simplicity of analysis, we
show $\mathop{\rm FW}(R,p),\;\mathop{\rm FW}(R)$, and $\mathop{\rm FW}(R,k)$
with $\mathop{\rm FW}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h,p),\;\mathop{\rm
FW}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h)$, and
$\mathop{\rm FW}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h,k)$,
respectively. We also show half of $\mathop{\rm FW}_{\mathbin{\text{
\leavevmode\hbox to4.34pt{\vbox to2.98pt{\pgfpicture\makeatletter\hbox{\hskip
0.13562pt\lower-0.13562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h)$ with
$\mathop{\rm FW}_{1/2}(w,h)$. Let $\square C$ denote the minimum-area bounding
box of $C$ and let $\mathop{\rm width}(C)$ and $\mathop{\rm height}(C)$ denote
the horizontal and vertical dimensions of $\square C$. Let $\mathop{\rm
Area}(C)$ and $\mathop{\rm diam}(C)$ denote the area and diameter of $C$,
respectively. For a rectangle $R$, let $\mathop{\rm AR}(R)$ be the aspect
ratio of $R$ which is defined as $\mathop{\rm
AR}(R)=\max\left\\{\frac{\mathop{\rm height}(R)}{\mathop{\rm
width}(R)},\>\frac{\mathop{\rm width}(R)}{\mathop{\rm height}(R)}\right\\}$.
Finally, we use $\rho$ to denote the approximation factor of an algorithm.

###  2 General Framework of our Approach

We first present a general framework for our algorithms for solving the
continuous $k$-medians problem in a convex polygon. Our approach is aligned
with that of [14] and can be summarized in as follows: the input to our
algorithms is a convex polygon $C$ with $n$ vertices and an integer $k$. We
assume without loss of generality that $C$ is aligned so that its diameter
coincides with the coordinate $x$-axis. We then enclose $C$ in an axis-aligned
minimum bounding box $R=\square C$ of dimensions $w$ and $h$, where
$w=\mathop{\rm diam}\left(C\right)$. By aligning the diameter with the
$x$-axis, we must have:

$\frac{wh}{2}\leq\mathop{\rm Area}\left(C\right)\leq wh$ (1)

Note that (1) holds for a general minimum bounding box of a convex region too
(the lower and upper bounds are tight when $C$ is a triangle and a rectangle,
respectively).

We then somehow divide $\square C$ into rectangular pieces of areas
$\mathop{\rm Area}\left(\square C\right)/k$. The way this partitioning is done
will have a significant impact on the performance of the algorithm and will be
discussed in Sections 4 and 5. Then, the center of each sub-rectangle is
chosen as our landmark points. It may happen that some of these points may lie
outside the convex polygon (Figure 1c). Such points are simply relocated back
into the polygon (Figure 1d). The way we to do this operation turns out to
have a minimal impact on the performance of the algorithm. This approach is
illustrated in Figure 1. Finally, without loss of generality (w.l.o.g.) and
for simplicity of our abalysis, we can consider the bounding box $R$ to be of
dimensions $w$ and $1$, where $w=\mathop{\rm diam}(C)\geq 1$. It follows that
$\frac{w}{2}\leq A\leq w$. The algorithm breaks $R$ into $k$ sub-rectangles of
equal area $\frac{w}{k}$.

(a)  (b)  (c)  (d)

(e)

Figure 1: We begin in (1a) with a convex polygon $C$, whose axis-aligned
bounding box $\square C$ is computed in (1b). The bounding box is then
partitioned into equal-area pieces in (1c). Some of the centers of these
pieces are then relocated in (1d), and (1e) shows the output and Voronoi
partition. The above images are reproduced from Figure 1 of [14].

###  3 Upper and Lower Bounds

Given a convex object $C$ of area $A$, we want to find upper and lower bounds
on $\mathop{\rm FW}(C)$. The main motivation to find these bounds is that, we
want to use them in finding upper and lower bounds for the $k$-medians problem
($\mathop{\rm FW}(C,k)$). Note that the papers [15], [16] and [17] almost
entirely deal with finding upper and lower bounds on $\mathop{\rm FW}(C)$ in
terms of $A$ and $d=\mathop{\rm diam}(C)$. Summarized in one line, they prove
the following bounds: $0.1666dA\leq\mathop{\rm FW}(C)\leq 0.3490dA$.

Unfortunately, these bounds are not useful in our work for two reasons. First,
a lower bound in terms of diameter of $C$ does not help us achieve a lower
bound on $\mathop{\rm FW}(C,k)$. And secondly, the upper bound can be
significantly improved when the convex region is “skinny” (it is easy to show
that the Fermat-Weber of a very long skinny rectangle is approximately
$0.25dA$). The authors in [16] arrive at their upper bound by making using of
the fact that a convex object of diameter $d$ can always be contained in a
circle of radius $d/\sqrt{3}$. Rather than using a bounding circle, we find it
more useful to derive bounds in terms of a bounding box that contains $C$.
This is because for a long and skinny region, the area of the minimum bounding
circle can be infinitely larger than the area of the convex region itself. But
if one considers the minimum bounding box of $C$, we can prove that the ratio
of its area to that of the convex polygon is at most 2 for any convex region
(see equation (1)).

In the following sections, we will derive lower and upper bounds for a convex
polygon $C$ of area $A$ that is contained within a rectangle of dimensions $w$
and $h$, where $A\in[0,wh]$ (this rectangle need not necessarily be the
minimum bounding box of $C$). The Fermat-Weber value of the rectangle itself
is denoted using $\mathop{\rm FW}_{\mathbin{\text{ \leavevmode\hbox
to4.34pt{\vbox to2.98pt{\pgfpicture\makeatletter\hbox{\hskip
0.13562pt\lower-0.13562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h)$. A closed
form expression for $\mathop{\rm FW}_{\mathbin{\text{ \leavevmode\hbox
to4.34pt{\vbox to2.98pt{\pgfpicture\makeatletter\hbox{\hskip
0.13562pt\lower-0.13562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h)$ is given in
Section A of the Online Supplement.

####  3.1 Lower bounding $\mathop{\rm FW}(C)$

Here, we derive a simple lower bound that we will use to place an overall
lower bound on $\mathop{\rm FW}(C,k)$. For a given area $A$, it is a well
known fact that disk is the shape that minimizes its Fermat-Weber value.
Hence, using the Fermat-Weber of a disk, we can arrive at an easy lower bound
on $\mathop{\rm FW}(C)$: $\Phi_{LB_{1}}(A)=\frac{2}{3\sqrt{\pi}}A^{3/2}$ (see
Remark 2 in Section A of the Online Supplement). In most cases, this simple
lower bound is large enough for our analysis. But, in some cases, we have
skinny regions and there might be a big gap between this simple lower bound
and the actual Fermat-Weber value. For such cases we consider the region to be
the intersection of a disk of radius $r$ and a slab of height $h$ with
$r\geq\frac{h}{2}$. As you can also see in Figure 2, the area of such region
can be written in terms of $r$ and $h$. Calculating the Fermat-Weber of such
region we obtain another lower bound on $\mathop{\rm FW}(C)$:
$\Phi_{LB_{2}}(A_{(r,h)})=\frac{4r^{3}}{3}\sin^{-1}\left(\frac{h}{2r}\right)+\frac{1}{3}rh\sqrt{r^{2}-\frac{h^{2}}{4}}+\frac{1}{12}h^{3}\log\left(\frac{2r+\sqrt{4r^{2}-h^{2}}}{h}\right)$.
Combining these with the fact that the region is contained within a box of
dimensions $w$ and $h$, we can obtain a comprehensive lower bound as
summarized in the following lemma.

######  Lemma 1.

Let $C$ be a convex region with area $A$, contained in a box $B$ of dimensions
$w$ and $h$, with $w\geq h$. If $B^{\prime}$ is a horizontal slab of height
$h$ that contains $B$ and $D$ is a disk of radius $r$ centered at the centroid
of the box such that $\mathop{\rm Area}\left(D\cap B^{\prime}\right)=A$, then:

$\mathop{\rm FW}\left(C\right)\geq\begin{cases}\frac{2}{3}\pi r^{3}&\mbox{if
}r<\frac{h}{2}\\\
\frac{4r^{3}}{3}\sin^{-1}\left(\frac{h}{2r}\right)+\frac{1}{3}rh\sqrt{r^{2}-\frac{h^{2}}{4}}+\frac{1}{12}h^{3}\log\left(\frac{2r+\sqrt{4r^{2}-h^{2}}}{h}\right)&\mbox{if
}r\geq\frac{h}{2}\end{cases}$ (2)

###### Proof.

(a) Region $C^{*}$ of minimal Fermat-Weber.

(b) Breaking $C^{*}$ into triangles and sectors.

Figure 2: A narrow convex region of area $A$ formed by intersection of a disk
with radius $r$ and a slab of height $h$, that provides a lower bound for the
Fermat-Weber value.

Refer to Figure 2 for this proof. The shape $C^{*}$ that minimizes
$\mathop{\rm FW}\left(C\right)$ in $B^{\prime}$ is the intersection of a disk
of radius $r$ with a slab of height $h$, and its Fermat-Weber value varies
according to $r$ and $h$.

###### Case 1:

If $r<h/2$, then $C^{*}$ is a disk and hence we have $\mathop{\rm
FW}\left(C^{*}\right)=\frac{2}{3}\pi r^{3}$ (from Lemma 16 in Section A of the
Online Supplement).

###### Case 2:

If $r\geq h/2$, then $C^{*}$ is the intersection of a disk and a slab of
height $h$, and the Fermat-Weber of such a region can be found out by
evaluating the integral
$\iint_{C^{*}}\sqrt{x_{1}^{2}+x_{2}^{2}}\,dx_{1}\,dx_{2}\,$. An easy way to do
this is to break $C^{*}$ into regions consisting of right-angled triangles and
circular sectors (Figure 2b) and then use Lemmas 16 and 18 of Section A of the
Online Supplement to arrive at the lower bound. ∎ We will denote the lower
bound in (2) using $\Phi_{LB}\left(A,h\right)=\mathop{\rm
FW}\left(C^{*}\right)$. Note that the $\Phi_{LB}$ is independent of the width
of the rectangle (since we have assumed that $w\geq h$).

####  3.2 Lower Bounds on $\mathop{\rm FW}(C,k)$

(a)

(b)

(c)

(d)

Figure 3: Lower bounding $\mathop{\rm FW}(C,k)$: Fermat-Weber of each Voronoi
cell can be lower bounded by a disk. The sum of Fermat-Weber of disks is
minimized when the areas of all disks are equal, which follows from convexity
of $\Phi_{LB_{1}}$. The same argument holds if we were to replace the disks by
slabs ($\Phi_{LB_{2}}$) shown in Figure 2a.

Let set of points $\\{p^{*}_{1},...,p^{*}_{k}\\}$ be optimum solution for
polygon $C$, which is itself embedded in a box of dimensions $w$ and $1$. If
each of $k$ points is assigned area $A^{*}_{i}$ (i.e., if the area of the
Voronoi cell associated with the $i^{th}$ point is $A^{*}_{i}$), then the
Fermat-Weber value of $C$ must satisfy (refer to Figure 3):

$\mathop{\rm
FW}\left(C,k\right)\geq\sum_{i=1}^{k}\Phi_{LB_{1}}\left(A^{*}_{i}\right)\,$

Since each of the summands is _convex_ as a function of $A^{*}_{i}$, the
right-hand side is _minimized_ when each of the points is assigned an equal
area $A^{*}_{i}=A/k$ (Figure 3d). We therefore have:

$\mathop{\rm FW}\left(C,k\right)\geq k\cdot\Phi_{LB_{1}}\left(A/k\right)$ (3)

Replacing $\Phi_{LB_{1}}$ with $\Phi_{LB}$ gives us a better lower bound and
because $\Phi_{LB}$ is also convex in $A$, all the arguments still hold.

$\mathop{\rm FW}\left(C,k\right)\geq k\cdot\Phi_{LB}\left(A/k,1\right)\,.$ (4)

####  3.3 Upper bounding $\mathop{\rm FW}\left(C\right)$

To find an upper bound on $\mathop{\rm FW}(C)$, we will answer the following
question: What is the shape of the convex region of a given area $A$, that is
contained within a box $w$ and $h$ and has the maximum Fermat-Weber quantity?
Intuitively skinnier regions have larger Fermat-Weber values. But to find the
exact shape of such a region is not easy. Interestingly, this becomes
tractable if $A=wh/2$. In Lemma 2 we will provide an upper bound for the case
$A=wh/2$. And in Lemma 5, we will extend this result to find an upper bound
for all $A\in[0,wh]$. Here on, we will use $\mathop{\rm FW}_{1/2}(w,h)$ to
denote $0.5\mathop{\rm FW}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h)$, which is
half the Fermat-Weber value of the rectangle.

######  Lemma 2.

Let $C$ be a convex region of area $A$ that is contained within a box $B$ of
dimensions $w$ and $h$. If $A=\frac{wh}{2}$, then we have:

$\mathop{\rm FW}(C)\leq{\mathop{\rm FW}}_{1/2}(w,h)$

###### Proof.

(a)  (b)  (c)

Figure 4: It is obvious that all regions $C$ above have the same Fermat-Weber
value relative to $x_{0}$, namely $\mathop{\rm FW}_{1/2}(w,h)$.

Let $x_{0}$ denote the center of $B$. By definition of Fermat-Weber, for any
convex region $C$ we have: $\mathop{\rm FW}(C)\leq\mathop{\rm FW}(C,x_{0})$.
Consider the family $\mathcal{C}$ consisting of all convex regions $C$ in $B$
which merely consist of the area lying to one side of a line through $x_{0}$,
as shown in Figure 4. It is obvious that, for any region
$C^{{}^{\prime}}\in\mathcal{C}$, we have $\mathop{\rm
FW}(C^{{}^{\prime}},x_{0})=\mathop{\rm FW}_{1/2}(w,h)$ by a trivial symmetry
argument. Therefore, it will suffice to show that we can take _any_ convex
region $C$ in $B$ with area $wh/2$ and transform it into a region
$C^{{}^{\prime}}\in\mathcal{C}$ in a manner that does not decrease
$\mathop{\rm FW}(C,x_{0})$ . This will basically prove our result:
$\mathop{\rm FW}(C)\leq\mathop{\rm FW}(C,x_{0})\leq\mathop{\rm
FW}(\mathcal{C},x_{0})=\mathop{\rm FW}_{1/2}(w,h)$. We will show how to
execute this transformation after making two straightforward observations:

######  Lemma 3.

Let $s$ denote a line segment in the plane and let $\vec{v}$ be a vector in
the plane, so that $s+t\vec{v}$ is a translation operator on $s$ in the
direction $\vec{v}$. Then the function $f(t)=\int_{s+t\vec{v}}||x||\,dx$ is
convex in $t$.

###### Proof.

The function $f(t)$ is simply the Fermat-Weber value of the line segment
$s+t\vec{v}$ relative to the origin; it is an infinite sum of convex functions
and is therefore itself convex.∎

######  Lemma 4.

For any triangle $T$ with vertices $\\{x_{1},x_{2},x_{3}\\}$, let $T(t)$
denote the sheared triangle $\\{x_{1},x_{2},x_{3}+t(x_{2}-x_{1})\\}$. Then the
function $g(t)=\mathop{\rm FW}(T(t),x_{0})$ is convex in $t$ for any fixed
$x_{0}$.

###### Proof.

This is a corollary of Lemma 3 because $g(t)$ is an infinite sum of convex
functions $f(t)$. ∎

We can now proceed to prove Lemma 2. Consider any convex region $C$ with area
$wh/2$, contained inside a box $B$ with dimensions $w\times h$, as in the
statement of Lemma 2.

(a)  (b)  (c)  (d)

Figure 5: Two applications of Lemma 3 permit us to assume that $C$ takes the
shape shown in Figure 5d.

By visualizing $C$ as a union of vertical line segments (Figure 5a),we can
apply Lemma 3 to assume without loss of generality that $C$ takes the shape
shown in Figure 5b, i.e., that $C$ is the area lying below some concave
function (this is because the function defined in Lemma 3 is convex and
therefore is maximized when each line segment is as far from the origin,
$x_{0}$, as possible). By visualizing $C$ as a union of _horizontal_ line
segments (Figure 5c) we can subsequently assume without loss of generality
that $C$ takes the shape shown in Figure 5d, i.e., that $C$ is the area lying
below some concave and increasing function. By using a series of shear
transformations and iteratively applying Lemma 4, we can show that the region
$C$ takes the form shown in Figure 4 and in doing so, we would have only
increased the Fermat-Weber value of $C$ relative to $x_{0}$, the center of
$B$. Due to space constraints, these transformations are described in detail
in section B of the Online Supplement and we conclude the proof here.

∎

######  Lemma 5.

Let $C$ be a convex region contained in a box $B$ of dimensions $w\times h$
with $w\geq h$ such that $C$ contains a horizontal line segment whose length
is equal to that of $\mathop{\rm width}(C)$. If $A=\mathop{\rm Area}(C)$, then
we have:

$\mathop{\rm FW}(C)\leq{\mathop{\rm FW}}_{1/2}\left(w,\frac{2A}{w}\right)$ (5)

###### Proof.

We break up the proof into two separate cases:

###### Case 1: $A<wh/2$

. Since $A<\frac{wh}{2}$ and since $C$ contains a line segment whose length is
width($C$), we can always construct a smaller box $B^{\prime}$ with dimensions
$w^{\prime}\times h^{\prime}$ containing the region $C$, such that
$A=\frac{w^{\prime}h^{\prime}}{2}$ (see Figure 6a). Applying Lemma 2 for
$B^{\prime}$, we find that $\mathop{\rm FW}\left(C\right)\leq\mathop{\rm
FW}_{1/2}\left(w^{\prime},h^{\prime}\right)$. By performing some basic
algebra, it is not hard to show that, among all values of $w^{\prime}$ and
$h^{\prime}$ such that $w^{\prime}\leq w$, $h^{\prime}\leq h$ and
$w^{\prime}h^{\prime}=2A$, the value
$FW_{1/2}\left(w^{\prime},h^{\prime}\right)$ is maximized when $w^{\prime}=w$
and $h=2A/w$ (Fermat-Weber value of a rectangle increases with aspect ratio).
Thus, we find that:

$\mathop{\rm FW}(C)\leq{\mathop{\rm FW}}_{1/2}\left(w,\frac{2A}{w}\right)\,$

(a) $A<wh/2$

(b) $A\geq wh/2$

Figure 6: We can find a box $B^{\prime}$ that encloses region $C$ such that
$w^{\prime}h^{\prime}=2A$, $\forall A\in[0,wh]$.

###### Case 2: $A\geq wh/2$

. Since $A\geq wh/2$, we can obviously find a larger rectangle $B^{\prime}$,
which contains the region $C$ such that $A=\frac{w^{\prime}h^{\prime}}{2}$.
One easy way to do that is to increase the height of $B$ to $h^{\prime}$ such
that $A=\frac{wh^{\prime}}{2}$ (see Figure 6b), which leads to
$h^{\prime}=\frac{2A}{w}\geq h$. Using Lemma 2 for $B^{\prime}$, we arrive at
the upper bound which completes the proof. ∎ It is easy to verify that the
upper bound of Lemma 5 is convex and monotonically increasing in $A$ (see
Figure 7a). It also has an undesirable property that, for some interval:
$A\in(A_{c},hw]$, we actually have $\mathop{\rm
FW}_{1/2}\left(w,\frac{2A}{w}\right)>\mathop{\rm FW}_{\mathbin{\text{
\leavevmode\hbox to4.34pt{\vbox to2.98pt{\pgfpicture\makeatletter\hbox{\hskip
0.13562pt\lower-0.13562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h)$, which is
the Fermat-Weber value of the rectangle itself. Therefore,

$\Phi^{2}_{UB}(A,w,h)=\min\left\\{{\mathop{\rm
FW}}_{1/2}\left(w,\frac{2A}{w}\right),{\mathop{\rm FW}}_{\mathbin{\text{
\leavevmode\hbox to4.34pt{\vbox to2.98pt{\pgfpicture\makeatletter\hbox{\hskip
0.13562pt\lower-0.13562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h)\right\\}$

will be a more meaningful upper bound. But this function, $\Phi^{2}_{UB}$,
(Figure 7b) is neither convex or concave in the desired region of interest. To
help simplify the analysis in the later section, we choose the simplest
_concave envelope_ of the above function as our final upper bound,
$\Phi_{UB}\,$:

$\Phi_{UB}\left(A,w,h\right)=\min\left\\{\frac{A}{A_{c}}{\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h),{\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(w,h)\right\\}$ (6)

where $A_{c}$ is the solution of the equation: $\mathop{\rm
FW}_{1/2}\left(w,\frac{2A_{c}}{w}\right)={\mathop{\rm FW}}_{\mathbin{\text{
\leavevmode\hbox to4.34pt{\vbox to2.98pt{\pgfpicture\makeatletter\hbox{\hskip
0.13562pt\lower-0.13562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}\left(w,h\right)$.
Fermat-Weber value of a rectangle can be calculated using Equation (8) in
Lemma 17 in Section A of the Online Supplement. Note that the ratio
$\frac{A_{c}}{hw}$ depends only on the aspect ratio of the rectangle. Also, by
construction, for a given $w$ and $h$, $\Phi_{UB}$ is a piecewise linear
concave function.

(a) $FW_{1/2}\left(w,\frac{2A}{w}\right)$

(b) Concave envelope of $\Phi^{2}_{UB}$

Figure 7: Upper bound for a convex region of area $A$ within a unit square.

######  Remark 1.

Few interesting observations on the Fermat-Weber center can be made at this
point. Using Lemma 3.1 of [18] and the lower bound on $\mathop{\rm FW}(C)\geq
0.16dA$, it can be shown that choosing any point within a convex region is a
constant factor-4.17 approximation for the 1-median problem. The center of the
smallest enclosing circle of $C$ is a factor 2.41 approximation of Fermat-
Weber center, which was proved in [16]. Whereas, using bounds $\Phi_{UB}$ and
$\Phi_{LB_{2}}$ we can show that the center of the minimum bounding box of a
convex region is a factor-2 approximation algorithm for the 1-median problem.

###  4 A Constructive Algorithm

As discussed in Section 2, the performance of our approach is sensitive to how
we divide the bounding box of the convex polygon into $k$ rectangular sub-
regions of equal area. More specifically, the aspect ratios of the sub-
rectangles will determine the quality of the upper bound. Here, we modify a
well-known constructive algorithm in data visualization field called
Squarified treemap algorithm [19] and use it as a partitioning subroutine. Our
algorithm takes a convex polygon $C$ and an integer $k$ and gives a partition
of $C$ into $k$ sub-regions and then places a median point at the center of
each sub-region.

####  4.1 Description of the Constructive Algorithm

The algorithm first bounds the polygon with its minimum bounding box $\square
C$. Let $R=\square C$ and let $w$ and $h$ denote its dimensions and assume
w.l.o.g. that $w\geq h$. The algorithm then rotates $C$ in a way that the
bounding box is aligned with the $x$-axis. Note that $w=\mathop{\rm diam}(C)$.
The algorithm then subdivides the bounding box into $k$ sub-rectangles with
equal areas. In each iteration, the algorithm makes a vertical (horizontal)
division of the remaining (unfilled) part of $\square C$ and fills the left
(bottom) part of the division with a subset of the remaining (unplaced) sub-
regions in a way that the aspect ratio of the sub-regions that will be placed
is minimized. In each iteration, if the width of the remaining part of
$\square C$ is greater than its height the division will be vertical and
otherwise it will be horizontal. Since we assumed $w\geq h$ the first division
will be vertical. It creates a strip with a single rectangle at the left side
of $R$ which has area equal to $\mathop{\rm Area}(\square C)/k$ and calculates
the aspect ratio of this rectangle. Then it adds another rectangle with same
area to this strip on top of the first rectangle. Clearly, the width of the
strip will increase. Again it calculates the aspect ratio. Note that the
aspect ratio of all rectangles in one strip is the same. Then, it continues
adding the rectangles as long as the aspect ratio of our rectangles in the
strip keeps decreasing. Once by adding another rectangle to the current strip
the aspect ratio increases, the algorithm fixes the current strip and a new
strip is created. Let $S$ denote the union of the rectangles in this first
strip. After fixing this strip, it will let $R=R\backslash S$ and will
continue to the next iteration. In any iteration if $\mathop{\rm
height}(R)>\mathop{\rm width}(R)$ the division will be horizontal and the
rectangles will be added next to each other in a horizontal strip. The
algorithm continues until $\square C$ is partitioned into $k$ equal area
rectangles. Figure 8 shows an illustration of applying this algorithm for
partitioning a bounding box into 7 equal area rectangles. Algorithm 1 shows
the detailed steps of this partitioning scheme.

Figure 8:  Dividing a box with aspect ratio 1.6 into 7 sub-rectangles using
Squarified Algorithm.

After completing the partitioning phase, Algorithm 2 finds a location for
median points. For the rectangles that are completely inside $C$, it places a
median point at the center of each such rectangle and for those which are not
located completely inside $C$, but have an intersection with $C$, it places a
median point at the center of the bounding box of each intersection area. For
any rectangle that has no intersection with $C$, it randomly places one center
inside $C$. This random placement has minimal impact on the performance of the
algorithm which will be discusses in Section 7.1.

1

Input: An axis-aligned rectangle $R$ with dimensions $w$ and $h$ and an
integer $k$.

Output: A partition of $R$ into $k$ rectangles, each having area $\mathop{\rm
Area}(R)/k$.

2 /*
**************************************************************************************
*/

3 if k=1 then

4 return $R$;

5

6else

7 Let $w$ and $h$ denote the width and height of $R$, respectively;

8 if $w\geq h$ then

9 Fill the left part of rectangle with $i\leq k$ sub-rectangles on top of each
other each having area $\mathop{\rm Area}(R)/k$ in a way that the aspect ratio
of these sub-rectangles is smaller than the aspect ratio of sub-rectangles
when the left part is filled by $i-1$ sub-rectangles;

10 Let $R_{j},\;j=1,...,i$ denote the placed sub-rectangles;

11 $S=\cup_{j=1}^{i}R_{j}$;

12 $R^{\prime}=R\backslash S$;

13 $w^{\prime}=w-\frac{i}{kh}\mathop{\rm Area}(R)$;

14 $h^{\prime}=h$;

15

16 else

17 Fill the bottom part of rectangle with $i\leq k$ sub-rectangles next to
each other in a way that the aspect ratio of these sub-rectangles is smaller
than the aspect ratio of sub-rectangles when the bottom part is filled by
$i-1$ sub-rectangles;

18 Let $R_{j},\;j=1,...,i$ denote the placed sub-rectangles;

19 $S=\cup_{j=1}^{i}R_{j}$;

20 $R^{\prime}=R\backslash S$;

21 $w^{\prime}=w$;

22 $h^{\prime}=h-\frac{i}{kw}\mathop{\rm Area}(R)$;

23

24 end if

25 $k^{\prime}=k-i$;

26 return ${\sf
SquarifiedPartition}\>(R^{\prime},w^{\prime},h^{\prime},k^{\prime})$;

27

28 end if

Algorithm 1 Algorithm ${\sf SquarifiedPartition}\>(R,w,h,k)$ takes as input an
axis-aligned rectangle $R$ and its dimensions $w$ and $h$ and a positive
integer $k$ and returns a partition of $R$ into $k$ sub-rectangles with equal
areas.

1

Input: A convex polygon $C$ and an integer $k$.

Output: The locations of $k$ median points $p_{i},\;i=1,...,k$ in $C$ that
approximately minimize $\mathop{\rm FW}(C,k)$ within a factor of 2.002.

2 /*
**************************************************************************************
*/

3 Let $R=\square C$ denote a minimal bounding box of $C$. Rotate $C$ so that
$R$ is aligned with the coordinate axes;

4 Let $w=\mathop{\rm width}(R)$;

5 Let $h=\mathop{\rm height}(R)$;

6 Let $R_{1},...,R_{k}={\sf SquarifiedPartition}\>(R,w,h,k)$;

7 for $i\in\\{1,...,k\\}$ do

8 Let $c_{i}$ denote the center of $R_{i}$;

9 if $c_{i}\in C$ then

10 Set $p_{i}=c_{i}$;

11

12 else

13 if $R_{i}\cap C$ is nonempty then

14 Let $R_{i}^{{}^{\prime}}$ be the minimum axis-aligned bounding box of
$R_{i}\cap C$ and let $c_{i}^{{}^{\prime}}$ denote its center;

15 Set $p_{i}=c_{i}^{{}^{\prime}}$;

16

17 else

18 Place $p_{i}$ anywhere in $C$;

19

20 end if

21

22 end if

23

24 end for

25return $p_{1},...,p_{k}$;

Algorithm 2 Algorithm ${\sf ConstructFW}\>(C,k)$ takes as input a convex
polygon $C$ and an integer $k$ and places $k$ median points in $C$.

####  4.2 Analysis of Algorithm 2

#####  4.2.1 Running Time of Algorithm 2

This algorithm can be performed with running time $\mathcal{O}(n+k+k\log n)$.
This is because Algorithm 1 takes $\mathcal{O}(k)$ operations to form the
placement of the sub-rectangles and Algorithm 2 requires $\mathcal{O}(n)$
operations to find a minimum bounding box of $C$. The last step of Algorithm 2
consists of moving the center points to $C$ when necessary, which takes
$\mathcal{O}(k\log n)$ operations using a point-in-polygon algorithm [20].

#####  4.2.2 Aspect Ratios in Algorithm 1

To investigate the aspect ratios of the rectangles produce by Algorithm 1,
first, we make two simplifying assumptions:

Assumption 1.

We assume the bounding box $R=\square C$, once rotated and aligned with the
axes, is such that its width is larger than its height, i.e., $w\geq h$.

Assumption 2.

Without loss of generality we assume that the height of the bounding box is
equal to 1. Hence, $w\geq 1$.

######  Lemma 6.

If $w/k\geq 0.5$, Algorithm 1 divides $R=\square C$ into $k$ equal area
rectangles with dimensions $\frac{w}{k}\times 1$.

###### Proof.

At the beginning, since $w\geq h$, the algorithm starts with vertical
subdivision. If we put one single rectangle on the left, the aspect ratio will
be $\mathop{\rm AR}_{1}=\max\\{\frac{w}{k},\frac{k}{w}\\}$. Then, if we add
another rectangle to this single rectangle strip, the aspect ratio of each of
the two rectangles becomes $\mathop{\rm
AR}_{2}=\max\\{\frac{4w}{k},\frac{k}{4w}\\}$. We can easily see that for
$\frac{w}{k}\geq 1$ we have $\mathop{\rm AR}_{1}=\frac{w}{k}$ and $\mathop{\rm
AR}_{2}=\frac{4w}{k}$ and hence $\mathop{\rm AR}_{1}$ is smaller and the strip
with one rectangle will be fixed. For $0.5\leq\frac{w}{k}\leq 1$, $\mathop{\rm
AR}_{1}=\frac{k}{w}\leq 2$ and $\mathop{\rm AR}_{2}=\frac{4w}{k}\geq 2$ and
again $\mathop{\rm AR}_{1}$ has smaller value and the strip with one rectangle
will be fixed.

While the width of the undivided part of the main rectangle is greater than
its height, the algorithm will continue likewise for new strips. Therefore, it
suffices to consider the case when the height of the undivided rectangle
becomes greater than its width. Assume that $i$ rectangles have been already
located in the main rectangle next to each other. The width and the height of
the undivided rectangle will be $w-i\frac{w}{k}$ and 1, respectively. Thus we
have

$w-i\frac{w}{k}<1\Longrightarrow i>k-\frac{k}{w}>k-2\geq k-1$

So, the case when the height becomes greater than the width of the undivided
rectangle only happens when one rectangle is remained and it means the
subdivision is complete. ∎

######  Lemma 7.

If we have a rectangle with width $w$ and height $h$ and we divide it into $k$
rectangles using Algorithm 1 and $w/h\leq k$, the aspect ratio of all
rectangles in the first created strip is less than or equal to 2.

###### Proof.

First, note that by construction and assumption of $w\geq h$ the first strip
is a vertical strip where we will have rectangles that their height is greater
than or equal to their width and they all have the same aspect ratios. Let
$\mathbin{\text{ \leavevmode\hbox to4.84pt{\vbox
to6.78pt{\pgfpicture\makeatletter\hbox{\hskip 0.48438pt\lower-0.48438pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.96875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.81247pt}\pgfsys@lineto{3.87498pt}{5.81247pt}\pgfsys@lineto{3.87498pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{3.87498pt}{5.81247pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{i}$ denote a strip
that contains $i$ rectangles. Now, assume that Algorithm 1 has fixed the first
strip and the aspect ratio of rectangles in this strip is greater than 2. So,

${\mathop{\rm AR}}_{\,\mathbin{\text{ \leavevmode\hbox to3.39pt{\vbox
to4.75pt{\pgfpicture\makeatletter\hbox{\hskip 0.33905pt\lower-0.33905pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.67812pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{4.06874pt}\pgfsys@lineto{2.7125pt}{4.06874pt}\pgfsys@lineto{2.7125pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{2.7125pt}{4.06874pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{i}}=\max\\{\frac{2i/kh}{h/i},\frac{h/i}{2i/kh}\\}=\frac{h/i}{2i/kh}>2$

Now, we add another rectangle to this strip and calculate the new aspect
ratio.

${\mathop{\rm AR}}_{\,\mathbin{\text{ \leavevmode\hbox to3.39pt{\vbox
to4.75pt{\pgfpicture\makeatletter\hbox{\hskip 0.33905pt\lower-0.33905pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.67812pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{4.06874pt}\pgfsys@lineto{2.7125pt}{4.06874pt}\pgfsys@lineto{2.7125pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{2.7125pt}{4.06874pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{i+1}}=\max\\{\frac{h/(i+1)}{2(i+1)/kh},\frac{2(i+1)/kh}{h/(i+1)}\\}$

If
$\max\\{\frac{h/(i+1)}{2(i+1)/kh},\frac{2(i+1)/kh}{h/(i+1)}\\}=\frac{h/(i+1)}{2(i+1)/kh}$,
clearly the aspect ratio is decreased by adding the $(i+1)$th rectangle. This
contradicts the assumption that the algorithm has fixed the strip with $i$
rectangles. So when the strip is fixed, we must have
$\max\\{\frac{h/(i+1)}{2(i+1)/kh},\frac{2(i+1)/kh}{h/(i+1)}\\}=\frac{2(i+1)^{2}}{kh^{2}}$.
Then for $i=1,...,k-1$, we will have

$\frac{h/i}{2i/kh}>2\implies\frac{kh^{2}}{2i^{2}}>2\implies\frac{2i^{2}}{kh^{2}}<0.5\implies\frac{2(i+1)^{2}}{kh^{2}}<2\,,$

which again shows adding the $(i+1)$th rectangle could improve the aspect
ratio and make it less than 2 that contradicts our initial assumption. This
completes the proof. ∎

######  Lemma 8.

If we use Algorithm 1 for dividing a rectangle $R$ with dimensions $w$ and
height $h$ and $w/h\leq 2$, in every step of the algorithm, as long as we have
more than one sub-rectangle remaining, the undivided part of the rectangle has
aspect ratio less than or equal to 2.

###### Proof.

Let $w^{\prime}$ and $h^{\prime}$ to be, respectively, the length of the
longer and shorter sides of the undivided part of $R$ that is remained after
the first strip is fixed by the algorithm. Using this definition,
$w^{\prime}/h^{\prime}$ represents the aspect ratio of the undivided part in
every step of the algorithm. If the direction does not change, we still have
$w^{\prime}/h^{\prime}=w^{\prime}/h<w/h\leq 2$. The algorithm will continue,
while maintaining this condition, until after fixing a strip the direction
changes. Therefore, it suffices to consider the case where the direction
changes after fixing the first strip (see Figure 9). Without loss of
generality, assume $w\geq h$, let the number of sub-rectangles in the fixed
strip be $i$ and the remaining sub-rectangles for the undivided part be
$r=k-i$.
Now, let $z=w^{\prime}/h^{\prime}\in\mathbb{R}$ and assume $z>2$. Hence,
$w>w^{\prime}=zh^{\prime}$. Since the area of each sub-rectangle is
$\frac{1}{i+r}$, we have

$\frac{h(w-h^{\prime})}{i}=\frac{hh^{\prime}}{r}\implies\frac{w-h^{\prime}}{i}=\frac{h^{\prime}}{r}\implies
i=\frac{(w-h^{\prime})r}{h^{\prime}}\implies i\geq zr-r\implies i\geq r(\lceil
z\rceil-1)$

Let $\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*}$ denote one of
the rectangles in the fixed strip. By increasing $i$, the area of the
undivided part decreases and since the height of the rectangle does not
change, the aspect ratio of $\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*}$ increases.
Since our algorithm seeks to minimize the aspect ratio in each strip, $i$
should be minimized. Thus, $i=\lceil rz\rceil-r$. We have

$\mathop{\rm AR}(\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*})=\frac{w-h^{\prime}}{h/i}=\frac{i^{2}h^{\prime}/r}{h}=\frac{i^{2}}{rh/h^{\prime}}=\frac{i^{2}}{rw^{\prime}/h^{\prime}}=\frac{(\lceil
rz\rceil-r)^{2}}{rz}$

For $r\geq 2$ and $z>2$, this term is minimized when $r=2,z=2.5$, which gives
$\mathop{\rm AR}(\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*})\geq 1.8$.
Suppose that we reduce one rectangle from the strip and add it to the
undivided part of our rectangle. Let $\mathbin{\text{ \leavevmode\hbox
to6.2pt{\vbox to4.26pt{\pgfpicture\makeatletter\hbox{\hskip
0.19374pt\lower-0.19374pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{**}$ denote one of
the rectangles in the modified strip. We have

$\mathop{\rm AR}(\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{**})=\max\\{\frac{w-h^{\prime}}{h/(i-1)},\frac{h/(i-1)}{w-h^{\prime}}\\}=\max\\{\frac{(\lceil
rz\rceil-r-1)^{2}}{rz},\frac{rz}{(\lceil rz\rceil-r-1)^{2}}\\}$

Clearly, if the maximum is the first statement, it is less than $\mathop{\rm
AR}(\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*})$ and if the
maximum is the second statement, it is maximized when $r=2,z=2.5$ and results
in $\mathop{\rm AR}(\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{**})\leq 1.25$.
This is a contradiction since by construction the aspect ratio of a fixed
strip cannot be reduced by removing a rectangle. Hence, the assumption that
$z>2$ is rejected.

Figure 9:  A rectangle having a fixed strip mentioned in the proof of Lemma 8.
The left figure shows a rectangle with width $w$ and height $h$ when a strip
with $i$ sub-rectangles is fixed and the direction has switched. The right
figure shows this rectangle when one sub-rectangle is reduced from that strip
and added to the undivided part on the right.

∎

######  Corollary 9.

If we have a rectangle with width $w$ and height $h$ and we divide it into $k$
rectangles using Algorithm 1 and $w/h\leq k$, the aspect ratio of all
rectangles in all created strips before a change of direction is at most 2.

###### Proof.

This is by iteratively applying the result of Lemma 7 in the undivided part
which by Lemma 8 satisfies the assumptions of Lemma 7. ∎

######  Lemma 10.

If $\mathop{\rm AR}(R)\leq 2$, the aspect ratio of the last sub-rectangle
created by Algorithm 1 is less than or equal to 3.

###### Proof.

We know from 8 that for dividing a rectangle with aspect ratio less than or
equal to 2 using Algorithm 1, while the number of remaining sub-rectangles is
more than 1, the undivided part of the rectangle always has aspect ratio less
than or equal to 2. The last sub-rectangle will be generated either
immediately after a change in direction or width of the last undivided
rectangle which has aspect ratio less than or equal to two, should be divided
into two equal parts. For the latter case, the aspect ratio is maximized when
the width and the height of the undivided part are equal in which case the
aspect ratio of the last two sub-rectangles will be equal to 2, which is less
than 3.
For the former case, let $\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*}$ be the last
sub-rectangle and suppose we have $i$ sub-rectangles in the strip immediately
before the last sub-rectangle (see Figure 10). Let $w$ and $h$ be the width
and height of the union of this strip and the last rectangle and assume,
w.l.o.g., that $w\geq h$ and that the area of this rectangle is equal to
$wh=1$. Therefore, the area of each sub-rectangle is $1/(i+1)$. We obtain

$\mathop{\rm AR}(\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*})=\frac{h}{h^{\prime}}=\frac{h^{2}}{1/(i+1)}=\frac{i+1}{w^{2}}$

We want to see when the aspect ratio of $\mathbin{\text{ \leavevmode\hbox
to6.2pt{\vbox to4.26pt{\pgfpicture\makeatletter\hbox{\hskip
0.19374pt\lower-0.19374pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*}$ is maximized.
Since in this case the last sub-rectangle is happening after a change in
direction, we must have $i\geq 2$. Note that when we have $i$ sub-rectangles
in the strip, $\mathop{\rm AR}(\mathbin{\text{ \leavevmode\hbox to6.2pt{\vbox
to4.26pt{\pgfpicture\makeatletter\hbox{\hskip 0.19374pt\lower-0.19374pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*})$ is better
than the case if we had $i-1$ and $i+1$ sub-rectangles in the strip. This is
obvious for $i+1$, since we assumed $w\geq h$. Since we know the aspect ratio
of sub-rectangles when the strip has $i$ sub-rectangles is better than the
case with $i-1$, we have:

$\frac{(w-h^{\prime})i}{h}<\frac{h}{(w-h^{\prime\prime})(i-1)}\,,$

where $h^{\prime\prime}$ is the height of $\mathbin{\text{ \leavevmode\hbox
to6.2pt{\vbox to4.26pt{\pgfpicture\makeatletter\hbox{\hskip
0.19374pt\lower-0.19374pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*}$ if we have
$i-1$ sub-rectangles in the strip. In the given inequality, the left-hand side
represents the aspect ratio of sub-rectangles when there are $i$ sub-
rectangles in the strip, while the right-hand side represents the aspect ratio
of sub-rectangles when there are $i-1$ sub-rectangles in the strip. It is
important to note that in the left-hand side, the sub-rectangles are arranged
horizontally since there is only one sub-rectangle left, and this is the only
orientation that allows the strip to be positioned before the last sub-
rectangle. Conversely, in the right-hand side, the sub-rectangles are arranged
vertically. This orientation is chosen because if they were arranged
horizontally, the resulting aspect ratio would not be worse than the case with
$i$ sub-rectangles. Then replacing $h^{\prime}$ with $1/h(i+1)$,
$h^{\prime\prime}$ with $2/h(i+1)$ and $h$ with $1/w$, we obtain:

$w^{4}<\frac{(i+1)^{2}}{i^{2}(i-1)^{2}}$

Since $w\geq h$ and $wh=1$, we have $w\geq 1$, which gives us $i\leq 2$.
Hence, $i=2$ and $\mathop{\rm AR}(\mathbin{\text{ \leavevmode\hbox
to6.2pt{\vbox to4.26pt{\pgfpicture\makeatletter\hbox{\hskip
0.19374pt\lower-0.19374pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.3875pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{3.87498pt}\pgfsys@lineto{5.81247pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{5.81247pt}{3.87498pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}_{*})=\frac{3}{w^{2}}\leq
3$.

Figure 10:  The strip immediately before the last sub-rectangle mentioned in
10.

∎

######  Theorem 11.

If we have a rectangle with width $w$ and height 1 (with $w\geq 1$) and we
want to divide it into $k$ sub-rectangles such that $w/k\leq 0.5$ using
Algorithm 1, the aspect ratio of all rectangles except the last one is less
than or equal to 2 and for the last one it is less than or equal to 3.

###### Proof.

Algorithm 1 starts with creating one strip at the left part of the rectangle
(since we have $w\geq h$). The first strip will be repeated until the width of
the undivided part of the rectangle becomes smaller than the height of the
rectangle, at which point the direction changes. Before this change, somewhere
through the process, the aspect ratio of the undivided part will become less
than 2, if at the beginning it was not the case. By Corollary 9, all of the
sub-rectangles created so far have aspect ratios not greater than 2.

We claim that when the direction changes, we must have the ratio of the width
of the undivided part to its height less than or equal to the number of
remaining sub-rectangles. To prove this, let $w_{r}$ be the width of the
undivided part of the rectangle and let $r=k-i$ be the number of remaining
sub-rectangles for this part (see Figure 11). We must show $w_{r}/h\leq r$ or
$w_{r}/(k-i)\leq 1$. This can be proved by

$\frac{w_{r}h}{k-i}=\frac{wh}{k}\implies\frac{w_{r}}{k-i}=\frac{w}{k}\leq
0.5<1$

Figure 11:  An intermediate step of Algorithm 1 while $i$ sub-rectangles are
fixed and $r=k-i$ sub-rectangles should be placed in the remaining part of the
box with width $w_{r}$ and height $h$.

Therefore, the condition of Lemma 7 is satisfied for the undivided part after
the change in direction. Also, after the change of direction, if $r\geq 2$, we
have an undivided rectangle with aspect ratio not greater than 2, satisfying
the condition $w/h\leq 2$ in Lemma 8. If the number of remaining sub-
rectangles $r$ is more than one, i.e., $w/h\leq 2\leq r$, we can conclude, by
Corollary 9, that the aspect ratio of sub-rectangles in the next strip is less
than or equal to 2. While we have more than one sub-rectangle, we continue the
algorithm by iteratively generating sub-rectangle (in strips) and undivided
rectangles with aspect ratios not greater than 2. Therefore, all sub-
rectangles that have been generated so far have aspect ratio less than or
equal to 2. Once we get into the situation that only one sub-rectangle is
remained, by Lemma 10, the aspect ratio of the last sub-rectangle is less than
or equal to 3. ∎

###  5 A Subdivision Algorithm

As mentioned in Sections 2 and 4, the performance of our approach is mainly
driven by how we divide the bounding box of the convex polygon into $k$
rectangular sub-regions of equal area and what would be the aspect ratios of
those sub-rectangles. Here, we modify an algorithm presented in [21] for
solving the $k$-Centers problem. The difference between $k$-centers and the
$k$-medians problems is that the former minimizes the maximum distance between
each point and its closest center. This algorithm divides a rectangle into $k$
equal area sub-rectangles and we use it as our partitioning subroutine.
Similar to our constructive algorithm, our subdivision algorithm takes a
convex polygon $C$ and an integer $k$ and gives a partition of $C$ into $k$
sub-regions and then places a median point at the center of each sub-region.

####  5.1 Description of the Subdivision Algorithm

Similar to the constructive algorithm, our subdivision algorithm first creates
the bounding box aligned with the coordinate axes. Then it breaks the bounding
box into $k$ area-equal sub-rectangles with up to 6 different configurations.
In each configuration, our algorithm first divides the bounding box into two
parts, horizontally or vertically. Based on the number of sub-rectangles in
each part, the algorithm finds the dividing point in a way that the area of
sub-rectangles in the first part be equal to the area of sub-rectangles in the
other part. Beside equal areas, all sub-rectangles in the same part have the
same aspect ratios. This partitioning scheme is sketched in Figure 12 and
described in Algorithm 3. Then our algorithm investigates these configurations
and the configuration with the smallest maximum aspect ratio of sub-rectangles
is selected as the final configuration. If the maximum aspect ratio in two or
more configurations are the same, the algorithm compares the minimum aspect
ratio of sub-rectangles in different configurations and chooses the one with
the lower value as the final configuration. Figure 13 shows a sample of the
output of the subdivision algorithm described in Algorithm 4.

(a) $\text{``flag''}={\tt VERTICAL}$ (b) $\text{``flag''}={\tt HORIZONTAL}$

Figure 12: The output of Algorithm 3 where
$(p_{1},q_{1},p_{2},q_{2})=(4,3,6,5)$ and $\ell$ is as indicated. We subdivide
the rectangle into two grids, one of which has $4\times 3$ rectangles and one
of which has $6\times 5$ rectangles; the width and height of these two grids
is determined by $\ell$. The above images are reproduced from Figure 6 of
[21].

Input: An axis-aligned rectangle $R$, having dimensions $w\times h$, integers
$p_{1}$, $q_{1}$, $p_{2}$, $q_{2}$, a positive number $\ell$, and a “flag”
equal to VERTICAL or HORIZONTAL.

Output: A partition of $R$ into $p_{1}q_{1}+p_{2}q_{2}$ equal area rectangles.

1 /*
*************************************************************************************************
*/

2 if "flag" = VERTICAL then

3 Let $R_{1}$ be the left half of $R$, having dimensions $(w-\ell)\times h$;

4 Let $R_{2}$ be the right half of $R$, having dimensions $\ell\times h$;

5 Break $R_{1}$ into a $p_{1}\times q_{1}$ rectangular grid, and call the
rectangular cells $\boxdot_{1},...,\boxdot_{p_{1}q_{1}}$;

6 Break $R_{2}$ into a $p_{2}\times q_{2}$ rectangular grid, and call the
rectangular cells
$\boxdot_{p_{1}q_{1}+1},...,\boxdot_{p_{1}q_{1}+p_{2}q_{2}}$;

7

8else

9 Let $R_{1}$ be the bottom half of $R$, having dimensions $w\times(h-\ell)$;

10 Let $R_{2}$ be the top half of $R$, having dimensions $w\times\ell$;

11 Break $R_{1}$ into a $p_{1}\times q_{1}$ rectangular grid, and call the
rectangular cells $\boxdot_{1},...,\boxdot_{p_{1}q_{1}}$;

12 Break $R_{2}$ into a $p_{2}\times q_{2}$ rectangular grid, and call the
rectangular cells
$\boxdot_{p_{1}q_{1}+1},...,\boxdot_{p_{1}q_{1}+p_{2}q_{2}}$;

13

14 end if

15return $\boxdot_{1},...,\boxdot_{p_{1}q_{1}+p_{2}q_{2}}$;

Algorithm 3 Algorithm ${\sf
GridPartition}\>(R,p_{1},q_{1},p_{2},q_{2},\ell,\mbox{``flag''})$ takes as
input an axis-aligned rectangle $R$ and positive integers $p_{1},q_{1},p_{2}$
and $q_{2}$ and divides $R$ into $p_{1}q_{1}+p_{2}q_{2}$ sub-rectangles with
equal area.

1

Input: A convex polygon $C$ and an integer $k$.

Output: The locations of $k$ median points $p_{i},\;i=1,...,k$ in $C$ that
approximately minimize $\mathop{\rm FW}(C,k)$ within a factor of 2.002.

2 /*
*************************************************************************************************
*/

3 Rotate $C$ so that $\square C$ is aligned with the coordinate axes;

4 Let $\square C$ denote the minimum bounding box of $C$;

5 Let $w=\mathop{\rm width}(R)$;

6 Let $h=\mathop{\rm height}(R)$;

7 Set $p_{0}=\lfloor{\sqrt{wk/h}}\rfloor$,
$q_{0}=\lfloor{\sqrt{hk/w}}\rfloor$, $\mbox{minAR}=\infty$, and
$\mbox{minmaxAR}=\infty$;

8 for $p\in\\{p_{0}-1,p_{0},p_{0}+1\\}$ do

9 Set $q=\lfloor{k/p}\rfloor$;

10 if $p,q\geq 1$ then

11 Set $s=k-pq$, so that $k=pq+s=(p-s)q+s(q+1)$;

12 Let $\ell$ be the solution to
$\Big{(}\frac{w-\ell}{p-s}\Big{)}\Big{(}\frac{h}{q}\Big{)}=\Big{(}\frac{\ell}{s}\Big{)}\Big{(}\frac{h}{q+1}\Big{)}$
that satisfies $0\leq\ell\leq w$. If no such $\ell$ exists, let $\ell=0$;

13 Let $\boxdot_{1},...,\boxdot_{k}={\sf GridPartition}\>(\square
C,p-s,q,s,q+1,\ell,$ VERTICAL);

14 Let $(x^{\prime}_{1},...,x^{\prime}_{k})$ be the centers of the boxes
$\boxdot_{i}$;

15 if $\ell\neq 0$ then

16 Let $\mathop{\rm AR}_{1}=\max(\frac{wq^{2}}{hk},\frac{hk}{wq^{2}})$ and
$\mathop{\rm AR}_{2}=\max(\frac{w(q+1)^{2}}{hk},\frac{hk}{w(q+1)^{2}})$ and
$\mathop{\rm AR}=\max(AR_{1},AR_{2})$;

17

18 else

19 Let $\mathop{\rm AR}=\max(\frac{wq^{2}}{hk},\frac{hk}{wq^{2}})$;

20 end if

21 if $\mathop{\rm AR}<\mbox{minAR}$ then

22 Set $\mbox{minAR}=\mathop{\rm AR}$ and
$x_{1},...,x_{k}=x^{\prime}_{1},...,x^{\prime}_{k}$;

23 else

24 if $\mathop{\rm AR}=\mbox{minAR}$ and $\min(\mathop{\rm AR}_{1},\mathop{\rm
AR}_{2})<\mbox{minmaxAR}$ then

25 Set $\mbox{minAR}=\mathop{\rm AR}$ and $\mbox{minmaxAR}=\min(\mathop{\rm
AR}_{1},\mathop{\rm AR}_{2})$;

26 Set $x_{1},...,x_{k}=x^{\prime}_{1},...,x^{\prime}_{k}$;

27 end if

28

29 end if

30

31 end if

32

33 end for

34for $q\in\\{q_{0}-1,q_{0},q_{0}+1\\}$ do

35 Set $p=\lfloor{k/q}\rfloor$;

36 if $p,q\geq 1$ then

37 Set $s=k-pq$, so that $k=pq+s=(q-s)p+s(p+1)$;

38 Let $\ell$ be the solution to
$\Big{(}\frac{w}{p}\Big{)}\Big{(}\frac{h-\ell}{q-s}\Big{)}=\Big{(}\frac{w}{p+1}\Big{)}\Big{(}\frac{\ell}{s}\Big{)}$
that satisfies $0\leq\ell\leq h$. If no such $\ell$ exists, let $\ell=0$;

39 Let $\boxdot_{1},...,\boxdot_{k}={\sf GridPartition}\>(\square
C,p,q-s,p+1,s,\ell,$ HORIZONTAL);

40 Let $(x^{\prime}_{1},...,x^{\prime}_{k})$ be the centers of the boxes
$\boxdot_{i}$;

41 if $\ell\neq 0$ then

42 Let $\mathop{\rm AR}_{1}=\max(\frac{hp^{2}}{wk},\frac{wk}{hp^{2}})$ and
$\mathop{\rm AR}_{2}=\max(\frac{h(p+1)^{2}}{wk},\frac{wk}{h(p+1)^{2}})$ and
$\mathop{\rm AR}=\max(AR_{1},AR_{2})$;

43

44 else

45 Let $\mathop{\rm AR}=\max(\frac{hp^{2}}{wk},\frac{wk}{hp^{2}})$;

46

47 end if

48 if $\mathop{\rm AR}<\mbox{minAR}$ then

49 Set $\mbox{minAR}=\mathop{\rm AR}$ and
$x_{1},...,x_{k}=x^{\prime}_{1},...,x^{\prime}_{k}$;

50 else

51 if $\mathop{\rm AR}=\mbox{minAR}$ and $\min(\mathop{\rm AR}_{1},\mathop{\rm
AR}_{2})<\mbox{minmaxAR}$ then

52 Set $\mbox{minAR}=\mathop{\rm AR}$ and $\mbox{minmaxAR}=\min(\mathop{\rm
AR}_{1},\mathop{\rm AR}_{2})$;

53 Set $x_{1},...,x_{k}=x^{\prime}_{1},...,x^{\prime}_{k}$;

54 end if

55

56 end if

57

58 end if

59

60 end for

61for $i\in\\{1,...,k\\}$ do

62 if $x_{i}\in C$ then

63 Set $p_{i}=x_{i}$;

64

65 else

66 if $R_{i}\cap C$ is nonempty then

67 Let $R_{i}^{{}^{\prime}}$ be the minimum axis-aligned bounding box of
$R_{i}\cap C$ and let $c_{i}^{{}^{\prime}}$ denote its center;

68 Set $p_{i}=c_{i}^{{}^{\prime}}$;

69

70 else

71 Place $p_{i}$ anywhere in $C$;

72

73 end if

74

75 end if

76

77 end for

78return $p_{1},...,p_{k}$;

Algorithm 4 Algorithm ${\sf SubdivideFW}$ takes a polygon $C$ and integer $k$
as input, partitions $C$ into $k$ sub-regions and finds locations for $k$
median points.

Figure 13:  Six different configurations of dividing a bounding box of a
polygon into 14 sub-rectangles using Algorithm 4. The width of bounding box is
1.4917 and the height is 0.9085. In each configuration, the box is divided
into two parts. All 14 sub-rectangles have same areas. The bottom right figure
is chosen among these six configurations because of having the best maximum
aspect ratio of sub-rectangles. The aspect ratio of sub-rectangles in the top
part of this configuration is 1.0876 and for the sub-rectangles in the bottom
part is 1.4367.

####  5.2 Analysis of Algorithm 4

#####  5.2.1 Running Time of Algorithm 4

This algorithm can be performed with running time $\mathcal{O}(n+k+k\log n)$.
This is because Algorithm 3 takes $\mathcal{O}(k)$ operations to partition the
rectangle and Algorithm 4 requires $\mathcal{O}(n)$ operations to find a
minimum bounding box of $C$. The last step of Algorithm 4 consists of moving
the center points to $C$ when necessary, which takes $\mathcal{O}(k\log n)$
operations using a point-in-polygon algorithm [20].

#####  5.2.2 Aspect Ratios in Algorithm 4

Similar to Section 4.2.2, we first adopt Assumptions 1 and 2 to simplify the
analysis of aspect ratios.

######  Lemma 12.

If $w/k\geq 0.5$, one of the configurations of Algorithm 4 divides the
bounding box into $k$ rectangles each with dimensions $\frac{w}{k}\times 1$.

###### Proof.

We know that $q_{0}=\lfloor\sqrt{hk/w}\rfloor=\lfloor\sqrt{k/w}\rfloor$. It is
easy to show that if $0.5\leq w/k\leq 1$, we will have $q_{0}=1$ and if
$w/k>1$, we have $q_{0}=0$. In all cases, we have a configuration with $q=1$
and hence $p=\lfloor k/q\rfloor=k$. In this case, $s=\ell=0$ and the bounding
box would be partitioned into $k$ rectangles with dimensions
$\frac{w}{k}\times 1$. ∎

######  Claim 13.

For $p=p_{0}+1$, we always have $q=q_{0}-1$ or $q=q_{0}$.

###### Proof.

When $p=p_{0}+1$, we have
$q=\Bigl{\lfloor}\frac{k}{1+p_{0}}\Bigr{\rfloor}=\Bigl{\lfloor}\frac{k}{1+\lfloor\sqrt{kw}\rfloor}\Bigr{\rfloor}$.
We know that $\frac{\sqrt{kw}}{1+\lfloor\sqrt{kw}\rfloor}<1$. We have,

$\frac{\sqrt{kw}}{1+\lfloor\sqrt{kw}\rfloor}<1\;\Longrightarrow\;\frac{k}{1+\lfloor\sqrt{kw}\rfloor}<\frac{\sqrt{k}}{\sqrt{w}}\;\Longrightarrow\;q=\Bigl{\lfloor}\frac{k}{1+\lfloor\sqrt{kw}\rfloor}\Bigr{\rfloor}\leq\Bigl{\lfloor}\sqrt{\frac{k}{w}}\Bigr{\rfloor}=q_{0}$

For the lower bound we start with the fact that $w\geq 1$.

$w\geq 1\Rightarrow
w\sqrt{k}+\sqrt{w}\geq\sqrt{k}\;\Rightarrow\;w\sqrt{k}+\sqrt{w}+k\sqrt{w}\geq\sqrt{k}+k\sqrt{w}\;\Rightarrow\;\sqrt{w}(k+1+\sqrt{kw})\geq\sqrt{k}(1+\sqrt{wk})\;\Rightarrow\;$
$\dfrac{\sqrt{k}}{\sqrt{w}}\leq\dfrac{k+1+\sqrt{kw}}{1+\sqrt{kw}}\;\Rightarrow\;\dfrac{\sqrt{k}}{\sqrt{w}}-1\leq\dfrac{k}{1+\sqrt{kw}}\;\Rightarrow\;\Bigl{\lfloor}{\sqrt{\dfrac{k}{w}}}\Bigr{\rfloor}-1\leq\Bigl{\lfloor}\dfrac{k}{1+\sqrt{kw}}\Bigr{\rfloor}\leq\Bigl{\lfloor}\dfrac{k}{1+\lfloor\sqrt{kw}\rfloor}\Bigr{\rfloor}\;\Rightarrow\;q_{0}-1\leq
q$

Hence, for $p=p_{0}+1$, we have $q\in\\{q_{0}-1,q_{0}\\}$. ∎

######  Lemma 14.

At least one of the configurations made with $p=p_{0}$ or $p=p_{0}+1$, has
$q=q_{0}$

###### Proof.

By 13, if we set $p=p_{0}+1$, we would have $q=q_{0}$ or $q=q_{0}-1$. If in
this case $q=q_{0}$, we are done. Therefore, it suffices to show that if
$q=q_{0}-1$ when $p=p_{0}+1$, in the configuration that we set $p=p_{0}$, we
will have $q=q_{0}$.
We prove this in two parts. First, we show that if $p=p_{0}$, we will have
$q=\lfloor k/p\rfloor=\lfloor k/p_{0}\rfloor\geq q_{0}$ and then we show that
$q<q_{0}+1$. First,

$p_{0}=\lfloor\sqrt{wk}\rfloor\;\Rightarrow\;\frac{k}{p_{0}}=\frac{k}{\lfloor\sqrt{wk}\rfloor}\geq\frac{k}{\sqrt{wk}}=\sqrt{\dfrac{k}{w}}\geq\lfloor\sqrt{\dfrac{k}{w}}\rfloor=q_{0}\;\Rightarrow\;q=\lfloor\frac{k}{p_{0}}\rfloor\geq
q_{0}$

Second, suppose that when $p=p_{0}+1$, we have
$q=\lfloor\frac{k}{p_{0}+1}\rfloor=q_{0}-1$, then

$\frac{k}{p_{0}+1}=q_{0}-\alpha,\quad 0<\alpha\leq
1\;\Longrightarrow\;k=p_{0}q_{0}+q_{0}-\alpha
p_{0}-\alpha\;\Longrightarrow\;\frac{k}{p_{0}}=q_{0}+\frac{q_{0}}{p_{0}}-\alpha-\frac{\alpha}{p_{0}}$

Therefore, for the case of $p=p_{0}$ we have

$q=\lfloor\frac{k}{p_{0}}\rfloor=q_{0}+\lfloor\frac{q_{0}}{p_{0}}-\alpha-\frac{\alpha}{p_{0}}\rfloor$

It is enough to show that $\frac{q_{0}}{p_{0}}-\alpha-\frac{\alpha}{p_{0}}<1$.
Since $w\geq h$, we always have $p_{0}\geq q_{0}$ and thus,
$\frac{q_{0}}{p_{0}}\leq 1$. Since $\alpha>0$, we can conclude that
$\frac{q_{0}}{p_{0}}-\alpha-\frac{\alpha}{p_{0}}<1$. ∎

Using Lemmas 12 and 14 we can analyze the aspect ratios of the output
rectangles of Algorithm 4 by considering several cases. To avoid repetition we
combine this section with Section 6.2.2.

###  6 Approximation Factors

####  6.1 Upper Bound on $\mathop{\rm FW}(C,k)$ for Algorithms 2 and 4

In order to derive an upper bound for $\mathop{\rm FW}(C,k)$ under Algorithms
2 and 4, we first make a straightforward observation that validates our use of
the upper bounding function $\Phi_{UB}$ from Equation (6). Recall that
Algorithm 2 fits $k$ rectangles of equal area in the bounding box of $C$,
i.e., $R=\square C$, Algorithm 4 partitions $\square C$ into $k$ rectangles of
equal area, and that in both algorithms $C$ is initially oriented so that its
diameter is aligned with the coordinate $x$-axis. It is easy to see, then,
that for any rectangle $R_{i}$ produced by either of these algorithms, it must
be the case that the region $R_{i}\cap C$ contains a horizontal line segment
whose length is equal to width($R_{i}\cap C$) (a similar fact was previously
proven in Claim 4.1 of [22]). Thus, we can safely conclude that, if Algorithms
2 and 4 produce $k$ rectangles with equal areas and dimensions $w_{i}\times
h_{i}$, where $w_{i}$ is the length of the longer edge, a valid upper bound
for $\mathop{\rm FW}(C,k)$ is indeed $\sum_{i}\Phi_{UB}(A_{i},w_{i},h_{i})$,
where $A_{i}=\text{Area}(R_{i}\cap C)$. By (6) we have

$\mathop{\rm FW}(C,k)=\sum_{i=1}^{k}\mathop{\rm FW}(C\cap
R_{i})\leq\sum_{i=1}^{k}\Phi_{UB}(A_{i},w_{i},h_{i})$

It is not hard to verify algebraically that, for any fixed $A_{i}$, the
function $\Phi_{UB}\left(A_{i},w_{i},h_{i}\right)$ is maximized when the
aspect ratio of $R_{i}$ is as large as possible. Let
$\beta=\max_{i=1,...,k}\mathop{\rm AR}(R_{i})$. Thus, for an upper bound, and
using Lemma 5, we can replace $w_{i}$ with $\sqrt{2A_{i}\beta}$ and $h_{i}$
with $\sqrt{2A_{i}/\beta}$. By observing that $\Phi_{UB}$ is concave in
$A_{i}$, we ultimately conclude that:

$\mathop{\rm FW}(C,k)\leq
k\cdot\Phi_{UB}(\frac{A}{k},\sqrt{\frac{2A\beta}{k}},\sqrt{\frac{2A}{k\beta}}\,),$
(7)

We can derive a more explicit upper bound for $\mathop{\rm FW}(C,k)$ by
considering the relationship between $k$ and $w$, as described in the next
section.

####  6.2 Approximation Factor of Algorithms 2 and 4

We analyze each algorithm by breaking all possibilities into several cases in
Sections 6.2.1 and 6.2.2. The following theorem summarizes the results of this
analysis.

######  Theorem 15.

The solution to the $k$-medians problem provided by Algorithm 2 and Algorithm
4 are within factor 2.002 of optimality.

#####  6.2.1 Approximation Factor of Algorithm 2

We break our analysis into three possible cases: $0.5\leq w/k\leq 1000$,
$w/k>1000$, and $w/k<0.5$. For simplicity in the rest of the analysis, let
$\alpha=A/k$, and $z=w/k$. Approximation factors for each of these cases are
as follows:

CASE I $\bm{(0.5\leq z\leq 1000}$): By Lemma 6, in this case, our algorithm
divides the bounding box into $k$ rectangles each with dimensions
$\frac{w}{k}\times 1$. For the upper bound we have

$\mathop{\rm FW}(C,k)\leq
k\cdot\Phi_{UB}(\frac{A}{k},\frac{w}{k},1)=k\cdot\Phi_{UB}(\alpha,z,1)$

For the lower bound we have $\mathop{\rm FW}(C,k)\geq
k\cdot\Phi_{LB}(\frac{A}{k},1)=k\cdot\Phi_{LB}(\alpha,1)$. To pick the best
lower bound in (2), we investigate two cases depending on the value of
$\alpha$.

CASE I.1 ($\bm{\alpha\leq\frac{\pi}{4}}$): The smallest bounding box of a
convex polygon has an area that is no greater than twice the area of the
polygon. Thus, we have the inequality $z/2\leq\alpha\leq\min(z,\pi/4)$, where
$z$ is bounded above by $\pi/2$. The lower bound is derived from (3), i.e.,
$\Phi_{LB}(C)$ comes from the first case in (2). Computational analysis
demonstrates that in this case the approximation factor
$\rho=\Phi_{UB}/\Phi_{LB}$ is bounded above by 1.88, which occurs at $z=0.5$
and $\alpha=z/2=0.25$ (see Figure 14). Note that while Figure 14 shows a spike
in the ratio $\Phi_{UB}/\Phi_{LB}$ around $z=1$, the algorithm actually
generates the results closer to optimality when $z=1$. This discrepancy arises
because the upper bound we use in our proofs amplifies the ratio near $z=1$.

Figure 14:  The approximation factor of Algorithm 2 when
$\alpha\leq\dfrac{\pi}{4}$, $z\geq 0.5$ and $\alpha=\dfrac{z}{2}$.

CASE I.2 $\bm{(\alpha>\frac{\pi}{4}})$: For this case, we can establish that
$z\geq\frac{\pi}{4}$ due to the given condition that $z/2\leq\alpha\leq z$. In
this scenario, the value of $\Phi_{LB}(C)$ corresponds to the second case in
(2). Computational analysis shows, as illustrated in Figure 15, that in this
case $\rho\leq 2$ and the maximum for each value of $z$ occurs at
$\alpha=z/2$.

Figure 15:  The approximation factor of Algorithm 2 when
$\alpha>\dfrac{\pi}{4}$, $0.5\leq z\leq 1000$ and $\alpha=\dfrac{z}{2}$.
Bottom figure shows the bounds ratio for $z\leq 10$.

CASE II $\bm{(z>1000)}$: In this case, similar to the last case our algorithm
divides the bounding box into $k$ rectangles each with dimensions
$\frac{w}{k}\times 1$. However, since the bounding box $\square C$ is very
long and skinny we can approximate $\Phi_{UB}$ using the $L_{1}$ norm and
$\Phi_{LB}$ using $L_{\infty}$ norm. As the value of $z$ increases and
consequently, the aspect ratio of the sub-rectangles becomes larger, the value
of ${\mathop{\rm FW}}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(z,1)$ approaches
${\mathop{\rm FW}}_{1/2}(z,2)$. This phenomenon occurs because when the width
is significantly larger than the height of the rectangle, the change of the
Fermat-Weber due to displacement of Fermat-Weber point along the rectangle’s
height is minimal. Hence, we can see $\alpha_{c}$ defined as $A_{c}$ in (6),
i.e., ${\mathop{\rm
FW}}_{1/2}\left(z,\frac{2\alpha_{c}}{z}\right)={\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}\left(z,1\right)$,
for a large $z$ will becomes equal to $z$, i.e., $\alpha_{c}=z$. Hence, the
upper bound is the concave envelope of $\mathop{\rm
FW}_{1/2}\left(z,\frac{2\alpha_{c}}{z}\right)$ or
$\nicefrac{{\alpha}}{{z}}\,{\mathop{\rm FW}}_{\mathbin{\text{ \leavevmode\hbox
to4.34pt{\vbox to2.98pt{\pgfpicture\makeatletter\hbox{\hskip
0.13562pt\lower-0.13562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(z,1)$ for all
values of $\alpha$. Under an $L_{1}$ norm, we have ${\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.34pt{\vbox
to2.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.13562pt\lower-0.13562pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.27126pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{2.7125pt}\pgfsys@lineto{4.06874pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.06874pt}{2.7125pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(z,1)=0.25(z^{2}+z)$
(from Equation (9) in Lemma 17 in Section A of the Online Supplement). The
upper bound, therefore is precisely:

$\Phi_{UB}(\alpha,z,1)=\frac{\alpha}{z}0.25(z^{2}+z)=0.25\alpha(z+1)$

For the lower bound, it is easy to see that instead of the slab-shape in
Figure 2a, when we use the $L_{\infty}$ norm, the shape within our slab of
height 1 with minimal Fermat-Weber value is simply a rectangle with dimensions
$\alpha\times 1$, whose Fermat-Weber value is $0.25\alpha^{2}$ (from Equation
(10) in Lemma 17 in Section A of the Online Supplement). Therefore, for the
lower bound we have

$\Phi_{LB}(\alpha,1)=0.25\alpha^{2}$

The approximation factor is therefore:

$\rho=\frac{\Phi_{UB}}{\Phi_{LB}}=\frac{0.25\alpha(z+1)}{0.25\alpha^{2}}=\frac{z+1}{\alpha}<2.002\,,$

since $\alpha\geq z/2$ and $z>1000$.

Case III $\bm{(z<0.5)}$: Theorem 11 shows that Algorithm 1 divides the
bounding box into $k$ rectangles, while the aspect ratio of all except one
rectangle is less than or equal to 2 and the aspect ratio of the last
rectangle is at most 3.

We know that once the aspect ratio of the sub-rectangles get larger, the
Fermat-Weber value and hence the approximation factor of our algorithm
increases. Here, we consider the worst case for the aspect ratios of the sub-
rectangles and find the approximation factor. According to Theorem 11, all
sub-rectangles, except one, have an aspect ratio of 2 or less, while the last
sub-rectangle has an aspect ratio of at most 3. Therefore, we consider a
configuration with $k-1$ sub-rectangles of dimensions
$\sqrt{2z}\times\sqrt{z/2}$ (having an aspect ratio of 2) and one sub-
rectangle with dimensions $\sqrt{3z}\times\sqrt{z/3}$ (having an aspect ratio
of 3). Since the aspect ratio of the sub-rectangles are not identical in this
worst-case scenario, we initially fix the area of the polygon contained within
the sub-rectangle with an aspect ratio of 3. Then, assuming that the other
sub-rectangles are identical, we proceed with the analysis similar to the
previous case. We denote $\alpha_{1}$ as the area of the polygon within the
sub-rectangle with an aspect ratio of 3 and $\alpha_{2}$ as the area of the
polygon within the other sub-rectangles. Recall that this area must be equal
within those sub-rectangles in order to maximize the approximation factor.
Hence, $\alpha_{1}\leq z$ and $\frac{A-\alpha_{1}}{k-1}\leq\alpha_{2}\leq z$.
The upper bound is calculated by summing the upper bound for the sub-rectangle
with aspect ratio 3 and the other sub-rectangles.

$\Phi_{UB}=\Phi_{UB_{(\mathop{\rm AR}_{\mathbin{\text{ \leavevmode\hbox
to3.44pt{\vbox to2.37pt{\pgfpicture\makeatletter\hbox{\hskip
0.10764pt\lower-0.10764pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.21529pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.15277pt}\pgfsys@lineto{3.22916pt}{2.15277pt}\pgfsys@lineto{3.22916pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{3.22916pt}{2.15277pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}=3)}}+(k-1)\cdot\Phi_{UB_{(\mathop{\rm
AR}_{\mathbin{\text{ \leavevmode\hbox to3.44pt{\vbox
to2.37pt{\pgfpicture\makeatletter\hbox{\hskip 0.10764pt\lower-0.10764pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.21529pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.15277pt}\pgfsys@lineto{3.22916pt}{2.15277pt}\pgfsys@lineto{3.22916pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{3.22916pt}{2.15277pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}=2)}}$

In the case of a rectangle with an aspect ratio of 3, the value of
$\alpha_{c}$ can be calculated as $0.8844z$, where $\alpha_{c}$ is defined by
the equation $\alpha_{c}:{\mathop{\rm
FW}}_{1/2}(z,\frac{2\alpha_{c}}{z})={\mathop{\rm FW}}_{\mathbin{\text{
\leavevmode\hbox to4.82pt{\vbox to3.32pt{\pgfpicture\makeatletter\hbox{\hskip
0.1507pt\lower-0.1507pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(z,1)$.
Consequently, when we set $\alpha_{1}$ as a fixed value, we compare it with
$\alpha_{c}$. If $\alpha_{1}$ is less than $\alpha_{c}$, we consider
$\frac{\alpha_{1}}{0.8844z}{\mathop{\rm FW}}_{\mathbin{\text{ \leavevmode\hbox
to4.82pt{\vbox to3.32pt{\pgfpicture\makeatletter\hbox{\hskip
0.1507pt\lower-0.1507pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\sqrt{3z},\sqrt{z/3})$
as the upper bound. However, if $\alpha_{1}$ is greater than or equal to
$\alpha_{c}$, we consider ${\mathop{\rm FW}}_{\mathbin{\text{ \leavevmode\hbox
to4.82pt{\vbox to3.32pt{\pgfpicture\makeatletter\hbox{\hskip
0.1507pt\lower-0.1507pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\sqrt{3z},\sqrt{z/3})$
as the upper bound. In the case of a rectangle with an aspect ratio of 2, the
value of $\alpha_{c}$ can be calculated as $0.8405z$. Then for $\alpha_{2}\leq
0.8405z$, we consider $\frac{\alpha_{2}}{0.8405z}{\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.82pt{\vbox
to3.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.1507pt\lower-0.1507pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\sqrt{2z},\sqrt{z/2})$
as the upper bound and for $\alpha_{2}>0.8405z$ we consider ${\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.82pt{\vbox
to3.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.1507pt\lower-0.1507pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\sqrt{2z},\sqrt{z/2})$.
Therefore, the upper bound is

$\Phi_{UB}=\min\left\\{\frac{\alpha_{1}}{0.8844z}{\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.82pt{\vbox
to3.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.1507pt\lower-0.1507pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\sqrt{3z},\sqrt{\dfrac{z}{3}}),{\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.82pt{\vbox
to3.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.1507pt\lower-0.1507pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\sqrt{3z},\sqrt{\dfrac{z}{3}})\right\\}+(k-1)\cdot\min\left\\{\frac{\alpha_{2}}{0.8405z}{\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.82pt{\vbox
to3.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.1507pt\lower-0.1507pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\sqrt{2z},\sqrt{\dfrac{z}{2}}),{\mathop{\rm
FW}}_{\mathbin{\text{ \leavevmode\hbox to4.82pt{\vbox
to3.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.1507pt\lower-0.1507pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}\pgfsys@setlinewidth{0.30139pt}\pgfsys@invoke{
}\pgfsys@roundjoin\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{3.01389pt}\pgfsys@lineto{4.52083pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{4.52083pt}{3.01389pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\sqrt{2z},\sqrt{\dfrac{z}{2}})\right\\}$

For the lower bound we use the first case in (2) that is
$\Phi_{LB}=\frac{2}{3}\pi r^{3}$. Recall that in order to determine the lower
bound, we must first have knowledge of the polygon’s area and divide it to $k$
to find the value of $\alpha$. Then we equate $\alpha$ to $\pi r^{2}$ to solve
for $r$ and finally calculate the lower bound. In this context,

$\alpha=\frac{\alpha_{1}+(k-1)\alpha_{2}}{k},$

and it is easy to see that if $k$ increases, the effect of the sub-rectangle
with aspect ratio of 3 decreases. So, the worst case happens for $k=3$.
Computational analysis shows that in this situation, the maximum approximation
factor happens for $\alpha_{1}=0.8844z$ and
$\alpha_{2}=\dfrac{A-\alpha_{1}}{2}=$ and its value is 1.9614 (i.e., $\rho\leq
1.9614$). Figure 16 shows the maximum approximation factor $\rho$ for values
of $\alpha_{1}$.

Figure 16:  The approximation factor of Algorithm 2 when $k=3$ and
$\alpha_{2}=\frac{(k/2)z-\alpha_{1}}{k-1}=\frac{1.5z-\alpha_{1}}{2}$.

#####  6.2.2 Approximation Factor of Algorithm 4

To find the approximation factor of this algorithm, we investigate several
cases that are summarized in Table 1. The last column shows the maximum
approximation ratio for each case.

Table 1:  Different investigated cases for finding the approximation factor of Algorithm 4. Case |  Condition |  $\bm{\rho_{\max}}$
---|---|---
CASE 1 | $w/k\leq 1/9$ | 1.8530
CASE 2 | $1/9\leq w/k<1/8$ | 1.8446
CASE 3 | $1/8\leq w/k<2/9$ | 1.8765
CASE 4 | $2/9\leq w/k\leq 1/4$ | 1.8408
CASE 5 | $1/4<w/k<0.5$ | 1.9614
CASE 6 | $w/k\geq 0.5$ | 2.002

CASE 1 $\bm{(w/k\leq 1/9)}$: In this case, we have
$q_{0}=\lfloor{\sqrt{hk/w}}\rfloor=\lfloor{\sqrt{k/w}}\rfloor\geq 3$. By Lemma
14, we know that at least one of the configurations made with $p=p_{0}$ or
$p=p_{0}+1$, has $q=q_{0}$. The maximum aspect ratio of created sub-rectangles
is

$\mathop{\rm AR}=\max\\{\frac{w(q+1)^{2}}{k},\frac{k}{wq^{2}}\\}$

Suppose that $q=q_{0}$. We have:

$\frac{w(q_{0}+1)^{2}}{k}\leq\frac{w(\sqrt{\dfrac{k}{w}}+1)^{2}}{k}=(1+\sqrt{\frac{w}{k}})^{2}\leq\frac{16}{9}$

Moreover, we have:

$q_{0}=\lfloor{\sqrt{k/w}}\rfloor\Longrightarrow
q_{0}^{2}\leq\frac{k}{w}<(q_{0}+1)^{2}\Longrightarrow
1\leq\frac{k}{wq_{0}^{2}}<\dfrac{(q_{0}+1)^{2}}{q_{0}^{2}}\Longrightarrow\frac{k}{wq_{0}^{2}}<\frac{16}{9}$

So, using the maximum aspect ratio $\mathop{\rm AR}=16/9$ for sub-rectangles
in this case and the first lower bound in (2), we will have
$\alpha_{c}=0.8279z$ and the maximum approximation factor is for $\alpha=z/2$
with value 1.8530.

CASE 2 $\bm{(1/9\leq w/k<1/8)}$: In this case, we have $q_{0}=2$. One of the
configurations that our algorithm generates, is achieved by setting
$q=q_{0}+1=3$ and $p=\lfloor\frac{k}{3}\rfloor$. If this configuration is made
of two grids, its worst-case aspect ratio is

$\mathop{\rm AR}=\max\\{\frac{wk}{p^{2}},\frac{(p+1)^{2}}{wk}\\}$

We investigate this case depending on different values of $\bmod(k,q=3)$.

  * •

$\bm{\bmod(k,3)=0}$

$\bmod(k,3)=0\Longrightarrow p=\frac{k}{3}\xrightarrow{s=0}\mathop{\rm
AR}=\max\\{\frac{wk}{k^{2}/9},\frac{k^{2}/9}{wk}\\}=\max\\{\frac{9w}{k},\frac{k}{9w}\\}\leq
1.125$

Note that in this case we have $s=0$ and $\ell=0$ and Algorithm 3 generates
only one grid. For this case, $\alpha_{c}=0.7836z$ and the maximum
approximation factor is for $\alpha=z/2$ with value 1.8408.

  * •

$\bm{\bmod(k,3)=1}$

$\bmod(k,3)=1\Longrightarrow p=\frac{k-1}{3}\Longrightarrow\mathop{\rm
AR}=\max\\{\frac{9kw}{(k-1)^{2}},\frac{(k+2)^{2}}{9kw}\\}$

Since $w\geq 1$ and $w/k<1/8$, we have $k\geq 10$. Using this inequality, we
will have $AR\leq 1.44$. Hence, $\alpha_{c}=0.8064z$ and the maximum
approximation factor is for $\alpha=z/2$ with value 1.8316.

  * •

$\bm{\bmod(k,3)=2}$

$\bmod(k,3)=2\Longrightarrow p=\frac{k-2}{3}\Longrightarrow\mathop{\rm
AR}=\max\\{\frac{9kw}{(k-2)^{2}},\frac{(k+1)^{2}}{9kw}\\}$

Since $w\geq 1$ and $w/k<1/8$, we would have $k\geq 11$. Using this
inequality, we will have $\mathop{\rm AR}\leq 1.68$. Hence,
$\alpha_{c}=0.8220z$ and the maximum approximation factor is for $\alpha=z/2$
with value 1.8446.

CASE 3 $\bm{(1/8\leq w/k\leq 2/9)}$: In this case, we have $q_{0}=2$. Again by
Lemma 14, we know that at least one of the configurations made with $p=p_{0}$
or $p=p_{0}+1$, has $q=q_{0}$. The maximum aspect ratio of sub-rectangles in
that configuration is

$\mathop{\rm AR}=\max\\{\frac{w(q_{0}+1)^{2}}{k},\frac{k}{wq_{0}^{2}}\\},$

where

$9/8\leq\frac{w(q_{0}+1)^{2}}{k}=\frac{9w}{k}\leq 2\,,\qquad\qquad\mbox{ and
}\qquad\qquad 9/8\leq\frac{k}{wq_{0}^{2}}=\frac{k}{4w}\leq 2.$

So, using maximum aspect ratio $\mathop{\rm AR}=2$ for sub-rectangles, we will
have $\alpha_{c}=0.8406z$ and the maximum approximation factor is for
$\alpha=z/2$ with value 1.8765.

CASE 4 $\bm{(2/9<w/k\leq 1/4)}$: In this case, we have $q_{0}=2$. One of the
configurations that our algorithm generates, is achieved by setting $q=q_{0}$
and $p=\lfloor\frac{k}{2}\rfloor$. We investigate this case based on different
values of $\bmod(k,q)$.

  * •

$\bm{\bmod(k,2)=0}$

$p=\frac{k}{2}\xrightarrow{s=0}\mathop{\rm
AR}=\max\\{\frac{kw}{p^{2}},\frac{p^{2}}{kw}\\}=\max\\{\frac{4w}{k},\frac{k}{4w}\\}\leq
1.125$

Hence, $\alpha_{c}=0.7836z$ and the maximum approximation factor is for
$\alpha=z/2$ with value 1.8408.

  * •

$\bm{\bmod(k,2)=1}$

$p=\frac{k-1}{2}\Longrightarrow\mathop{\rm
AR}=\max\\{\frac{(p+1)^{2}}{kw},\frac{kw}{p^{2}}\\}=\max\\{\frac{(k+1)^{2}}{4kw},\frac{4kw}{(k-1)^{2}}\\}\leq\max\\{\frac{9(k+1)^{2}}{8k^{2}},\frac{k^{2}}{(k-1)^{2}}\\}$

Since $w\geq 1$ and $w/k<1/4$, we have $k\geq 5$ and as a result the maximum
aspect ratio is 1.62. Having this aspect ratio, $\alpha_{c}=0.8182z$ and the
maximum approximation factor is for $\alpha=z/2$ with value 1.8403.

CASE 5 $\bm{(1/4<w/k<0.5)}$: In this case we have $q_{0}=1$. We investigate
this case based on different values of $\bmod(k,q)$.

  * •

$\bm{\bmod(k,2)=0}$
One of the configurations that our algorithm makes in this case, is obtained
by setting $q=q_{0}+1=2$ and $p=\lfloor\frac{k}{2}\rfloor=\frac{k}{2}$. Since
$s=0$, we have

$\mathop{\rm
AR}=\max\\{\frac{kw}{p^{2}},\frac{p^{2}}{kw}\\}=\max\\{\dfrac{4w}{k},\frac{k}{4w}\\}\leq
2$

In this case, using maximum aspect ratio of 2 for sub-rectangles, we will have
$\alpha_{c}=0.8406z$ and the maximum approximation factor is for $\alpha=z/2$
with value 1.8765.

  * •

$\bm{\bmod(k,2)=1}$
For this case, we consider three intervals.

    * –

$\bm{(1/4<w/k\leq 8/25)}$
In this case, one of the configurations that our algorithm makes, is obtained
by setting $q=q_{0}+1=2$ and $p=\lfloor\frac{k}{2}\rfloor=\frac{k-1}{2}$. The
maximum aspect ratio of sub-rectangles in that configuration is

$\mathop{\rm
AR}=\max\\{\frac{kw}{p^{2}},\frac{(p+1)^{2}}{kw}\\}=\max\\{\frac{4kw}{(k-1)^{2}},\frac{(k+1)^{2}}{4kw}\\}\leq\max\\{\frac{1.28k^{2}}{(k-1)^{2}},\frac{(k+1)^{2}}{2k^{2}}\\}\leq
2\,,$

where the upper bound comes from the fact that $w\geq 1$ and $w/k\leq 0.32$,
which gives $k\geq 5$. Therefore, the worst case of approximation factor is
the same as previous case which is 1.8765.

    * –

$\bm{(8/25<w/k\leq 18/49)}$
In this case, using the fact that $w\geq 1$ and $w/k\leq 18/49$, we can
observe that $k\geq 3$, which means we have either $k=3$ or $k\geq 5$.

For $k=3$, $w\geq 1$ and $w/3\leq 18/49$, we have $w\leq 54/49$. As a result,
$p_{0}=\lfloor\sqrt{wk/h}\rfloor=\lfloor\sqrt{3w}\rfloor=1$. So, we have a
configuration in which $p=p_{0}+1=2,\;q=1$ and $s=1$. This configuration makes
$(p-s)q=1$ rectangle with $\mathop{\rm
AR}=\max\\{\frac{3}{w},\frac{w}{3}\\}\leq 3$ and $(q+1)s=2$ rectangles with
$\mathop{\rm AR}=\max\\{\frac{4w}{3},\frac{3}{4w}\\}\leq 72/49$. Recall the
case that we had 2 rectangles with aspect ratio less than or equal to 2 and
one rectangle with aspect ratio less than or equal to 3 that we investigated
in the analysis of Algorithm 2. In that case, we showed that the maximum
approximation factor is 1.9614. Here, the aspect ratio of our rectangles are
less than or equal to that case. Hence, we can claim that the approximation
factor is less than 1.9614.

For $k\geq 5$, the maximum aspect ratio of the generated sub-rectangles is

$\mathop{\rm
AR}=\max\\{\frac{kw}{p^{2}},\frac{(p+1)^{2}}{kw}\\}=\max\\{\frac{4kw}{(k-1)^{2}},\frac{(k+1)^{2}}{4kw}\\}<2.296$

This gives $\alpha_{c}=0.8555z$ and hence $\rho\leq 1.9145$.

    * –

$\bm{(18/49<w/k<0.5)}$
In this case, we know that for one of the configurations where we set
$p=p_{0}$ or $p=p_{0}+1$, we get $q=q_{0}$. Then, the aspect ratio of
rectangles is less than $AR\leq\max\\{\frac{4w}{k},\frac{k}{w}\\}$ which gives
us the maximum of 49/18. In this case we get $\alpha_{c}=0.8741z$ and
$\rho\leq 1.9770$.

CASE 6 $\bm{(w/k\geq 0.5)}$: In this case, by Lemma 12, our algorithm divides
the bounding box into $k$ rectangles each with dimensions $\frac{w}{k}\times
1$. Hence, this case is identical to cases I and II of analysis of Algorithm
2, for which we showed $\rho\leq 2.002$.

###  7 Computational Results

As discussed above, both of our algorithms have very good worst-case
performance. However, it is still interesting to investigate their average
performance. In order to compare our algorithms and see their average
performance, we present in this section a simple computational experiment
using the convex hull of maps of Brookline, MA (Figure 17) and the state of
Massachusetts (Figure 18) as our initial polygon. We have partitioned the
polygon for a number of medians from 3 to 150 and for the cases when we have
several medians out of the polygon and we randomly place them inside the
polygon. We have run each case three times and use the average of these runs
in our computational results. Figure 19 shows the ratio of Fermat-Weber value
of our solution using ${\sf ConstructFW}$ and ${\sf SubdivideFW}$ Algorithms
to the lower bound.

Figure 17:  The map of Brookline partitioned into 111 sub-regions using ${\sf
SubdivideFW}$ Algorithm on the left and ${\sf ConstructFW}$ Algorithm on the
right. The median points corresponding to the center of the smaller rectangles
which are completely outside of the polygon are placed randomly in the
polygon. Figure 18:  The map of Massachusetts partitioned into 76 parts using
${\sf SubdivideFW}$ Algorithm on the left and ${\sf ConstructFW}$ Algorithm on
the right. The median points corresponding to the center of the smaller
rectangles which are completely outside of the polygon are placed randomly in
the polygon. Figure 19:  The approximation factor trend with respect to the
number of median points ($k$). Here, in approximation factor calculation, we
use actual Fermat-Weber value of our solutions over the lower bound. Figures
(a) and (b) show this ratio for ${\sf SubdivideFW}$ and ${\sf ConstructFW}$
Algorithms, respectively, on the map of Brookline, and Figures (c) and (d)
show the same for the map of Massachusetts.

####  7.1 Modification of the Algorithm

The computational results show a very satisfactory average performance.
However, we could still do better by applying a small modification in our
algorithms. In our algorithms we place the median points corresponding to
those sub-rectangles that are completely outside of the polygon, randomly
inside the polygon. Doing so we will only make the Fermat-Weber value better.
In Section 2 we mentioned that the way we do the placement for such points has
a minor impact on the performance of the algorithm. In this section we will
try to do a bit better than random.

For the ${\sf ConstructFW}$ Algorithm, we find the sub-rectangles made by the
algorithm that are fully in the polygon. For each sub-rectangle that is
completely outside of the polygon, we choose a strip and then add a new median
point to the rectangles fully in that strip. Assume that there are $i$ sub-
rectangles in the strip that are completely inside the polygon. So, the length
or width of those $i$ sub-rectangles decreases in a way that $i+1$ rectangles
fit. Then the $i+1$ median points will be the center of these new sub-
rectangles. The area of all new sub-rectangles would be $i/k(i+1)$ and the
center of rectangles have equal distance. To select a strip amongst all strips
we have for placing one new median, we use a measure for each strip and then
select the strip with maximum measure value. The measure is

$\frac{(CAR-NAR)\times CNR}{ONR},$

where CAR is the current aspect ratio of the sub-rectangles in the strip, NAR
is the new aspect ratio of the sub-rectangles by adding one new median point,
CNR is the current number of sub-rectangles in the strip, and ONR is the
original number of sub-rectangles in the strip before adding any median. After
adding one median, CAR, NAR and CNR for selected strip will be updated and the
process will be repeated until all outside median points are placed in a strip
inside the polygon.

We used the same measure and method for the ${\sf SubdivideFW}$ Algorithm. The
only difference was that based on the direction of dividing the bounding box
of the polygon into two sections, we use rows or columns that are generated,
instead of strips. For example if we have divided the box with a vertical
(horizontal) line into two parts, we consider columns (rows) instead of the
strips. Figures 20 and 21 show the results of using this modifcation on maps
of Brookline and Massachusetts.

Applying this modification and running the algorithms for Brookline and
Massachusetts maps, the ratio of Fermat-Weber value over the lower bound
decreases. Figure 22 shows the ratio of the Fermat-Weber value over the lower
bound when the outer medians points are placed randomly ($x$-axis) and when
they are placed using the modified point placement scheme ($y$-axis) on both
maps. One important parameter affecting the performance improvement is the
number of medians that are initially outside of the polygon. The more we have
the outer median points, the more potential there is for improvement by this
modification. The weighted average improvement of applying this modification
on the ${\sf SubdivideFW}$ Algorithm on Brookline and Massachusetts map is
2.14% and 3.45%, respectively. This value is 2.06% and 3.64% for the ${\sf
ConstructFW}$ Algorithm.

Figure 20:  The map of Brookline partitioned into 111 parts using ${\sf
SubdivideFW}$ Algorithm on the left and ${\sf ConstructFW}$ Algorithm on the
right, where the median points corresponding to the center of the sub-
rectangles which are completely outside of the polygon are placed in the
polygon using the modified point placement scheme. Figure 21: The map of
Massachusetts partitioned into 76 parts using ${\sf SubdivideFW}$ Algorithm on
the left and ${\sf ConstructFW}$ Algorithm on the right, where the median
points corresponding to the center of the sub-rectangles which are completely
outside of the polygon are placed in the polygon using the modified point
placement scheme. Figure 22:  The ratio of Fermat-Weber value over the lower
bounds when the outer median points are placed randomly ($x$-axis) and when
they are placed using the the modified point placement scheme ($y$-axis). The
upper figures refer to the Brookline’s map and the lower refer to
Massachusetts’ map. The left figures show the ratios on ${\sf SubdivideFW}$
Algorithm and the right figures show it for the ${\sf ConstructFW}$ algorithm.

###  8 Conclusion

We have presented two approximation algorithms for finding the location of $k$
median points in a convex polygon $C$ with $n$ vertices. Our algorithms
partition $C$ into $k$ sub-regions and then take the center of each sub-region
as a median point. Both algorithms have a computational complexity of
$\mathcal{O}(n+k+k\log n)$. This fact together with the worst-case performance
analysis and the average performance results show that our algorithms are
capable of finding high quality solutions efficiently. Potential directions
for future research could be considering $C$ to be a polygon with obstacles
(holes) or a general convex region and application of the presented algorithms
to the similar location optimization problems.

### References

  * [1] Christos H. Papadimitriou.  Worst-case and probabilistic analysis of a geometric location problem.  SIAM Journal on Computing, 1981.
  * [2] Sanjeev Arora, Prabhakar Raghavan, and Satish Rae.  Approximation schemes for euclidean k-medians and related.  Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 106–113, 1998.
  * [3] Yair Bartal.  Probabilistic approximation of metric spaces and its algorithmic applications.  Proceedings of 37th Conference on Foundations of Computer Science, pages 184–193, 1996.
  * [4] O Kariv and SL Hakimi.  An algorithmic approach to network location problems. II: The p-medians.  SIAM Journal on Applied Mathematics, 37(3):539–560, 1979.
  * [5] Arie Tamir.  An o (pn2) algorithm for the p-median and related problems on tree graphs.  Operations research letters, 19(2):59–64, 1996.
  * [6] Yair Bartal.  On approximating arbitrary metrices by tree metrics.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 161–168, 1998.
  * [7] Moses Charikar, Chandra CHekur, Ashish Goel, and Sudipto Guha.  Improved combinatorial algorithms for the facility location and k-median problems.  Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 114–123, 1998.
  * [8] Moses Charikar and Sudipto Guha.  A constant-factor approximation algorithm for the k-median problem.  Journal of Computer and System Sciences, 65.1:129–149, 2002.
  * [9] Vijay V. Vazirani Kamal Jain.  Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation.  Journal of the ACM, 48:274–296, 2001.
  * [10] Amin Saberi Kamal Jain, Mohammad Mahdian.  A new greedy approach for facility location problems.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 48:731–740, 2002.
  * [11] Ola Svensson Shi Li.  Approximating k-median via pseudo-approximation.  SIAM Journal on Computing, 45, 2013.
  * [12] Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh.  An improved approximation for k-median and positive correlation in budgeted optimization.  ACM Transactions on Algorithms (TALG), 13(2):1–31, 2017.
  * [13] Sándor P Fekete, Joseph S B. Mitchell, and Karin Weinbrecht.  On the continuous weber and k -median problems.  Proceedings of the sixteenth annual symposium on Computational geometry, pages 70–79, 2000.
  * [14] John Gunnar Carlsson, Fan Jia, and Ying Li.  An approximation algorithm for the continuous k-medians problem in a convex polygon.  INFORMS Journal on Computing, 26:280–289, 2014.
  * [15] Paz Carmi, Sariel Har-Peled, and Matthew J Katz.  On the fermat–weber center of a convex object.  Computational Geometry, 32(3):188–195, 2005.
  * [16] A. Karim Abu-Affash and Matthew J. Katz.  Improved bounds on the average distance to the fermat–weber center of a convex object.  Inf. Process. Lett., 109(6):329–333, February 2009.