11institutetext: N. Dupin 22institutetext: Laboratoire de Recherche en
informatique (LRI), CNRS, Université Paris-Saclay, France
22email<EMAIL_ADDRESS>33institutetext: F. Nielsen
44institutetext: Sony Computer Science Laboratories Inc, Tokyo, Japan
44email<EMAIL_ADDRESS>
55institutetext: E. Talbi 66institutetext: Univ. Lille, UMR 9189 - CRIStAL -
Centre de Recherche en Informatique Signal et Automatique de Lille, F-59000
Lille, France
66email<EMAIL_ADDRESS>
# k-medoids and p-median clustering are solvable in polynomial time for a 2d
Pareto front

Nicolas Dupin  Frank Nielsen  El-Ghazali Talbi
<EMAIL_ADDRESS>Nicolas Dupin  Frank Nielsen  El-Ghazali Talbi

# k-medoids and p-median clustering are solvable in polynomial time for a 2d
Pareto front

Nicolas Dupin  Frank Nielsen  El-Ghazali Talbi
<EMAIL_ADDRESS>Nicolas Dupin  Frank Nielsen  El-Ghazali Talbi

###### Abstract

This paper examines a common extension of k-medoids and k-median clustering in
the case of a two-dimensional Pareto front, as generated by bi-objective
optimization approaches. A characterization of optimal clusters is provided,
which allows to solve the optimization problems to optimality in polynomial
time using a common dynamic programming algorithm. More precisely, having $N$
points to cluster in $K$ subsets, the complexity of the algorithm is proven in
$O(N^{3})$ time and $O(K.N)$ memory space when $K\geqslant 3$, cases $K=2$
having a time complexity in $O(N^{2})$. Furthermore, speeding-up the dynamic
programming algorithm is possible avoiding useless computations, for a
practical speed-up without improving the complexity. Parallelization issues
are also discussed, to speed-up the algorithm in practice.

###### Keywords:

Bi-objective optimization clustering algorithms k-medoids p-median Euclidean
sum-of-squares clustering Pareto Front Dynamic programming Complexity

††journal: Preprint

##  1 Introduction

This paper is motivated by real-life applications of Multi-Objective
Optimization (MOO). Some optimization problems can be driven by more than one
objective function, with some conflicts among objectives. For example, one may
minimize financial costs, while maximizing the robustness to uncertainties
dupin2015modelisation ; peugeot2017mbse . In such cases, higher levels of
robustness are likely to induce financial over-costs. Pareto dominance,
preferring a solution from another if it is better for all the objectives, is
a weak dominance rule. With conflicting objectives, several non-dominated
solutions can be generated, these _efficient_ solutions are the best
compromises. A _Pareto front_ (PF) is the projection in the objective space of
the non-dominated solutions ehrgott2003multiobjective .

MOO approaches may generate large PF, for a trade-off evaluation by a decision
maker. The problem is here to select $K$ good compromise solutions from $N\gg
K$ non dominated solutions while maximizing the representativity of these $K$
solutions. This problem can be seen as an application of clustering
algorithms, partitioning the $N$ elements into $K$ subsets with a minimal
diversity, and giving a representative element of the optimal clusters.
Selecting best compromise solutions for human decision makers, one deals with
small values $K<10$. We note that partial PF are used inside population meta-
heuristics talbi2009metaheuristics . Clustering a PF is also useful in this
context to archive representative solutions of the partial PF
zio2011clustering . For such applications, the values of $K$ are larger than
the previous ones.

k-means clustering is one of the most famous unsupervised learning problem,
and is widely studied in the literature since the seminal algorithm provided
by Lloyd in lloyd1982least . The k-medoids problem, the discrete variant of
the k-means problem, fits better with our application to maximize the
dissimilarity around a representative solution kaufman1987clustering . If
k-medoids clustering is more combinatorial than k-means clustering, it is
known to be more robust on noises and outliers jain2010data . Both k-medoids
and k-means problem are NP hard in the general and the planar case
aloise2009np ; hsu1979easy . Lloyd’s algorithm can be extended to solve
heuristically k-medoids problems. PAM (Partitioning Around Medoids), CLARA
(Clustering LARge Applications) and CLARANS (Clustering Large Applications
based upon RANdomized Search) are such heuristics for k-medoids clustering
schubert2018faster . Hybrid and genetic algorithms were also investigated in
sheng2006genetic . Previous heuristics converge only to local minima, without
any guarantee to reach a global minimum. This paper proves that the special
case of k-medoids clustering in a two dimensional (2-d) PF is solvable in
polynomial time, thanks to a Dynamic Programming (DP) algorithm. Actually, the
result is obtained for a common extension of k-medoids and k-median problems,
with common issues to speed up the DP algorithm in practice. Having $N$ points
to cluster in $K$ subsets, the complexity of the algorithm is proven in
$O(N^{3})$ time and $O(KN)$ memory space when $K\geqslant 3$, cases $K=2$
having a time complexity in $O(N^{2})$. We note that the preliminary work
dupin2019medoids  stated a complexity in $O(N^{3})$ time and $O(N^{2})$ memory
space for the k-medoid problem.

In section 2, we define formally the problem and unify the notation. In
section 3, intermediate results and a characterization of optimal clusters are
presented. In section 4, it is described how to compute efficiently the costs
of the previous clusters. In section 5, a first DP algorithm is presented with
a proven polynomial complexity. In section 6, it is discussed how to speed up
the DP algorithm in practice, without improving the previous complexity. In
section 7, numerical and computational experiments are presented. In section
8, our contributions are summarized, discussing also future directions of
research.

$x$$y$$O=(x_{O},y_{O})$$\bullet$$B=(x_{B},y_{B})$ with$x_{O}<x_{B}$ and
$y_{O}<y_{B}$ $O$ dominates $B$$C=(x_{C},y_{C})$ with$x_{O}>x_{C}$ and
$y_{O}>y_{C}$ $C$ dominates $O$$D=(x_{D},y_{D})$ with$x_{O}<x_{D}$ and
$y_{D}<y_{O}$ $O$ and $D$ not comparable$A=(x_{A},y_{A})$ with$x_{O}>x_{A}$
and $y_{O}<y_{A}$ $A$ and $O$ not comparable Figure 1: Illustration of Pareto
dominance and incomparability quarters minimizing two objectives indexed by
$x$ and $y$: zones of $A$ and $D$ are incomparability zones related to $O$

##  2 Problem statement and notation

We consider a set $E=\\{x_{1},\dots,x_{N}\\}$ of $N$ elements of
${\mathbb{R}}^{2}$, such that for all $i\neq j$,
$x_{i}\phantom{0}\mathcal{I}\phantom{0}x_{j}$ defining the binary relations
$\mathcal{I},\prec$ for all
$y=(y^{1},y^{2}),z=(z^{1},z^{2})\in{\mathbb{R}}^{2}$ with:

$\displaystyle y\prec z$ $\displaystyle\Longleftrightarrow$ $\displaystyle
y^{1}<z^{1}\phantom{2}\mbox{and}\phantom{2}y^{2}>z^{2}$ (1) $\displaystyle
y\preccurlyeq z$ $\displaystyle\Longleftrightarrow$ $\displaystyle y\prec
z\phantom{2}\mbox{or}\phantom{2}y=z$ (2) $\displaystyle
y\phantom{1}\mathcal{I}\phantom{1}z$ $\displaystyle\Longleftrightarrow$
$\displaystyle y\prec z\phantom{2}\mbox{or}\phantom{2}z\prec y$ (3)

These hypotheses on $E$ characterizes 2-d discrete PF minimizing two
objectives, as illustrated in Figure 1. We note that the convention leading to
the definitions of $\mathcal{I},\prec$ considered the minimization of two
objectives. This is not a loss of generality, any bi-objective optimization
problem can be transformed into a minimization of two objectives. Such a set
$E$ can be extracted from any subset of ${\mathbb{R}}^{2}$ using an output-
sensitive algorithm nielsen1996output , or generated by bi-objective
optimization approaches, exact methods ehrgott2003multiobjective  and also
meta-heuristics talbi2009metaheuristics .

We consider in this paper the Euclidian distance :

$d(y,z)=|\\!|y-z|\\!|=\sqrt{\left(y^{1}-z^{1}\right)^{2}+\left(y^{2}-z^{2}\right)^{2}},\hskip
2.84544pt\forall y=(y^{1},y^{2}),(z^{1},z^{2})\in{\mathbb{R}}^{2}$ (4)

Let $K\in{\mathbb{N}}^{*}$ a strictly positive integer. $\Pi_{K}(E)$ denotes
the set of the possible partitions of $E$ in $K$ subsets:

$\Pi_{K}(E)=\left\\{P\subset{\mathcal{P}}(E)\>\bigg{|}\>\forall
p,p^{\prime}\in P,\>\>p\cap p^{\prime}=\emptyset\>,\>\bigcup_{p\in
P}p=E\>\mbox{and}\;|P|=K\>\right\\}$ (5)

Defining a cost function $f$ for each subset of $E$ to measure the
dissimilarity, we investigate $K$-clustering problems which can be written as
following combinatorial optimization problems, minimizing the sum of the
measure $f$ for all the $K$ clusters partitioning $E$:

$\min_{\pi\in\Pi_{K}(E)}\sum_{P\in\pi}f(P)$ (6)

_K-medoids_ and _K-median_ problems are in the shape of (6). On one hand,
discrete _K-median_ cost function $f_{med}(P)$ considers the minimal sum of
the distances from one chosen point of $P$, denoted as the _median_ , to the
other points of $P$. On the other hand, _K-medoids_ cost function $f_{mdd}(P)$
considers the minimal sum of the squared distances from one chosen point of
$P$, denoted as the _medoid_ , to the other points of $P$:

$\forall P\subset E,\;\;\;f_{med}(P)=\min_{y\in P}\sum_{x\in
P}\left|\\!\left|x-y\right|\\!\right|$ (7) $\forall P\subset
E,\;\;\;f_{mdd}(P)=\min_{c\in P}\sum_{x\in
P}\left|\\!\left|x-c\right|\\!\right|^{2}$ (8)

We unify notations with $\alpha>0$, considering the generic dissimilarity
function $f_{\alpha}(P)$:

$\forall P\subset E,\;\;\;f_{\alpha}(P)=\min_{y\in P}\sum_{x\in
P}\left|\\!\left|x-y\right|\\!\right|^{\alpha}$ (9)

######  Definition 1 ($\alpha$-medoids)

