0
$\begingroup$

We add a bit to: Bounds for minimax facility location in a convex region

Two earlier posts: Cutting convex regions into equal diameter and equal least width pieces - 2 and Facility location on manifolds

Definitions: The dispersal problem places $n$ points ('facilities') in a region $R$ such that the minimum pair-wise distance among them is maximized. In an optimal solution with $n$ facilities, let $D(i)$ be the distance from the $i$-th facility to the facility closest to it.

Question: If $R$ is a convex region and if $n$ facility points have been placed in it to achieve optimal dispersal, will all values of $D(i)$ be necessarily equal? If not, what is the upper bound of the ratio between the max value of $D(i)$ and the min value as a function of say, the shape of $R$, the dimensionality of $R$ and $n$?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ If $n=8$ and $R$ is the unit circle, having 7 equally spaced points on the circle and one in the center is optimal (from circle packing in a circle), which falsifies the first question. In general, the question is equivalent to asking how isolated a circle can be in an optimal circle packing. $\endgroup$
    – Daniel Weber
    Commented Sep 27, 2023 at 5:52
  • $\begingroup$ Thanks. i suspect the mapping to circle packing is not quite straightforward because if a facility is put on the boundary of R, only a fraction of a disk centered there will be inside R. Yes, I tend to agree with your conclusion that it is not necessary that all facility points in an optimal solution (one that maximizes least separation among them) are at the same least distance from the closest facility. and could you give an answer which has something on the upper bound asked in the question? $\endgroup$
    – Nandakumar R
    Commented Sep 27, 2023 at 17:03

0

Reset to default

You must log in to answer this question.