# Optimal point placement on integer lattice

What is known about the following point placement problem?
For positive integers $$N$$, $$n, 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}$$.

• 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. – Gamow Mar 30 '20 at 8:20
• Thanks, @Gamow. I modified the question. – user56067 Mar 30 '20 at 15:08
• 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. – Neal Young Apr 1 '20 at 20:02
• 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. – Neal Young Apr 1 '20 at 20:03