For all $\alpha>0$, the $\alpha$-medoid of a subset $P\subset E$ denotes the
point $p\in P$ such that $p=\mbox{argmin}_{y\in P}\sum_{x\in
P}\left|\\!\left|x-y\right|\\!\right|^{\alpha}$

######  Definition 2 ($K$-$\alpha$-Med2dPF )

For all $\alpha>0$, the $K$-clustering problem (6) using generic function
$f_{\alpha}(P)$ is denoted $K$-$\alpha$-Med2dPF.

With $\alpha=1$, the $\alpha$-medoids are the medians and $K$-$\alpha$-Med2dPF
corresponds to the discrete $K$-median clustering problem in a 2d PF. With
$\alpha=2$, the $\alpha$-medoids are the canonical medoids and
$K$-$\alpha$-Med2dPF corresponds to the $K$-medoids clustering problem in a 2d
PF. Furthermore, Lloyd’s algorithm for k-means clustering (lloyd1982least )
can be extended to solve heuristically $K$-$\alpha$-Med2dPF problems, the case
$K=2$ is the PAM (Partitioning Around Medoids) algorithm for k-medoids
schubert2018faster . We consider such neighborhood structure to define local
minimums, the local minimums are thus characterized as following:

######  Definition 3 (Local minimums of $K$-$\alpha$-Med2dPF)

For all $\alpha>0$ and $K\in{\mathbb{N}}^{*}$, local minimums of
$K$-$\alpha$-Med2dPF are characterized by the encoding of partitioning subsets
$P_{1},\dots,P_{K}$ and their respective $\alpha$-medoids $c_{1},\dots,c_{K}$,
with the property:

$\forall k\in[\\![1;K]\\!],\forall p\in P_{k},\forall k^{\prime}\neq
k,d(p,c_{k})\leqslant d(p,c_{k^{\prime}})$ (10)

##  3 State-of-the-art

This section describes related works to appreciate our contributions, in the
state of the art of the k-median and k-medoid problems.

###  3.1 The general p-median problem

The p-median problem was originally a logistic problem, having a set of
customers and defining the places of depots in order to minimize the total
distance for customers to reach the closest depot. We give here the general
form of the p-median problem. Let $N$ be the number of clients, called
$c_{1},c_{2},\dots,c_{N}$ , let $M$ be the number of potential sites or
facilities, called $f_{1},f_{2},\dots,f_{M}$ , and let $d_{i,j}$ be the
distance from $c_{i}$ to $f_{j}$. The p-median problem consists of opening $p$
facilities and assigning each client to its closest open facility, in order to
minimize the total distance. We note that in some version of the general
p-median problem, the graph of the possible assignments is not complete.
Considering complete grahs of distances is not a loss of generality, modeling
with $d_{i,j}=+\infty$ the edges which do not exist in the original graph.

The p-median problem is naturally formulated within the Integer Linear
Programming (ILP) framework. A first ILP formulation defines binary variables
$x_{i,j}\in\\{0,1\\}$ and $y_{j}\in\\{0,1\\}$. $x_{i,j}=1$ if and only if the
customer $i$ is assigned to the depot $j$. $y_{j}=1$ if and only if the point
$f_{j}$ is chosen as a depot. Following ILP formulation expresses the p-median
problem:

$\begin{array}[]{lll}\min_{x,y}&\displaystyle\sum_{j=1}^{n}\sum_{i=1}^{n}d_{i,j}x_{i,j}\\\
s.t:&\sum_{j=1}^{n}y_{j}=p\\\ &\sum_{j=1}^{n}x_{i,j}=1,&\forall
i\in[\\![1,n]\\!]\\\ &x_{i,j}\leqslant
y_{j},&\forall(i,j)\in[\\![1,n]\\!]^{2},\\\
\forall{i,j},&x_{i,j},y_{j}\in\\{0,1\\}\end{array}$ (11)

The p-median problem was proven NP-hard in the general case
kariv1979algorithmic . The p-median problem in ${\mathbb{R}}^{2}$ with an
Euclidian distance is also NP-hard megiddo1984complexity . In a tree
structure, the p-median problem is solvable in polynomial time, with a DP
algorithm running in $O(pn^{2})$ time tamir1998polynomial . One dimensional
(1d) cases of p-median are special cases of p-median with a tree structure, an
improved DP algorithm was proposed with a time complexity in $O(pn)$
hassin1991improved .

The p-median problem can be solved to optimality using ILP techniques. The
formulation (11) is tightened in elloumi2010tighter  for a more efficient
resolution with a Branch & Bound (B& B) solver. For larger sizes of instances,
Lagrangian relaxations were investigated in beltran2006solving ;
santos2009solving  or with column-and-row generation as in
avella2007computational . Heuristic algorithms are also widely studied
mladenovic2007p .

###  3.2 From p-median to $K$-$\alpha$-Med2dPF clustering problems

In our application, the graph is complete, the points
$f_{1},f_{2},\dots,f_{M}$ are exactly $c_{1},c_{2},\dots,c_{N}$ and
$d_{i,j}\\{1/\alpha\\}$ is the Euclidian distance in ${\mathbb{R}}^{2}$. The
k-medoid problem is the case $\alpha=2$, whereas the k-median problem is the
case $k=1$. Both cases are well known clustering problems.
$K$-$\alpha$-Med2dPF is not only an extension for k-median and k-medoids, the
value $\alpha>0$ is a parameter of interest, varying $\alpha$ leads to
different clustering solutions, as in fomin2019parameterized .

To the best of our knowledge, no specific studies concerned p-median or
k-medoids problems in a PF before the preliminary work dupin2019medoids . A
complexity in $O(N^{3})$ time and $O(N^{2})$ memory space for k-medoids
problems was proven in dupin2019medoids . We note that an affine 2d PF is a
line in ${\mathbb{R}}^{2}$, such case is equivalent to the 1d case. Hence,
k-medoids and k-median problems are solvable in $O(kn)$ time in an affine 2d
PF thanks to hassin1991improved .

General planar cases of p-median and k-medoid problems can also be seen as
specific cases of three-dimensional (3d) PF: affine 3d PF. Having a NP-hard
complexity proven for the planar cases of p-median problems, it implies that
the corresponding p-median problems are also NP-hard for 3d PF thanks to
megiddo1984complexity .

###  3.3 Clustering/selecting points in Pareto frontiers

We summarize here results related to the selection or the clustering of points
in PF, with applications to MOO algorithms. Maximizing the quality of discrete
representations of Pareto sets was studied with the hypervolume measure in the
Hypervolume Subset Selection (HSS) problem auger2009investigating ;
sayin2000measuring . The HSS problem, maximizing the representativity of $k$
solutions among a PF of size $n$ initial ones, is known to be NP-hard in
dimension 3 (and greater dimensions) since bringmann2018maximum . An exact
algorithm in $n^{O(\sqrt{k})}$ and a polynomial-time approximation scheme for
any constant dimension $d$ are also provided in bringmann2018maximum . The 2d
case is solvable in polynomial time thanks to a DP algorithm with a complexity
in $O(kn^{2})$ time and $O(kn)$ space provided in auger2009investigating . The
time complexity of the DP algorithm was improved in $O(kn+n\log n)$ by
bringmann2014two  and in $O(k(n-k)+n\log n)$ by kuhn2016hypervolume .

Selecting points in a 2d PF, maximizing the diversity, can be formulated also
using p-dispersion problems. Max-Min and Max-Sum p-dispersion problems are NP-
hard problemserkut1990discrete ; hansen1995dispersing . Max-Min and Max-Sum
p-dispersion problems are still NP-hard problems when distances fulfill the
triangle inequality erkut1990discrete ; hansen1995dispersing . The planar (2d)
Max-Min p-dispersion problem is also NP-hard wang1988study . The one-
dimensional (1d) cases of Max-Min and Max-Sum p-dispersion problems are
solvable in polynomial time, with a similar DP algorithm running in
$O(\max\\{pn,n\log n\\})$ time ravi1994heuristic ; wang1988study . Max-Min
p-dispersion was proven to be solvable in polynomial time, with a DP algorithm
running in $O(pn\log n)$ time and $O(n)$ space dupin2020polynomial . Other
variants of p-dispersion problems are also proven to be solvable in polynomial
time, using also DP algorithms dupin2020polynomial .

Some similar results exist also for k-means clustering. K-means is NP-hard for
2d cases, and thus for 3d PF mahajan2012planar . The 1d case of k-means is
also solvable by a DP algorithm, with a complexity in $O(kn)$ using memory
space in $O(n)$ gronlund2017fast . The restriction to 2d PF would be also
solvable in $O(n^{3})$ time with a DP algorithm if a conjecture is proven
dupin2018dynamic .

Lastly, p-center problems present also similar results. The discrete and
continuous p-center problems are NP-hard in general. The discrete p-center
problem in ${\mathbb{R}}^{2}$ with a Euclidian distance is also NP-hard
megiddo1984complexity , it implies also that the specific case of 3f PF are
also NP hard using discrete p-center culstering. The 1d case of continuous
p-center is solvable in $O(pn\log n)$ time and $O(n)$ space megiddo1983new ,
whereas the 2d PF cases are solvable in $O(pn\log n)$ time and $O(n)$ space
dupin2019planar . The discrete p-center problem in a 2d PF is solvable
$O(pn\log^{2}n)$ time and $O(n)$ space dupin2019planar .

$\emph{Obj}_{1}$$\emph{Obj}_{2}$$x_{1}$$\bullet$$x_{2}$$\bullet$$x_{3}$$\bullet$$x_{4}$$\bullet$$x_{5}$$\bullet$$x_{6}$$\bullet$$x_{7}$$\bullet$$x_{8}$$\bullet$$x_{9}$$\bullet$$x_{10}$$\bullet$$x_{11}$$\bullet$$x_{12}$$\bullet$$x_{13}$$\bullet$$x_{14}$$\bullet$$x_{15}$$\bullet$
Figure 2: Illustration of a 2-dimensional PF with 15 points, minimizing two
objectives and indexing the points with the Lemma 2

##  4 Intermediate results

###  4.1 Local optimality and interval clustering

In this section, local minimums for $K$-$\alpha$-Med2dPF clustering problems
are proven to fulfill an interval clustering property. These results extend
the previous ones, concerning only the global optimum of k-medoids problems in
a 2d PF dupin2019medoids .

###### Lemma 1

$\preccurlyeq$ is an order relation, and $\prec$ is a transitive relation:

