# a geometric variant of k-medians. NP-hard or in P?

The following problem is a special case of k-medians. Is it NP-hard? Is it in P?

Input: $$n$$ points $$(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$$ with each $$y_i \ge 0$$, and an integer $$k$$.

Output: a set $$S$$ containing $$k$$ of the given points, of minimum cost, defined as $$\sum_i d((x_i,y_i), S)$$, where $$d((x_i, y_i), S) = \min\big(y_i, ~\min\{ y_i - y_j : j \in S \,\wedge\, y_j \le y_i \,\wedge\,|x_i - x_j| \le 1 \}\big).$$

I think of this as each point "falling" vertically just until it either (a) reaches the x-axis, or (b) is aligned horizontally with, and at distance at most 1 from, one of the $$k$$ chosen points. The goal is to choose the $$k$$ points to minimize the total distance fallen by the remaining points, as shown below. (The input is on the left, a solution with $$k=3$$ is on the right. The cost of the solution is the total length of the dashed vertical lines.)

$$~~~~~~~~~$$ $$~~~~~~~~~~~~~~~~~~~~~~$$ input $$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$ solution with $$k=3$$

• Interesting. My first thought was to use dynamic programming on the x-ordered points but thar doesn't seem to work: the cluster centers can all be assumed to have the same y coordinate as an input and an x-coordinate one off from an input, but it may be necessary to keep track of large sets of cluster centers that are all active at the same x coordinate. – David Eppstein May 4 '15 at 7:39
• @DavidEppstein, Agreed. Note that the $k$ chosen points are from the input points. I'd also be interested in the variant where each point is either "red" or "blue", the $k$ chosen points must be blue, and in the cost the sum is over the red points only. – Neal Young May 6 '15 at 16:34