<p>Ken Supowit proved that the following problem is NP-hard: Given a set <span class="math-container">$P$</span> of <span class="math-container">$n$</span> points in the Euclidean plane and an integer <span class="math-container">$k$</span>, partition <span class="math-container">$P$</span> into <span class="math-container">$k$</span> clusters so that the largest cluster diameter is minimized.</p>

<blockquote>
  <p>Kenneth J Supowit: "Topics in Computational Geometry"<br>
  Ph.D. thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign (1981), Report UIUCDCS-R-81-1062</p>
</blockquote>

<p>Tomás Feder and Dan Greene proved that even the problem of approximating the smallest possible cluster diameter within a factor of <span class="math-container">$1.97$</span> is NP-hard.</p>

<blockquote>
  <p>T Feder, D.H Greene: "Optimal algorithms for approximate clustering"<br>
  Proceedings of the 20th Annual ACM Symposium on the Theory Computing (1988), pp. 434-444</p>
</blockquote>

CC BY-SA 4.0
2018-11-10T20:30:57.310Z
Can you translate my problem into either of these problems?  They don't seem to be the same problem.
Lars Ericson
CC BY-SA 4.0
2018-11-15T00:47:29.677Z
Also the distance function is not necessarily Euclidean, it is an arbitrary real-valued metric.  For example Vincenty distance. https://en.wikipedia.org/wiki/Vincenty%27s_formulae
Lars Ericson
CC BY-SA 4.0
2018-11-10T15:10:18.940Z
2018-11-10T15:10:18.940Z
Gamow
<p>What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows:</p>

<p><strong>Input</strong>: </p>

<ul>
<li>A set <span class="math-container">$S=\{s_1,\ldots,s_n\}$</span>, where the elements <span class="math-container">$s_i$</span> are of some type <span class="math-container">$T$</span>.  </li>
<li>A distance metric <span class="math-container">$D:T\rightarrow [0, \infty)$</span>.  </li>
<li>A radius <span class="math-container">$r:[0, \infty)$</span></li>
</ul>

<p><strong>Output</strong>: A partition <span class="math-container">$S_1,\ldots,S_m$</span> of <span class="math-container">$S$</span> such that </p>

<ul>
<li><span class="math-container">$S_i\cap S_j=\emptyset, i\neq j$</span> and </li>
<li><span class="math-container">$S=\cup_{i=1}^m S_i$</span> and</li>
<li><span class="math-container">$D(s,t) \leq r$</span>, <span class="math-container">$s,t \in S_i$</span> and</li>
<li>There is no other partition with the same properties of size <span class="math-container">$m^{\prime} &lt; m$</span>.</li>
</ul>

<p><strong>NOTE:</strong> I am saying "a partition" not "the partition", because there may be multiple partitions of least size for the same set of points.  For example consider <span class="math-container">$2 n$</span> points on a large circle where the points are spaced such that each pair of points is distance <span class="math-container">$r$</span> apart.  In this case there are <span class="math-container">$2 n-1$</span> distinct least-sized partitions of minimum size <span class="math-container">$n$</span>.</p>

<p><strong>NOTE:</strong> The following algorithm will produce a partition with desired properties except that it is not guaranteed to be least size:</p>

<ul>
<li><span class="math-container">$i=1$</span></li>
<li>While <span class="math-container">$|S| &gt; 0$</span>:

<ul>
<li>Choose <span class="math-container">$e \in S$</span> and set <span class="math-container">$S:=S-\{e\}$</span></li>
<li><span class="math-container">$S_i=\{x\in S: D(e,x) \leq r\}$</span></li>
<li>Set <span class="math-container">$S:=S \setminus S_i$</span></li>
<li>Set <span class="math-container">$i:=i+1$</span></li>
</ul></li>
</ul>

<p><strong>NOTE:</strong> It has been suggested that this is an NP-hard problem, but the above partial solution is <span class="math-container">$O(n^2)$</span>.</p>

<p><strong>NOTE:</strong> This problem is an abstraction of <a href="https://stackoverflow.com/questions/53075481/how-do-i-cluster-a-list-of-geographic-points-by-distance">this geographic problem</a>.</p>

<np-hardness><computational-geometry>
A least sized partition of a set under a distance metric
Lars Ericson
# A least sized partition of a set under a distance metric

(Asked by: username_0 on 2018-11-10)

What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows:

**Input**:

* A set $S=\{s\_1,\ldots,s\_n\}$, where the elements $s\_i$ are of some type $T$.
* A distance metric $D:T\rightarrow [0, \infty)$.
* A radius $r:[0, \infty)$

**Output**: A partition $S\_1,\ldots,S\_m$ of $S$ such that

* $S\_i\cap S\_j=\emptyset, i\neq j$ and
* $S=\cup\_{i=1}^m S\_i$ and
* $D(s,t) \leq r$, $s,t \in S\_i$ and
* There is no other partition with the same properties of size $m^{\prime} < m$.

**NOTE:** I am saying "a partition" not "the partition", because there may be multiple partitions of least size for the same set of points. For example consider $2 n$ points on a large circle where the points are spaced such that each pair of points is distance $r$ apart. In this case there are $2 n-1$ distinct least-sized partitions of minimum size $n$.

**NOTE:** The following algorithm will produce a partition with desired properties except that it is not guaranteed to be least size:

* $i=1$
* While $|S| > 0$:
  + Choose $e \in S$ and set $S:=S-\{e\}$
  + $S\_i=\{x\in S: D(e,x) \leq r\}$
  + Set $S:=S \setminus S\_i$
  + Set $i:=i+1$

**NOTE:** It has been suggested that this is an NP-hard problem, but the above partial solution is $O(n^2)$.

**NOTE:** This problem is an abstraction of [this geographic problem](https://stackoverflow.com/questions/53075481/how-do-i-cluster-a-list-of-geographic-points-by-distance).

**Tags:** np-hardness, computational-geometry


---

## 1 answers

### Answer by username_1 on 2018-11-10. Score: 4

Ken Supowit proved that the following problem is NP-hard: Given a set $P$ of $n$ points in the Euclidean plane and an integer $k$, partition $P$ into $k$ clusters so that the largest cluster diameter is minimized.

> Kenneth J Supowit: "Topics in Computational Geometry"  
> Ph.D. thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign (1981), Report UIUCDCS-R-81-1062

Tomás Feder and Dan Greene proved that even the problem of approximating the smallest possible cluster diameter within a factor of $1.97$ is NP-hard.

> T Feder, D.H Greene: "Optimal algorithms for approximate clustering"  
> Proceedings of the 20th Annual ACM Symposium on the Theory Computing (1988), pp. 434-444

> **Comments:**
> **username_0**: Can you translate my problem into either of these problems?  They don't seem to be the same problem.  
> **username_0**: Also the distance function is not necessarily Euclidean, it is an arbitrary real-valued metric.  For example Vincenty distance. https://en.wikipedia.org/wiki/Vincenty%27s_formulae  

---