$\forall x,y,z\in{\mathbb{R}}^{2},\phantom{3}x\prec
y\phantom{1}\mbox{and}\phantom{1}y\prec z\Longrightarrow x\prec z$ (12)

Proof: This is a trivial consequence of the transitivity of $\leqslant$ and
$<$ in ${\mathbb{R}}$:

######  Lemma 2 (Total order)

Points $(x_{i})$ can be indexed such that:

$\displaystyle\forall(i_{1},i_{2})\in[\\![1;N]\\!]^{2},$ $\displaystyle
i_{1}<i_{2}\Longrightarrow$ $\displaystyle x_{i_{1}}\prec x_{i_{2}}$ (13)
$\displaystyle\forall(i_{1},i_{2})\in[\\![1;N]\\!]^{2},$ $\displaystyle
i_{1}\leqslant i_{2}\Longrightarrow$ $\displaystyle x_{i_{1}}\preccurlyeq
x_{i_{2}}$ (14)

This property is stronger than the property that $\preccurlyeq$ induces a
total order in $E$. Furthermore, the complexity of the sorting re-indexation
is in $O(N.\log N)$

Proof: We reindex $E$ such that the first coordinate is increasing:

$\forall(i_{1},i_{2})\in[\\![1;N]\\!]^{2},i_{1}<i_{2}\Longrightarrow
x_{i_{1}}^{1}<x_{i_{2}}^{1}$

This sorting procedure has a complexity in $O(N.\log N)$. Let
$(i_{1},i_{2})\in[\\![1;N]\\!]^{2}$, with $i_{1}<i_{2}$. We have thus
$x_{i_{1}}^{1}<x_{i_{2}}^{1}$. Having $x_{i_{1}}\mathcal{I}x_{i_{2}}$ implies
$x_{i_{1}}^{2}>x_{i_{2}}^{2}$. $x_{i_{1}}^{1}<x_{i_{2}}^{1}$ and
$x_{i_{1}}^{2}>x_{i_{2}}^{2}$ is by definition $x_{i_{1}}\prec x_{i_{2}}$.
$\square$

###### Lemma 3

We suppose that points $(x_{i})$ are sorted following Proposition 2.

$\displaystyle\forall(i_{1},i_{2},i_{3})\in[\\![1;N]\\!]^{3},$ $\displaystyle
i_{1}\leqslant i_{2}<i_{3}\Longrightarrow
d(x_{i_{1}},x_{i_{2}})<d(x_{i_{1}},x_{i_{3}})$ (15)
$\displaystyle\forall(i_{1},i_{2},i_{3})\in[\\![1;N]\\!]^{3},$ $\displaystyle
i_{1}<i_{2}\leqslant i_{3}\Longrightarrow
d(x_{i_{2}},x_{i_{3}})<d(x_{i_{1}},x_{i_{3}})$ (16)

Proof: We note firstly that the equality cases are trivial, so that we can
suppose $i_{1}<i_{2}<i_{3}$ in the following proof. We prove here (15), the
proof of (16) is analogous.
Let $i_{1}<i_{2}<i_{3}$. We note $x_{i_{1}}=(x^{1}_{i_{1}},x^{2}_{i_{1}})$,
$x_{i_{2}}=(x^{1}_{i_{2}},x^{2}_{i_{2}})$ and
$x_{i_{3}}=(x^{1}_{i_{3}},x^{2}_{i_{3}})$ .
Proposition 2 ordering ensures $x^{1}_{i_{1}}<x^{1}_{i_{2}}<x^{1}_{i_{3}}$ and
$x^{2}_{i_{1}}>x^{2}_{i_{2}}>x^{2}_{i_{3}}$.
$d(x_{i_{1}},x_{i_{2}})^{2}={(x^{1}_{i_{1}}-x^{1}_{i_{2}})^{2}+(x^{2}_{i_{1}}-x^{2}_{i_{2}})^{2}}$
With $x^{1}_{i_{3}}-x^{1}_{i_{1}}>x^{1}_{i_{2}}-x^{1}_{i_{1}}>0$,
$(x^{1}_{i_{1}}-x^{1}_{i_{2}})^{2}<(x^{1}_{i_{1}}-x^{1}_{i_{3}})^{2}$
With $x^{2}_{i_{3}}-x^{2}_{i_{1}}<x^{2}_{i_{2}}-x^{2}_{i_{1}}<0$,
$(x^{2}_{i_{1}}-x^{2}_{i_{2}})^{2}<(x^{2}_{i_{1}}-x^{2}_{i_{3}})^{2}$
Thus
$d(x_{i_{1}},x_{i_{2}})^{2}<{(x^{1}_{i_{1}}-x^{1}_{i_{3}})^{2}+(x^{2}_{i_{1}}-x^{2}_{i_{3}})^{2}}=d(x_{i_{1}},x_{i_{3}})^{2}$.
$\square$

###### Proposition 1

[Interval clustering and local minimums of $2$-$\alpha$-Med2dPF]We suppose
that points $(x_{i})$ are sorted following Lemma 2. For all $\alpha>0$, local
minimums of $2$-$\alpha$-Med2dPF encoded with $P_{1},P_{2},c_{1},c_{2}$ are
necessarily on the shape $P_{1}=\\{x_{j}\\}_{j\in[\\![1,i]\\!]}$,
$P_{2}=\\{x_{j}\\}_{j\in[\\![i+1,N]\\!]}$, far a given $i\in[\\![1,N-1]\\!]$.
Hence, there is at most $N-1$ local minimums for $2$-$\alpha$-Med2dPF
problems.

Proof : Let $P_{1},P_{2},c_{1},c_{2}$ encoding a local minimum of
$2$-$\alpha$-Med2dPF, indexed such that $c_{1}\prec c_{2}$ (thanks the total
order of Lemma 2). Let $i=\max\\{j\in[\\![1,N]\\!],\>x_{j}\in P_{1}\\}$.
Having $c_{1}\prec c_{2}\preccurlyeq x_{N}$, Lemma 3 implies that
$d(x_{N},c_{2})\leqslant d(x_{N},c_{1})$ and (10) implies that $x_{N}\in
P_{2}$ and $i<N$. By definition of $i$, $x_{i+1}\in P_{2}$ and $i+1$ is the
minimal index of points of $P_{2}$, and we have $x_{i+1}\prec c_{2}$. In terms
of distances with equation (10), $d(x_{i},c_{1})\leqslant d(x_{i},c_{2})$ and
$d(x_{i+1},c_{2})<d(x_{i+1},c_{1})$. We prove now that for all
$i^{\prime}>i+1$, $d(i^{\prime},c_{2})<d(i^{\prime},c_{1})$. We prove by
contradiction that $c_{1}\preccurlyeq x_{i}$, supposing $x_{i}\prec c_{1}$. We
would have thus $x_{i+1}\preccurlyeq c_{1}\prec c_{2}$ and lemma 3 implies
$d(x_{i+1},c_{1})<d(x_{i+1},c_{2})$ which is in contradiction with (10). Let
$i^{\prime}>i+1$. Having $c_{1}\prec x_{i+1}\preccurlyeq c_{2}$, the total
order implies $c_{1}\prec x_{i+1}\preccurlyeq c_{2}\preccurlyeq
x_{i^{\prime}}$ or $c_{1}\prec x_{i+1}\preccurlyeq x_{i^{\prime}}\prec c_{2}$.
In the first case, $d(x_{i^{\prime}},c_{2})<d(x_{i^{\prime}},c_{1})$ is
implied by lemma 3. in the second case, $d(x_{i^{\prime}},c_{2})\leqslant
d(x_{i+1},c_{2})$ and $d(x_{i^{\prime}},c_{1})\geqslant d(x_{i+1},c_{1})$
using lemma 3. Hence, using $d(x_{i+1},c_{2})<d(x_{i+1},c_{1})$, we have thus
$d(x_{i^{\prime}},c_{2})\leqslant d(x_{i+1},c_{2})<d(x_{i+1},c_{1})\leqslant
d(x_{i^{\prime}},c_{1})$ i.e.
$d(x_{i^{\prime}},c_{2})<d(x_{i^{\prime}},c_{1})$. This proves that
$P_{2}=\\{x_{j}\\}_{j\in[\\![i+1,N]\\!]}$, and thus
$P_{1}=\\{x_{j}\\}_{j\in[\\![1,i]\\!]}$. $\square$

######  Proposition 2 (Optimal interval clustering)

We suppose that points $(x_{i})$ are sorted following Lemma 2. Each local
minimum of the $K$-$\alpha$-Med2dPF problems is only composed of clusters
${\mathcal{C}}_{i,i^{\prime}}=\\{x_{j}\\}_{j\in[\\![i,i^{\prime}]\\!]}=\\{x\in
E\>|\>\exists j\in[\\![i,i^{\prime}]\\!],\>x=x_{j}\\}$. As a consequence,
there is at most ${N}\choose{k}$ local optima for $K$-$\alpha$-Med2dPF
problems in a 2d PF of size $N$.

Proof: We prove the result by contradiction on $K\in{\mathbb{N}}$. We suppose
having a local minimum for $K$-$\alpha$-Med2dPF in $E$, encoded
$P_{1},\dots,P_{K}$ and their respective $\alpha$-medoids $c_{1},\dots,c_{K}$,
which does not fulfill Proposition 2. There exist a cluster $k$ such that
$P_{k}$ is not on the shape ${\mathcal{C}}_{i,i^{\prime}}$. Denoting
$i,i^{\prime}$ the minimal and maximal indexes of points of $P_{k}$, it exists
an index $j\in[\\![i,i^{\prime}]\\!]$ with $x_{j}\in P_{k^{\prime}}\neq
P_{k}$. Restricting relations (10), $P_{k},P_{k^{\prime}}$ must define a local
minimum of $2$-$\alpha$-Med2dPF among points $E^{\prime}=P_{k}\cup
P_{k^{\prime}}$. $P_{k},P_{k^{\prime}}$ being nested, this is in contradiction
with Proposition 1. $\square$

Remark: a similar property was proven for the global optima of continuous and
discrete K-center clustering problems in a 2d PF dupin2019planar , which is
the key ingredient to derive a polynomial DP algorithm. However, a main
difference exist in the optimality conditions: global optimal solution of
K-center may exist with nested clusters, the optimality condition is not
necessary for K-center problems.

###  4.2 Costs of interval clusters

