What is known about the following point placement problem?
For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute \begin{eqnarray*} \mu_1(N,n)\triangleq\min_{\mathcal{P}\subset \mathcal{G},\,|\mathcal{P}|=n}\sum_{g\in \mathcal{G} }d_1(g,\mathcal{P}) \end{eqnarray*} where $d_1$ denotes Manhattan distance ($l_1$ distance).

  1. Any known reasonably efficient algorithms to compute $\mu_1(N,n)$?
  2. What (symmetry) properties one should expect from an optimal $\mathcal{P}$ or its convex hull?
  3. Is anything known about continuous versions of this problem? For instance, the grid $\mathcal{G}$ is replaced by a unit square $\mathcal{S}$, and $\mathcal{P}$ is measurable subset of $\mathcal{S}$ or area $\sigma<1$ - and of course a different definition of $\mu_1$

It looks related to computing some type of 'optimal' $l_1$-DVD (Discrete Voronoi Diagram) for $\mathcal{G}$.

  • $\begingroup$ Complexity theory will not help you with this problem: Since the underlying language is sparse, Mahaney's theorem makes it unlikely that you should be able to establish NP-hardness. $\endgroup$ – Gamow Mar 30 '20 at 8:20
  • $\begingroup$ Thanks, @Gamow. I modified the question. $\endgroup$ – user56067 Mar 30 '20 at 15:08
  • $\begingroup$ So, choose $n$ "centers" in the $N\times N$ grid so as to minimize the sum, over all points in the grid, of the distance from the point to its nearest center? This seems like a special case of the metric $k$-medians problem, for which there are poly-time algorithms that compute solutions with value at most a constant times the optimal. Most of those algorithms are LP-based. You might study the integrality gap (if any) of the underlying LP in this particular case, and/or use an LP (or ILP) solver to solve moderate-sized instances. $\endgroup$ – Neal Young Apr 1 '20 at 20:02
  • $\begingroup$ You could also adapt the standard local-improvement algorithms for centroidal power diagrams to this problem, although those algorithms work better for minimizing the sum of the squared Euclidean distances. $\endgroup$ – Neal Young Apr 1 '20 at 20:03

Your Answer

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

Browse other questions tagged or ask your own question.