2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you translate my problem into either of these problems? They don't seem to be the same problem. $\endgroup$ – Lars Ericson Nov 10 '18 at 20:30
  • $\begingroup$ Also the distance function is not necessarily Euclidean, it is an arbitrary real-valued metric. For example Vincenty distance. en.wikipedia.org/wiki/Vincenty%27s_formulae $\endgroup$ – Lars Ericson Nov 15 '18 at 0:47

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.