With Proposition 2, the computation of cluster costs
$f_{\alpha}({\mathcal{C}}_{i,i^{\prime}})$ and the $\alpha$-medoids of
interval clusters ${\mathcal{C}}_{i,i^{\prime}}$ are of special interest. We
analyze here properties of these clusters to compute the costs efficiently
thereafter.

###### Lemma 4

Let $P\subset P^{\prime}\subset E$.We have $f_{\alpha}(P)\leqslant
f_{\alpha}(P^{\prime})$.
Especially, for all $i<i^{\prime}$,
$f_{\alpha}({\mathcal{C}}_{i,i^{\prime}})\leqslant
f_{\alpha}({\mathcal{C}}_{i,i^{\prime}+1})$ and
$f_{\alpha}({\mathcal{C}}_{i+1,i^{\prime}})\leqslant
f_{\alpha}({\mathcal{C}}_{i,i^{\prime}})$.

Proof: Let $P\subset P^{\prime}\subset E$, and let $i$ (resp $i^{\prime}$)
index defining the $\alpha$-medoids of $P$ (resp $P^{\prime}$. Using
$\sum_{x\in P}\left|\\!\left|x-x_{i}\right|\\!\right|^{\alpha}=\min_{y\in
P}\left|\\!\left|x-x_{i}\right|\\!\right|^{\alpha}$ and the positivity of
distances, we have:

$\displaystyle f_{\alpha}(P)$ $\displaystyle=$ $\displaystyle\sum_{x\in
P}\left|\\!\left|x-x_{i}\right|\\!\right|^{\alpha}$ $\displaystyle
f_{\alpha}(P)$ $\displaystyle\leqslant$ $\displaystyle\sum_{x\in
P}\left|\\!\left|x-x_{i^{\prime}}\right|\\!\right|^{\alpha}$ $\displaystyle
f_{\alpha}(P)$ $\displaystyle\leqslant$ $\displaystyle\sum_{x\in
P}\left|\\!\left|x-x_{i^{\prime}}\right|\\!\right|+\sum_{x\in
P^{\prime}\setminus
P}\left|\\!\left|x-x_{i^{\prime}}\right|\\!\right|^{\alpha}=f_{\alpha}(P^{\prime})$

For all $i<i^{\prime}$, applying the previous result with
$P={\mathcal{C}}_{i,i^{\prime}}$ and $P={\mathcal{C}}_{i,i^{\prime}+1}$, we
have $f_{\alpha}({\mathcal{C}}_{i,i^{\prime}})\leqslant
f_{\alpha}({\mathcal{C}}_{i,i^{\prime}+1})$, and with
$P={\mathcal{C}}_{i+1,i^{\prime}}$ and $P={\mathcal{C}}_{i,i^{\prime}}$
$f_{\alpha}({\mathcal{C}}_{i+1,i^{\prime}})\leqslant
f_{\alpha}({\mathcal{C}}_{i,i^{\prime}})$. $\hfill\square$

We define $c_{i,i^{\prime}}$ as the cost of cluster
${\mathcal{C}}_{i,i^{\prime}}$ for the $K$-$\alpha$-Med2dPF clustering. This
section aims to compute efficiently the costs $c_{i,i^{\prime}}$ for all
$i<i^{\prime}$. By definition:

$\forall
i<i^{\prime},\;\;\;c_{i,i^{\prime}}=f_{\alpha}({\mathcal{C}}_{i,i^{\prime}})=\min_{j\in[\\![i,i^{\prime}]\\!]}\sum_{k\in[\\![i,i^{\prime}]\\!]}\left|\\!\left|x_{j}-x_{k}\right|\\!\right|^{\alpha}$
(17)

We define for all $i\leqslant c\leqslant i^{\prime}$, elements
$d_{i,c,i^{\prime}}^{\alpha}$ giving the $\alpha$-Med2dPF of cluster
${\mathcal{C}}_{i,i^{\prime}}$ with $c$ chosen as the $\alpha$-medoid:

$\displaystyle\forall i\leqslant c\leqslant i^{\prime},\;\;\;$ $\displaystyle
d_{i,c,i^{\prime}}$
$\displaystyle=\sum_{k=i}^{i^{\prime}}\left|\\!\left|x_{k}-x_{c}\right|\\!\right|^{\alpha}$
(18) $\displaystyle\forall i\leqslant i^{\prime},\;\;\;$ $\displaystyle
c_{i,i^{\prime}}$
$\displaystyle=\min_{l\in[\\![i,i^{\prime}]\\!]}d_{i,l,i^{\prime}}$ (19)

###### Lemma 5

Let $i,i^{\prime}$, such that $i+1<i^{\prime}$. We have
$d_{i,i,i^{\prime}}>d_{i,i+1,i^{\prime}}$ and
$d_{i,i^{\prime},i^{\prime}}>d_{i,i^{\prime}-1,i^{\prime}}$. It implies:

$c_{i,i^{\prime}}=\min_{l\in[\\![i+1,i^{\prime}-1]\\!]}d_{i,l,i^{\prime}}$
(20)

Proof: By definition,
$d_{i,i,i^{\prime}}=\sum_{j=i}^{i^{\prime}}\left|\\!\left|x_{j}-x_{i}\right|\\!\right|^{\alpha}$
and
$d_{i,i+1,i^{\prime}}=\sum_{j=i}^{i^{\prime}}\left|\\!\left|x_{j}-x_{i+1}\right|\\!\right|^{\alpha}$.
Hence,
$d_{i,i,i^{\prime}}-d_{i,i+1,i^{\prime}}=\sum_{j=i+2}^{i^{\prime}}\left(\left|\\!\left|x_{j}-x_{i}\right|\\!\right|^{\alpha}-\left|\\!\left|x_{j}-x_{i+1}\right|\\!\right|^{\alpha}\right)$.
With Lemma 3, for all $j>i+1$,
$\left|\\!\left|x_{j}-x_{i}\right|\\!\right|^{\alpha}-\left|\\!\left|x_{j}-x_{i+1}\right|\\!\right|^{\alpha}>0$,
which implies $d_{i,i,i^{\prime}}-d_{i,i+1,i^{\prime}}>0$. The proof of
$d_{i,i^{\prime},i^{\prime}}>d_{i,i^{\prime}-1,i^{\prime}}$ is analogous,
which implies also (20). $\square$

###### Lemma 6

Let $i,i^{\prime}$, such that $i+1<i^{\prime}$. Let $c\geqslant i+1$ an index
of an $\alpha$-medoid of ${\mathcal{C}}_{i,i^{\prime}}$, ie
$d_{i,c,i^{\prime}}=\min_{l\in[\\![i+1,i^{\prime}-1]\\!]}d_{i,l,i^{\prime}}$.
If $i^{\prime}<N$, there exist $c^{\prime}$ an $\alpha$-medoid of
${\mathcal{C}}_{i,i^{\prime}+1}$, such that $c\leqslant c^{\prime}\leqslant
i^{\prime}$, i.e.
$c_{i,i^{\prime}+1}=\min_{l\in[\\![c,i^{\prime}-1]\\!]}d_{i,l,i^{\prime}}$.
If $i>1$, there exist $c^{\prime\prime}$ an $\alpha$-medoid of
${\mathcal{C}}_{i-1,i^{\prime}}$, such that $i\leqslant c^{\prime}\leqslant
c$, i.e. $c_{i-1,i^{\prime}}=\min_{l\in[\\![i,c]\\!]}d_{i,l,i^{\prime}}$

Proof: We prove the first assertion, the last one is proven similarly. Let
$i,i^{\prime}$, such that $i+1<i^{\prime}<N$. Let $c\geqslant i+1$ an index of
an $\alpha$-medoid of ${\mathcal{C}}_{i,i^{\prime}}$.
Let $c^{\prime\prime}<c$. The optimality of $c$ impose
$\sum_{j=i}^{i^{\prime}}\left|\\!\left|x_{j}-x_{c}\right|\\!\right|^{\alpha}\leqslant\sum_{j=i}^{i^{\prime}}\left|\\!\left|x_{j}-x_{c^{\prime\prime}}\right|\\!\right|^{\alpha}$.
Then, Proposition 3 assures that
$\left|\\!\left|x_{i^{\prime}+1}-x_{c}\right|\\!\right|^{\alpha}<\left|\\!\left|x_{i^{\prime}+1}-x_{c^{\prime\prime}}\right|\\!\right|^{\alpha}$.
Hence,
$\sum_{j=i}^{i^{\prime}+1}\left|\\!\left|x_{j}-x_{c}\right|\\!\right|^{\alpha}<\sum_{j=i}^{i^{\prime}+1}\left|\\!\left|x_{j}-x_{c^{\prime\prime}}\right|\\!\right|^{\alpha}$.
In other words, any $c^{\prime\prime}<c$ is not optimal in the minimization
defining $f_{\alpha}({\mathcal{C}}_{i,i^{\prime}+1})$ and
$c_{i,i^{\prime}+1}=\min_{l\in[\\![c,i^{\prime}-1]\\!]}d_{i,l,i^{\prime}}$.
$\hfill\square$

###  4.3 The case $1$-$\alpha$-Med2dPF

For all $i<i^{\prime}$, the straightforward computation of $c_{i,i^{\prime}}$
has a time complexity in $O((i^{\prime}-i)^{2})$, and thus in $O(N^{2})$. In
this section, the case of convex or concave 2d PF are proven to be solvable in
$O(N\log N)$ time when $\alpha>0$.

Algorithm 1: Computation of $c_{i,i^{\prime}}^{2}$
---
`` input: indexes $i\leqslant i^{\prime}$
`` output: the medoid cost $c_{i,i^{\prime}}^{2}$ , the index of the center
`` if $i^{\prime}-i<2$ return
$\left|\\!\left|z_{i}-z_{i^{\prime}}\right|\\!\right|^{2}$, $i^{\prime}$
`` if $i^{\prime}-i=2$ return
$\left|\\!\left|z_{i+1}-z_{i^{\prime}}\right|\\!\right|^{2}+\left|\\!\left|z_{i}-z_{i+1}\right|\\!\right|^{2}$,
$i+1$
``
`` define $\mbox{idInf}=i+1$,
$\mbox{valInf}=\left|\\!\left|x_{i}-x_{i^{\prime}}\right|\\!\right|$,
`` define $\mbox{idSup}=i^{\prime}-1$,
$\mbox{valSup}=\left|\\!\left|x_{i}-x_{i^{\prime}}\right|\\!\right|$,
`` while $\mbox{idSup}-\mbox{idInf}\geqslant 2$
`` Compute $\mbox{idMid}=\left\lfloor\frac{i+i^{\prime}}{2}\right\rfloor$,
$\mbox{temp}=d_{i,\emph{idMid},i^{\prime}}$,
$\mbox{temp2}=d_{i,\emph{idMid}+1,i^{\prime}}$
`` if $\mbox{temp}=\mbox{temp2}$
``$\mbox{idInf}=\mbox{idMid},\mbox{valInf}=\mbox{temp}$
``$\mbox{idSup}=1+\mbox{idMid}$, $\mbox{valSup}=\mbox{temp2}$
`` if $\mbox{temp}<\mbox{temp2}$
``$\mbox{idSup}=\mbox{idMid},\mbox{valSup}=\mbox{temp}$
`` if $\mbox{temp}>\mbox{temp2}$
``$\mbox{idInf}=1+\mbox{idMid},\mbox{valInf}=\mbox{temp2}$
`` end while
if $\mbox{valInf}<\mbox{valSup}$ return valInf, idInf
else return valSup, idSup

###### Proposition 3

We suppose that points $(z_{i})$ are sorted following Lemma 2, and that the 2d
PF $E$ is convex (or concave): it exist a ${\mathcal{C}}^{2}$, decreasing and
convex (or concave) function $g$ such that
$E=\\{(x_{1},g(x_{1})),\dots,(x_{i},g(x_{i})),\dots,(x_{N},g(x_{N}))\\}$.
Then, computing $1$-$\alpha$-Med2dPF in $E$ has a complexity in $O(N\log N)$
time and $O(1)$ additional space, using Algorithm 1.

Proof: Firstly, we notice that concave cases are implied by the convex cases,
using the axial symmetry around the line $(z_{1},z_{n})$. Hence, we suppose
that $g$ is convex for the rest of the proof.
Let $\displaystyle
h(t)=\sum_{j=1}^{N}(t-x_{j})^{\alpha}+\sum_{j=1}^{N}(g(t)-g(x_{j}))^{\alpha}$.
h is strictly convex and for all $j\in[\\![1,N]\\!]$, $h(x_{j})=d_{1,j,n}$.
Furthermore, $h(x_{2})<h(x_{1})$ and $h(x_{n-1})<h(x_{N})$ using Lemma 5.
Hence, $h$ is strictly decreasing, reach a minimum and then is strictly
increasing. This monotony hold for the restrictions $h(x_{j})=d_{1,j,n}$.
Algorithm 1 proceeds by a dichotomic, a decreasing (resp increasing) phase
detected with $d_{1,j,n}>d_{1,j+1,n}$ (resp $d_{1,j,n}<d_{1,j+1,n}$ ) implies
that the optimum is greater (resp lower) than $j$. An equality
$d_{1,j,n}=d_{1,j+1,n}$ implies that $j$ and $j+1$ return the optimal value.
$\hfill\square$

Remark: An open question is to generalize hypothesis where the Algorithm 1 is
valid to compute optimally $1$-$\alpha$-Med2dPF. A counter example, with
$\alpha=1$ and a PF of size $5$ is given as following:
$z_{1}=(1,0)$, $z_{2}=(0.55,0.45)$, $z_{3}=(0.549,0.549)$,
$z_{4}=(0.45,0.45)$, $z_{5}=(0,01)$.
$d_{1,2,5}^{2}=d_{1,4,5}^{2}=0.45^{2}+0.55^{2}+0.1^{2}+0.99^{2}+0.001^{2}+0.1^{2}+0.45^{2}+0.55^{2}=1.02002$
$d_{1,3,5}^{2}=2\times(0.451^{2}+0.549^{2})+2\times(0.099^{2}+0.001^{2})=1.029208$
We have $d_{1,1,5}>d_{1,2,5}$, $d_{1,2,5}<d_{1,3,5}$, $d_{1,3,5}>d_{1,4,5}$
and $d_{1,4,5}<d_{1,5,5}$.

##  5 Computing efficiently the costs of interval clustering

Computing $c_{i,i^{\prime}}$ independently for all $i<i^{\prime}$ using
straightforward computations induces a complexity in $O(N^{4})$ time. In the
case of convex (or concave) 2d PF and $\alpha>1$, the time complexity is in
$O(N^{3}\log N)$. To improve the complexity, we notice that $d$ fulfills
following relations:

$\forall i\leqslant c\leqslant
i^{\prime}<N,\;\;\;d_{i,c,i^{\prime}+1}=d_{i,c,i^{\prime}}+\left|\\!\left|x_{i^{\prime}+1}-x_{c}\right|\\!\right|^{\alpha}$
(21)

In dupin2019medoids , relations (21) are used to compute the whole matrix of
cluster costs in $O(N^{4})$ time and $O(N^{2})$ space. Actually, the following
development will avoid to store the whole DP matrix, which induces a space
complexity in $O(N^{2})$. For the improved DP algorithm, we need two types of
computations in $O(N)$ space: computing the costs
$f_{\alpha}({\mathcal{C}}_{1,j})$ for all $j\in[\\![1;N]\\!]$, and computing
costs $f_{\alpha}({\mathcal{C}}_{j^{\prime},j})$ for a given
$j\in[\\![1;N]\\!]$ and for all $j\in[\\![1;j^{\prime}]\\!]$.

Algorithm 2: Computing $f_{\alpha}({\mathcal{C}}_{1,j})$ for all
$j\in[\\![1;N]\\!]$
---
Input: $j\in[\\![1;N]\\!]$, $\alpha>0$, $N$ points of ${\mathbb{R}}^{2}$,
$E=\\{x_{1},\dots,x_{N}\\}$
Optional input: $\overline{c}=N$ or $\overline{c}\in[\\![1;N]\\!]$, an upper
bound to an optimal center of cluster ${\mathcal{C}}_{1,N}$.
Output: for all $j\in[\\![1;N]\\!]$, $v_{j}=f_{\alpha}({\mathcal{C}}_{1,j})$
and $c_{j}$ a center of cluster ${\mathcal{C}}_{1,j}$
``
`` define vector $v$ with $v_{j}=0$ for all $j\in[\\![1;N]\\!]$
`` define vector $c$ with $c_{j}=1$ for all $j\in[\\![1;N]\\!]$
`` define vector $temp$ with $temp_{i}=0$ for all $i\in[\\![1;N]\\!]$
``
`` for $j=2$ to $N$
``for $k=c_{j-1}$ to $\min(j,\overline{c})$
`` $temp_{k}=temp_{k}+\left|\\!\left|x_{k}-x_{j}\right|\\!\right|^{\alpha}$
`` end for
`` Compute $v_{k}=\displaystyle\min_{k\in[\\![a,b]\\!]}temp_{k}$,
$c_{k}=\mbox{arg}\displaystyle\min_{k\in[\\![a,b]\\!]}temp_{k}$
`` where $a=c_{j-1}$ and $b=\min(j-1,\overline{c})$
`` end for
``
return vectors $v$ and $c$

###### Proposition 4

Algorithm 2 computes the cluster costs $f_{\alpha}({\mathcal{C}}_{1,j})$ for
all $j\in[\\![1;j]\\!]$ with a complexity in $O(N^{2})$ time and in $O(N)$
memory space.

Proof: To compute the costs $f_{\alpha}({\mathcal{C}}_{1,j})$ for all
$j\in[\\![1;N]\\!]$, Algorithm 2 constructs and store the costs with $j$
increasing, with a temporary vector containing the required values of
$d_{1,j^{\prime},j}$ at the step $j$, the step $j+1$ updating the values
$d_{1,j^{\prime},j+1}$ using $O(1)$ computations
$d_{i,c,i^{\prime}+1}=d_{i,c,i^{\prime}}+\left|\\!\left|x_{i^{\prime}+1}-x_{c}\right|\\!\right|^{\alpha}$.
By induction, at the end of the iteration $j$,
$f_{\alpha}({\mathcal{C}}_{1,j})$ is stored in the vector $v$ and $c$. Even
with an initial lower bound, the complexity is at least in $O(N)$ to compute
each value $f_{\alpha}({\mathcal{C}}_{1,j})$, for a total time complexity in
$O(N^{2})$. The optimal lower bounds reduces practical computations, without
any improvement of the worst case complexity. The validity of the restrictions
are provided by Lemma 6. $\hfill\square$

Algorithm 3: Computing $f_{\alpha}({\mathcal{C}}_{j^{\prime},j})$ for all
$j^{\prime}\in[\\![1;j]\\!]$ for a given $j\in[\\![1;N]\\!]$
---
Input: $j\in[\\![2;N]\\!]$, $\alpha>0$, $N$ points of ${\mathbb{R}}^{2}$,
$E=\\{x_{1},\dots,x_{N}\\}$
Optional input: $\underline{c}=1$ or $\underline{c}\in[\\![1;j]\\!]$, a lower
bound to an optimal center of cluster ${\mathcal{C}}_{1,j}$.
Output: for all $j^{\prime}\in[\\![1;j]\\!]$,
$v_{j^{\prime}}=f_{\alpha}({\mathcal{C}}_{j^{\prime},j})$ and $c_{j^{\prime}}$
a center of cluster ${\mathcal{C}}_{j^{\prime},j}$
``
`` define vector $v$ with $v_{j^{\prime}}=0$ for all
$j^{\prime}\in[\\![1;j]\\!]$
`` define vector $c$ with $c_{j^{\prime}}=j$ for all
$j^{\prime}\in[\\![1;j]\\!]$
`` define vector $temp$ with $temp_{i}=0$ for all $i\in[\\![1;j]\\!]$
``
`` for $j^{\prime}=j-1$ to $1$ with increment $j^{\prime}=j^{\prime}-1$
``for $k=c_{j^{\prime}+1}$ to $\max(j^{\prime},\underline{c})$ with increment
$k=k-1$
`` $temp_{k}=temp_{k}+\left|\\!\left|x_{k}-x_{j}\right|\\!\right|^{\alpha}$
`` end for
`` Compute $v_{k}=\displaystyle\min_{k\in[\\![a,b]\\!]}temp_{k}$,
$c_{k}=\mbox{arg}\displaystyle\min_{k\in[\\![a,b]\\!]}temp_{k}$
`` where $a=c_{j-1}$ and $b=\min(j-1,\overline{c})$
`` end for
``
return vectors $v$ and $c$

###### Proposition 5

Algorithm 3 computes the cluster costs
$f_{\alpha}({\mathcal{C}}_{j^{\prime},j})$ for all
$j^{\prime}\in[\\![1;j]\\!]$ for a given $j\in[\\![1;N]\\!]$ with a complexity
in $O(j^{2})$ time and in $O(N)$ memory space.

Proof: Algorithm 3 is similar with Algorithm 2: to compute the costs
$f_{\alpha}({\mathcal{C}}_{j^{\prime},j})$ for all
$j^{\prime}\in[\\![1;j]\\!]$ for a given $j$, Algorithm 3 constructs and store
the costs with $j$ decreasing, with a temporary vector containing the required
values of $d_{1,j^{\prime},j}$ at the step $j$, the step $j-1$ updating the
values $d_{j-1,l,j}$ using $O(1)$ computations
$d_{j^{\prime}-1,l,j}=d_{j^{\prime},l,j}+\left|\\!\left|x_{j^{\prime}-1}-x_{c}\right|\\!\right|^{\alpha}$.
By induction, at the end of the iteration $j^{\prime}$,
$f_{\alpha}({\mathcal{C}}_{j^{\prime},j})$ is stored in the vector $v$ and
$c$. Even with an initial upper bound, the complexity is at least in $O(j)$ to
compute each value $f_{\alpha}({\mathcal{C}}_{j^{\prime},j})$, for a total
time complexity in $O(j^{2})$. The optional lower bounds reduces practical
computations, without any improvement of the worst case complexity. The
validity of the restrictions are provided by Lemma 6. $\hfill\square$

##  6 Dynamic Programming algorithm and complexity results

in this section, the polynomial complexity of $K$-$\alpha$-Med2dPF is proven,
distinguishing the case $K=2$ from the general case with $K>2$.

###  6.1 The case $2$-$\alpha$-Med2dPF

In the case $k=2$, $2$-$\alpha$-Med2dPF can be reformulated with Proposition
2, considering the following optimization problem instead of (9):

$2-\alpha-
Med2dPF\phantom{2}:\phantom{2}\min_{j\in[\\![1;N-1]\\!]}f_{\alpha}({\mathcal{C}}_{1,j})+f_{\alpha}({\mathcal{C}}_{j+1,N})$
(22)

Algorithm 4 solves this reformulated problem enumerating all the possibilities
following $j\in[\\![1;N-1]\\!]$, with an efficient computation of costs
$f_{\alpha}({\mathcal{C}}_{1,j})$ using Algorithm 2 and
$f_{\alpha}({\mathcal{C}}_{j+1,N})$ with Algorithm 3. Both computations have a
complexity in $O(N^{2})$ time and $O(N)$ space.

Algorithm 4: $2$-$\alpha$-Med2dPF
---
Input: $\alpha>0$, $N$ points of ${\mathbb{R}}^{2}$,
$E=\\{x_{1},\dots,x_{N}\\}$
Output: $M$ the optimal value of $2$-$\alpha$-Med2dPF, and an optimal solution
``
`` define vector $f,l$ with $f_{j}=l_{j}=0$ for all $j\in[\\![1;N]\\!]$
`` initialize integers $c,j^{*}$ with $c,j^{*}=1$ and float $M=0.0$
``
`` run Algorithm 2:
`` store $f_{i}:=f_{\alpha}({\mathcal{C}}_{1,i})$ for all
$i\in[\\![1;N-K+1]\\!]$
`` store $c:=c_{1,N}$, $M=f_{\alpha}({\mathcal{C}}_{1,N-1})$
``
`` run Algorithm 3 with $c$ as lower bound:
``store $l_{i}:=f_{\alpha}({\mathcal{C}}_{1,i})$ for all
$i\in[\\![1;N-K+1]\\!]$
``
`` for $j=1$ to $N-1$
``if $f_{j}+l_{j+1}<M$ then $M:=f_{j}+l_{j+1}$ and $j^{*}=j$
`` end for
``
return $M$ and $[\\![1;j^{*}]\\!]$,$[\\![j^{*}+1;N]\\!]$

With a similar algorithm, Algorithm 4 explore all the local minima of
$2$-$\alpha$-Med2dPF. Once the costs are computed in $O(N^{2})$ time, the
costs and $\alpha$-medoids can be stored. Denoting $c_{i}$ (resp
$c^{\prime}_{i}$) the $\alpha$-medoids of cluster ${\mathcal{C}}_{1,i}$ (resp
${\mathcal{C}}_{i,N}$) $[\\![1;j]\\!],[\\![j+1;N]\\!]$ defines a local minimum
if $d(c^{\prime}_{i},j)\geqslant d(c_{i},j)$ and
$d(c^{\prime}_{i},j+1)\leqslant d(c_{i},j+1)$, such remaining computations are
in $O(1)$ for each possible local optimum, and thus in $O(N)$ to test the
$N-1$ possible local optimums. Computing all the local optimums (that are at
most $N-1$) has thus a complexity in $O(N^{2})$.

Algorithm 4’: Exhaustive search of Local minima of $2$-$\alpha$-Med2dPF
---
Input: $\alpha>0$, $N$ points of ${\mathbb{R}}^{2}$,
$E=\\{x_{1},\dots,x_{N}\\}$
``
`` define vector $f,l$ with $v_{j}=0$ for all $j\in[\\![1;N]\\!]$
`` define vector $c,c^{\prime}$ with $c_{j}=1$ and $c^{\prime}_{j}=N$ for all
$j\in[\\![1;N]\\!]$
`` initialize integer $j^{*}$ with $j^{*}=1$ and float $M=0.0$
``
`` run Algorithm 2:
`` store $f_{i}:=f_{\alpha}({\mathcal{C}}_{1,i})$ for all
$i\in[\\![1;N-K+1]\\!]$
`` store $c_{i}:=c_{1,i}$, $M=f_{\alpha}({\mathcal{C}}_{1,N-1})$
``
`` run Algorithm 3 with $c$ as lower bound:
``store $l_{i}:=f_{\alpha}({\mathcal{C}}_{1,i})$ for all
$i\in[\\![1;N-K+1]\\!]$
`` store $c^{\prime}_{i}:=c_{i,N}$
``
`` for $j=1$ to $N-1$
``if if $d(c^{\prime}_{i},j)\geqslant d(c_{i},j)$ and
$d(c^{\prime}_{i},j+1)\leqslant d(c_{i},j+1)$
``then print local Minimum $[\\![1;j]\\!],[\\![j+1;N]\\!]$
`` end for
``
return

###  6.2 General cases $k$-$\alpha$-Med2dPF with $k>2$

In the general case, Proposition 2 allows to design a DP algorithm,
enumerating the possibilities among the possibly global optimal solutions.

######  Proposition 6 (Bellman equations)

Defining $M_{k,i}$ as the optimal cost of $K$-$\alpha$-Med2dPF among the
points indexed in $[\\![1,i]\\!]$ for all $k\in[\\![2,K]\\!]$ and
$i\in[\\![k,n]\\!]$, we have:

$\forall i\in[\\![1,n]\\!],\>\>\>M_{1,i}=f_{\alpha}({\mathcal{C}}_{1,i})$ (23)
$\forall i\in[\\![1,n]\\!],\>\forall
k\in[\\![2,K]\\!],\>\>\>M_{k,i}=\min_{j\in[\\![k-1,i-1]\\!]}(M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j+1,i}))$
(24)

