<p>What is known about the following point placement problem?<br>
For positive integers <span class="math-container">$N$</span>, <span class="math-container">$n&lt;N^2$</span>, and <span class="math-container">$N\times N$</span> grid <span class="math-container">$\mathcal{G}$</span>, compute
<span class="math-container">\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*}</span>
where <span class="math-container">$d_1$</span> denotes Manhattan distance (<span class="math-container">$l_1$</span> distance).</p>

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

<p>It looks related to computing some type of 'optimal' <span class="math-container">$l_1$</span>-DVD (Discrete Voronoi Diagram) for <span class="math-container">$\mathcal{G}$</span>.</p>

CC BY-SA 4.0
2020-03-30T08:20:57.203Z
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
CC BY-SA 4.0
2020-03-30T15:08:30.123Z
Thanks, @Gamow. I modified the question.
user56067
CC BY-SA 4.0
2020-04-01T20:02:10.897Z
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
CC BY-SA 4.0
2020-04-01T20:03:36.150Z
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
<ds.algorithms><optimization><ds.data-structures><computational-geometry><voronoi>
Optimal point placement on integer lattice
user56067
# Optimal point placement on integer lattice

(Asked by: username_0 on 2020-03-30)

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}$.

**Tags:** ds.algorithms, optimization, ds.data-structures, computational-geometry, voronoi

> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks, @username_1. I modified the question.  
> **username_2**: 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.  
> **username_2**: 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.  

---

## 0 answers

