# Finding the closest point to a sets of discrete points

In a paper I am reviewing, the authors define the following problem and construct an algorithm. They give no further references and I suspect it has appeared somewhere in the literature before.

Let $P_1,\ldots,P_n$ be sets of points in a space with a metric $d$. Define the distance to a set as $$\operatorname{dist}(x, P_i) = \min\{ d(x,p) \,|\, x \in P_i\}.$$ The problem is to compute $$\min_x \sum_{i=1}^n \operatorname{dist}(x, P_i).$$ What is the name of this problem? Has it been discussed in the literature? What if $d(x,P_i) = ||x - P_i||_2?$

• I don't know of any references to that specific formula, but wouldn't this be covered under optimization/minimization problems? – Ronny Jan 2 '13 at 17:23
• It seems like a generalized 1-median problem. – Suresh Venkat Jan 2 '13 at 17:42
• The 1-median problem would be to minimize sum_i sum_{p in P_i} d(x, p), right? Has the generalized version appeared anywhere? – Ben Jan 2 '13 at 18:57
• Not that I'm aware of. Of course it inherits all of the hardness of the 1-median since all the sets can be singletons. It should also admit the 2-approximation that comes from choosing one of the input points as the center. – Suresh Venkat Jan 6 '13 at 6:53

• That seems to be about the special case where the sets $P_i$ consist of every one of the $\binom{n}{p}$ subsets of $p$ points of the input, and the NP-hardness result in that paper requires $p$ to be non-constant. So this doesn't appear to say much about the hardness of the problem asked here in which the $P_i$ are specified, because expanding out all of the $p$-subsets into an explicit list of sets is not a polynomial-time reduction. – David Eppstein Jan 6 '13 at 2:02