Proof: (23) is trivial. We suppose $k\geqslant 2$ and prove (24). Let
$i\in[\\![1,n]\\!]$. Selecting for each $j\in[\\![k-1,i-1]\\!]$ an optimal
solution of $(k-1)$-$\alpha$-Med2dPF among points indexed in $[\\![1,j]\\!]$,
and adding cluster $[\\![j,i]\\!]$, it makes a feasible solution for
$(k-1)$-$\alpha$-Med2dPF among points indexed in $[\\![1,i]\\!]$ with a cost
$M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j+1,i})$. This last cost is greater than
the optimal $k$-$\alpha$-Med2dPF cost, thus $M_{k,i}\leqslant
M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j+1,i})$.

$M_{k,i}\leqslant\min_{j\in[\\![k-1,i-1]\\!]}(M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j+1,i}))$
(25)

Let $j_{1}<j_{2}<\dots<j_{k-1}$ indexes such that
$[\\![1,j_{1}]\\!],[\\![j_{1}+1,j_{2}]\\!],\dots,[\\![j_{k-1}+1,N]\\!]$
defines an optimal solution of $k$-$\alpha$-Med2dPF, its cost is $M_{k,i}$.
Necessarily, $j_{1},j_{2},\dots,j_{k-2}$ defines an optimal solution of
$(k-1)$-$\alpha$-Med2dPF among points indexed in $[\\![1,j_{k-1}]\\!]$. On the
contrary, a strictly better solution for $M_{k,i}$ would be constructed adding
$[\\![j_{k-1}+1,N]\\!]$. We have thus:
$M_{k,i}=M_{k-1,j_{k-1}}+f_{\alpha}({\mathcal{C}}_{j_{k-1}+1,i})$. Combined
with (25), it proves :
$M_{k,i}=\min_{j\in[\\![k-1,i-1]\\!]}(M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j+1,i}))$.
$\hfill\square$

Algorithm 5: dynamic programming algorithm for $K$-$\alpha$-Med2dPF
---
Input:
\- $\alpha>0$ ;
\- $N$ points of ${\mathbb{R}}^{2}$, $E=\\{x_{1},\dots,x_{N}\\}$ such that for
all $i\neq j$, $x_{i}\phantom{0}\mathcal{I}\phantom{0}x_{j}$ ;
\- $K\in{\mathbb{N}}^{*}$ the number of clusters
``
`` initialize matrix $M$ with $M_{k,i}=0$ for all
$k\in[\\![1;K-1]\\!],i\in[\\![k;N-K+k]\\!]$
`` initialize vectors $u$ with $u_{i}=\max(1,i-1)$ for all
$i\in[\\![1;N-1]\\!]$
``
`` sort $E$ following the order of Proposition 2
`` run Algorithm 2:
`` store $M_{1,i}:=f_{\alpha}({\mathcal{C}}_{1,i})$ for all
$i\in[\\![1;N-K+1]\\!]$
`` store $u_{i}:=c_{1,i}$ for all $i\in[\\![1;N]\\!]$
``
`` for $i=2$ to $N-1$
`` compute and store $f_{\alpha}({\mathcal{C}}_{i^{\prime},i})$ for all
$i^{\prime}\in[\\![1;i]\\!]$ with Algorithm 3 using $u_{i}$ as lower bound
`` for $k=\max(2,K+i-N)$ to $\min(K-1,i)$
`` set
$M_{k,i}=\min_{j\in[\\![1,i]\\!]}C_{k-1,j-1}+f_{\alpha}({\mathcal{C}}_{j,i})$
`` end for
`` delete the stored $f_{\alpha}({\mathcal{C}}_{i^{\prime},i})$ for all
$i^{\prime}\in[\\![1;i]\\!]$
`` end for
``
`` compute and store $f_{\alpha}({\mathcal{C}}_{i^{\prime},N})$ for all
$i^{\prime}\in[\\![1;N]\\!]$ with Algorithm 3 using $u_{N}$ as lower bound
`` set
$OPT=\min_{j\in[\\![2,N]\\!]}M_{K-1,j-1}+f_{\alpha}({\mathcal{C}}_{j,N})$
`` set
$j=\mbox{argmin}_{j\in[\\![2,N]\\!]}M_{K-1,j-1}+f_{\alpha}({\mathcal{C}}_{j,N})$
`` delete the stored $f_{\alpha}({\mathcal{C}}_{i^{\prime},N})$ for all
$i^{\prime}\in[\\![1;N]\\!]$
``
`` $i=j$
`` initialize ${\mathcal{P}}=\\{[\\![j;N]\\!]\\}$, a set of sub-intervals of
$[\\![1;N]\\!]$.
`` for $k=K-1$ to $2$ with increment $k\leftarrow k-1$
`` compute and store $f_{\alpha}({\mathcal{C}}_{i^{\prime},i})$ for all
$i^{\prime}\in[\\![1;i]\\!]$
`` find $j\in[\\![1,i]\\!]$ such that
$M_{i,k}=M_{j-1,k-1}+f_{\alpha}({\mathcal{C}}_{j,i})$
`` add $[\\![j,i]\\!]$ in ${\mathcal{P}}$
`` delete the stored $f_{\alpha}({\mathcal{C}}_{i^{\prime},i})$ for all
$i^{\prime}\in[\\![1;i]\\!]$
`` $i=j-1$
`` end for
``
return $OPT$ the optimal cost and the partition
${\mathcal{P}}\cup[\\![1,i]\\!]$

These relations allow to compute the optimal values of $M_{k,i}$ by dynamic
programming in the Algorithm 4. $M_{K,N}$ is the optimal value of
$k$-$\alpha$-Med2dPF, backtracking on the matrix $(M_{k,i})_{i,k}$ computes
the optimal partitioning clusters.

Actually, to compute the optimal value $M_{K,N}$ and to recover the indexes of
this optimal solution by backtracking, some elements of the matrix
$(M_{k,i})_{i,k}$ are useless to compute. For $i<N$, there is no need to
compute the values $M_{K,i}$. For $k<K$, there is no need to compute the
values $M_{k,N}$. In the line $k<K$, the elements $M_{k,i}$ for $i<k$ are not
used, and $M_{k,k}=0$. In the line $k<K$, the elements with $i>N-K+k$ will not
be used in the backtracking operations starting from $M_{K,N}$. In a line
$k<K$, the indexes to compute fulfill $k<i\leqslant N-K+k$.

To compute $M_{k,i}$, it requires the previous optimal computations of
$M_{k-1,j}$ with $j<i$. It is possible (similarly with dupin2019planar ;
dupin2020polynomial ), to compute the matrix $M$ following the index $k$. In
Algorithm 4, the matrix $M$ is computed line by line following the index $i$
increasing. Indeed, to compute each value $M_{k,i}$ of the line $i$, it
requires the same cluster costs $f_{\alpha}({\mathcal{C}}_{i^{\prime},i})$ for
all $i^{\prime}\in[\\![1;i]\\!]$, computed by Algorithm 3. It allows to use
the cost computations in Algorithm 3 one time, and to delete the vector costs
one the line $i$ is completed, minimizing the space memory used. On the
contrary, the first version presented in dupin2019medoids  stores the whole
matrix of costs, inducing a space complexity in $O(N^{2})$, whereas Algorithm
4 has a space complexity in $O(KN)$, the size of the DP matrix.

###  6.3 Complexity results

###### Theorem 6.1

Let $E=\\{x_{1},\dots,x_{N}\\}$ a subset of $N$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $x_{i}\phantom{0}\mathcal{I}\phantom{0}x_{j}$.
Clustering $E$ with $K$-$\alpha$-Med2dPF is solvable to optimality in
polynomial time with Algorithm 4. The complexity is $O(N^{3})$ time and in
$O(KN)$ memory space , and $O(N^{2})$ time and in $O(N)$ memory space when
$K=2$. $1$-$\alpha$-Med2dPF is solvable in $O(N^{2})$ time in general, the
cases of a convex or concave 2d PF with $\alpha>0$ induces a time complexity
in $O(N\log N)$.

Proof:The case $K=1$ = is given in section 4.3 with Proposition 3. The case
$K=2$ is given using Algorithm 4 as described in section 6.1. In the
following, we focus on the cases $K>2$ and Algorithm 5. (24) uses only values
$M_{k,i}$ with $j<k$ in Algorithm 5. Induction proves that $M_{k,i}$ has its
final value for all $i\in[\\![1,N]\\!]$ at the end of the for loops from $k=2$
to $K$. $M_{k,N}$ is thus at the end of these loops the optimal value of
k-$\alpha$-Med2dPF clustering among the $N$ points of $E$. The backtracking
phase searches for the equalities in
$M_{i,k}=M_{j-1,k-1}+f_{\alpha}({\mathcal{C}}_{j,i})$ to return the optimal
clusters ${\mathcal{C}}_{j^{\prime},i}$. Let us analyze the complexity.

Sorting and indexing the elements of $E$ following Lemma 2 has a complexity in
$O(N\log N)$. The first line $M_{1,i}$ is computed in $O(N^{2})$ time using
Algorithm 2 and Proposition 4. Then, to compute the line $i<N$ of the DP
matrix $M_{k,i}$, the cost computations using Algorithm 3 have a complexity in
$O(N^{2})$ time with Proposition 5, and the remaining operations iterating
(24) have a time complexity in $O(NK)$. Each line $i<N$ is thus computed in
$O(N^{2})$ time, the bottleneck is the computations of cluster costs, and the
total complexity to compute the DP matrix $M$ is in $O(N^{3})$ time. The
backtracking phase requires $K$ computations having a complexity in $O(N^{2})$
time, re-computing the cluster costs, the complexity of this phase is in
$O(KN^{2})$ time. Hence, the complexity of Algorithm 5 is in $O(N^{3})$ time
and in $O(KN)$ memory space. $\square$

##  7 Speeding-up the DP algorithms

In this section, it is studied how to speed-up the DP algorithms in practice,
without improving the theoretical complexity proven in section 6. On one hand,
it is investigated how to remove useless computations in Algorithms 4 and 5.
On the other hand, parallelization issues are discussed.

###  7.1 Additional stopping criterion

An additional stopping criterion can be designed to stop the enumeration of
cases $M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j+1,i})$ to compute $M_{k,i}$:

###### Lemma 7

Let $i\in[\\![1,N]\\!]$ and $k\in[\\![2,K]\\!]$. Let $\beta$ an upper bound
for $M_{i,k}$. We suppose it exist $j_{0}\in[\\![1,i]\\!]$ such that
$f_{\alpha}({\mathcal{C}}_{j_{0},i})\geqslant\beta$. Then, each optimal index
$j^{*}$ such that
$M_{k,i}=M_{k-1,j^{*}}+f_{\alpha}({\mathcal{C}}_{j^{*}+1,i})$ fulfills
necessarily $j^{*}>j_{0}$. In other words,
$M_{k,i}=\min_{j\in[\\![\max(k-1,j_{0}),i-1]\\!]}M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j+1,i})$

Proof: We have $f_{\alpha}({\mathcal{C}}_{j_{0},i})\geqslant\beta\geqslant
M_{k,i}$. Lemma 4 implies that for all $j<j_{0}$,
$f_{\alpha}({\mathcal{C}}_{j_{0},i})>f_{\alpha}({\mathcal{C}}_{j_{0},i})\geqslant
M_{k,i}$. Using $M_{k-1,j}\geqslant 0$,
$M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j_{0},i})>M_{k,i}$, and thus
$M_{k,i}=\min_{j\in[\\![\max(k-1,j_{0}),i-1]\\!]}M_{k-1,j}+f_{\alpha}({\mathcal{C}}_{j+1,i})$.
$\hfill\square$

Lemma 7 allows to compute optimal value of each value of the DP matrix using
less computations than the algorithms proposed in the last section. A strong
interest of this property is that it avoids to compute the costs
$f_{\alpha}({\mathcal{C}}_{j,i})$ with the smallest values of $j$, ie the
greatest gap $|i-j|$, which are the more time consuming cost computations. We
discuss in the following how to incorporate such stopping criterion in the
Algorithms 4 and 5.

###  7.2 Speeding-up the case $K=2$

In the case of $2$-$\alpha$-Med2dPF, the stopping criterion can be processed
also with index $j$ increasing:

###### Lemma 8

Let $\beta$ an upper bound for $M_{N,2}$. We suppose it exist
$j_{1}\in[\\![1,N]\\!]$ such that
$f_{\alpha}({\mathcal{C}}_{j_{1},N})\geqslant\beta$. We suppose it exist
$j_{2}\in[\\![1,N]\\!]$ such that
$f_{\alpha}({\mathcal{C}}_{1,j_{2}})\geqslant\beta$. Then,
$M_{N,2}=\min_{j\in[\\![j_{1},j_{2}]\\!]}f_{\alpha}({\mathcal{C}}_{1,j})+f_{\alpha}({\mathcal{C}}_{j+1,N})$.

Proof: Lemma 7 implies that $j_{1}$ is a lower bound for the optimal
separation index. Similarly, $j_{2}$ is an upper bound for the optimal
separation index, using that $j\mapsto f_{\alpha}({\mathcal{C}}_{1,j})$ is
increasing with Lemma 4.

Incorporating the stopping criterion of Lemma 8 in Algorithm 4 shall minimize
the computations of $f_{\alpha}({\mathcal{C}}_{1,j})$ and
$f_{\alpha}({\mathcal{C}}_{j+1,N})$. Costs computations of Algorithm 2 and 3
will be proceeded only when needed. Firstly, cost computations
$f_{\alpha}({\mathcal{C}}_{1,j})$ (resp $f_{\alpha}({\mathcal{C}}_{j,N})$) are
proceeded for heuristic $j\in[\\![1;N/2]\\!]$ (resp $j\in[\\![N/2;N]\\!]$),
with an interruption of Algorithm 2 and 3. Then, we set $j_{1}=j_{2}=N/2$
$\beta=f_{\alpha}({\mathcal{C}}_{1,N/2})+f_{\alpha}({\mathcal{C}}_{N/2+1,N})$,
$\beta$ defines a feasible solution of $2$-$\alpha$-Med2dPF, and upper bound
of the optimal cost. Then, the interrupted cost computations are continued
till the stopping criterion is not reached, computing costs
$f_{\alpha}({\mathcal{C}}_{1,j})+f_{\alpha}({\mathcal{C}}_{j+1,N})$ and
updating $\beta$ to the best found value which may activate earlier the
stopping criterion of Lemma 8.

###  7.3 Improved algorithm in the general case

Lemma 7 can be used to stop earlier the optimal computations of each value in
the DP matrix $M_{k,i}$. For each $i\in[\\![2,N]\\!]$, the stopping criterion
is used to stop the cost computations when all the $M_{k,i}$ for $k>2$ are
proven optimal using Lemma 7. The advantage of such stopping criterion is to
avoid the most time consuming cost computations.

Lemma 7 can also be used in a recursive approach using memoisation. In such
approach, the cost computations and some values of the DP matrix are memoised,
and Lemma 7 allows to reduce the number of values to compute in the DP matrix.
However, such memoisation can induce a memory space in $O(N^{2})$.

###  7.4 Parallelization issues

A parallel implementation is a practical issue to speed up the DP algorithms.
In Algorithms 2 and 3, the inner loop induces independent computations that
can be processed in parallel, the implementation is straightforward in an
environment like OpenMP. This makes the parallelization of the crucial phase
in terms of complexity in the Algorithm 4 (and also 4’) for the case $K=2$.
The final loop in Algorithm 2 can also be parallelized, this is less crucial
than the parallelization of Algorithm 2 and 3, as this last phase has a linear
time complexity. After the improvement proposed is section 7.2, the
computations in the inner loops remain independent. For the general case, the
DP algorithm as written in Algorithm 5 keeps independent computations for the
inner loops to compute the costs of clusters.

##  8 Conclusion and perspectives

This paper examined properties of an extended version of the K-medoid and
K-median problems in the special case of a discrete set of non-dominated
points in a two dimensional Euclidian space. A characterization of global and
local optima is proven with interval clustering. It is proven that there is at
most ${N}\choose{K}$ local minima for $K$-$\alpha$-Med2dPF problems in a 2d PF
of size $N$. For small values of $K$, local minima can be enumerated. The
interval clustering property allows to design a dynamic programming algorithm
with a polynomial complexity to compute the global optimal cost and a global
optimal solution. The complexity is proven in $O(N^{3})$ time and $O(KN)$
memory space when $K\geqslant 3$, cases $K=2$ having a time complexity in
$O(N^{2})$. $1$-$\alpha$-Med2dPF problems are solvable in $O(N\log N)$ time
when $\alpha>1$ the 2d PF is concave or convex. Practical speed-up are also
proposed, in relation with discussions on parallelization issues.

The complexity in $O(N^{3})$ may be a bottleneck to deal with very large 2d
PF, which open new perspectives. Heuristics may apply efficiently for such
cases. Initialization strategies can use optimal solutions of p-centre or
p-dispersion problems in a 2d PF or in 1d cases after projection. Having a NP-
hard complexity proven for general planar cases of p-median problems, the
cases of 3d PF are also NP-hard problems. For such cases, perspectives are
opened to design specific heuristics, but also to study approximation
algorithms.

## References

  * [1] D. Aloise, A. Deshpande, P. Hansen, and P. Popat.  NP-hardness of Euclidean sum-of-squares clustering.  Machine learning, 75(2):245–248, 2009.
  * [2] A. Auger, J. Bader, D. Brockhoff, and E. Zitzler.  Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences.  In Proceedings of GECCO 2009, pages 563–570. ACM, 2009.
  * [3] P. Avella, A. Sassano, and I. Vasilev.  Computational study of large-scale p-median problems.  Mathematical Programming, 109(1):89–114, 2007.
  * [4] C. Beltran, C. Tadonki, and J. P. Vial.  Solving the p-median problem with a semi-lagrangian relaxation.  Computational Optimization and Applications, 35(2):239–260, 2006\.
  * [5] K. Bringmann, S. Cabello, and M. Emmerich.  Maximum volume subset selection for anchored boxes.  arXiv preprint arXiv:1803.00849, 2018.
  * [6] K. Bringmann, T. Friedrich, and P. Klitzke.  Two-dimensional subset selection for hypervolume and epsilon-indicator.  In Annual Conference on Genetic and Evolutionary Computation, pages 589–596. ACM, 2014.
  * [7] N. Dupin.  Modélisation et résolution de grands problèmes stochastiques combinatoires: application à la gestion de production d’électricité.  PhD thesis, Univ. Lille 1, 2015.
  * [8] N. Dupin.  Polynomial algorithms for p-dispersion problems in a 2d pareto front.  arXiv preprint arXiv:2002.11830, 2020.
  * [9] N. Dupin, F. Nielsen, and E. Talbi.  Dynamic programming heuristic for k-means clustering among a 2-dimensional pareto frontier.  7th Internat. Conf. on Metaheuristics and Nature Inspired Computing, 2018.
  * [10] N. Dupin, F. Nielsen, and E. Talbi.  k-medoids clustering is solvable in polynomial time for a 2d Pareto front.  In World Congress on Global Optimization, pages 790–799. Springer, 2019.
  * [11] N. Dupin, F. Nielsen, and E. Talbi.  Clustering a 2d Pareto Front: p-center problems are solvable in polynomial time.  In International Conference on Optimization and Learning, pages 179–191. Springer, 2020.
  * [12] M. Ehrgott and X. Gandibleux.  Multiobjective combinatorial optimization - theory, methodology, and applications.  In Multiple criteria optimization: State of the art annotated bibliographic surveys, pages 369–444. Springer, 2003.
  * [13] S. Elloumi.  A tighter formulation of the p-median problem.  Journal of combinatorial optimization, 19(1):69–83, 2010.
  * [14] E. Erkut.  The discrete p-dispersion problem.  European Journal of Operational Research, 46(1):48–60, 1990.
  * [15] F. Fomin, P. Golovach, and K. Simonov.  Parameterized k-clustering: The distance matters!  arXiv preprint arXiv:1902.08559, 2019.
  * [16] A. Grønlund, K. Larsen, A. Mathiasen, J. Nielsen, S. Schneider, and M. Song.  Fast exact k-means, k-medians and Bregman divergence clustering in 1d.  arXiv preprint arXiv:1701.07204, 2017.
  * [17] P. Hansen and I. Moon.  Dispersing facilities on a network.  Cahiers du GERAD, 1995.
  * [18] R. Hassin and A. Tamir.  Improved complexity bounds for location problems on the real line.  Operations Research Letters, 10(7):395–402, 1991.
  * [19] W. Hsu and G. Nemhauser.  Easy and hard bottleneck location problems.  Discrete Applied Mathematics, 1(3):209–215, 1979.
  * [20] A. Jain.  Data clustering: 50 years beyond k-means.  Pattern recognition letters, 31(8):651–666, 2010.
  * [21] O. Kariv and S. Hakimi.  An algorithmic approach to network location problems. ii: The p-medians.  SIAM Journal on Applied Mathematics, 37(3):539–560, 1979.
  * [22] L. Kaufman and P. Rousseeuw.  Clustering by means of medoids.  North-Holland, 1987.
  * [23] T. Kuhn, C. Fonseca, L. Paquete, S. Ruzika, M. Duarte, and J. Figueira.  Hypervolume subset selection in two dimensions: Formulations and algorithms.  Evolutionary Computation, 24(3):411–425, 2016.
  * [24] S. Lloyd.  Least squares quantization in PCM.  IEEE transactions on information theory, 28(2):129–137, 1982.
  * [25] M. Mahajan, P. Nimbhorkar, and K. Varadarajan.  The planar k-means problem is NP-hard.  Theoretical Computer Science, 442:13–21, 2012.
  * [26] N. Megiddo and K. Supowit.  On the complexity of some common geometric location problems.  SIAM journal on computing, 13(1):182–196, 1984.
  * [27] N. Megiddo and A. Tamir.  New results on the complexity of p-centre problems.  SIAM Journal on Computing, 12(4):751–758, 1983.
  * [28] N. Mladenović, J. Brimberg, P. Hansen, and J. Moreno-Pérez.  The p-median problem: A survey of metaheuristic approaches.  European Journal of Operational Research, 179(3):927–939, 2007\.
  * [29] F. Nielsen.  Output-sensitive peeling of convex and maximal layers.  Information processing letters, 59(5):255–259, 1996.
  * [30] T. Peugeot, N. Dupin, M-J Sembely, and C. Dubecq.  MBSE, PLM, MIP and Robust Optimization for System of Systems Management, Application to SCCOA French Air Defense Program.  In Complex Systems Design&Management, pages 29–40. Springer, 2017\.
  * [31] S. Ravi, D. Rosenkrantz, and G. Tayi.  Heuristic and special case algorithms for dispersion problems.  Operations Research, 42(2):299–310, 1994.
  * [32] A. Santos.  Solving large p-median problems using a lagrangean heuristic.  2009\.
  * [33] S. Sayın.  Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming.  Mathematical Programming, 87(3):543–560, 2000.
  * [34] E. Schubert and P. Rousseeuw.  Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms.  arXiv preprint arXiv:1810.05691, 2018.
  * [35] W. Sheng and X. Liu.  A genetic k-medoids clustering algorithm.  Journal of Heuristics, 12(6):447–466, 2006.
  * [36] E. Talbi.  Metaheuristics: from design to implementation, volume 74.  Wiley, 2009.
  * [37] A. Tamir, D. Pérez-Brito, and J. Moreno-Pérez.  A polynomial algorithm for the p-centdian problem on a tree.  Networks: An International Journal, 32(4):255–262, 1998.
  * [38] D. Wang and Y. Kuo.  A study on two geometric location problems.  Information processing letters, 28(6):281–286, 1988.
  * [39] E. Zio and R. Bazzo.  A clustering procedure for reducing the number of representative solutions in the pareto front of multiobjective optimization problems.  European Journal of Operational Research, 210(3):624–634, 2011\.