2
$\begingroup$

Facility location studies optimal placement of a certain number $n$ of points (facilities) in some region $R$. (https://en.wikipedia.org/wiki/Facility_location_problem)

The minimax facility location problem finds $n$ locations in $R$ for the facility points such that: if $P$ is any point in $R$ and $d(P)$ is the distance from $P$ to the closest facility point, then the highest value of $d(P)$ as $P$ ranges over $R$ is minimized.

The dispersal problem places $n$ points in $R$ such that the minimum pair-wise distance among them is maximized.

Question: Is this claim true: "If the region $R$ is a closed and homogeneous manifold (such as a sphere or $S^1 \times S^1$) with a metric, then, for any $n$, if a given configuration of $n$ facility points solves one of the above problems, then, it automatically solves the other problem for that $n$"?

If the claim holds, does its converse also hold — "if both above problems have same answer for any $n$ in some $R$, then, $R$ is a closed and homogeneous manifold"?

Note: The earlier version of the post had a confused formulation of the maximin problem. Now, maximin has been replaced by dispersion.

Improve this question
$\endgroup$
4
  • $\begingroup$ I suppose that $R$ is a Riemannian manifold, not a Finsler manifold? $\endgroup$
    – Ben McKay
    Commented May 4, 2021 at 18:57
  • $\begingroup$ As to the type of manifolds being considered being wider than Riemannian - I would request experts to decide. $\endgroup$
    – Nandakumar R
    Commented May 4, 2021 at 20:47
  • $\begingroup$ Thank you. Made one more attempt to get the problem statement in order. $\endgroup$
    – Nandakumar R
    Commented May 5, 2021 at 18:42
  • 1
    $\begingroup$ Thanks; now the question is clear. $\endgroup$
    – Willie Wong
    Commented May 5, 2021 at 21:38

1 Answer 1

Reset to default
3
$\begingroup$

I believe the answer is No, the claim is not true. At least not if my reformulation of the question is correct.

What the OP calls dispersion is usually viewed as optimal packing of $n$ congruent circles, also known as the Tammes problem (e.g., this MO question).

The OP's minimax facility location problem I believe can be viewed as optimal cover by congruent disks, with the distance from any point $p \in R$ to a facility at most the radius of a covering disk.

So the OP's question is essentially:

Is the best packing configuration also the best covering configuration?

In the plane this is true, a result of Richard Kershner from 1939. So the OP's question is a natural extension.

Here is why I think that in more general situations, the claim is false. Consider packing and covering the flat square torus by congruent circles/disks. There has been considerable work on the packing question, a variant of the Tammes problem. There has been much less work on covering. However, the two papers cited below indicate that the optimal configurations are not the same for $n=3$.

First the optimal packing. Note the asymmetry:

     Torus3Pack

Next the optimal cover. Note the symmetry.

     Torus3Cover

I could be misinterpreting these two papers, but if not, then they provide an example showing the optimal packing and covering configurations are, in general, not identical.

Brandt, Madeline, William Dickinson, AnnaVictoria Ellsworth, Jennifer Kenkel, and Hanson Smith. "Optimal packings of two to four equal circles on any flat torus." Discrete Mathematics 342, no. 12 (2019): 111597. DOI.

Joós, Antal. "On covering the square flat torus by congruent discs." Australasian J. Combinatorics 75, no. 1 (2019): 113-126. PDF download.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the pointers and the quite surprising (conjectured) answer - quite hard to accept that the two questions can have different answers. Maybe same is the case even on a sphere. Maybe there are parallels to an earlier discussion: mathoverflow.net/questions/251604/… $\endgroup$
    – Nandakumar R
    Commented May 6, 2021 at 18:27
  • $\begingroup$ Yes, I think packing and covering on a sphere are not always identical, but I could not identify proven cases where they are known to differ. Partly because there are few proven cases. $\endgroup$
    – Joseph O'Rourke
    Commented May 6, 2021 at 19:34
  • 1
    $\begingroup$ Re that earlier question about thinnest ball covers: See especially Henry Cohn's answer: "Overall sphere covering is more complicated than sphere packing, and there seems to be no close relationship between the optimal solutions." $\endgroup$
    – Joseph O'Rourke
    Commented May 6, 2021 at 19:38
  • $\begingroup$ Reg the mapping of maximin to covering and dispersion to packing, is the equal sized disks condition obvious? for best dispersion, should every site have same distance to its closest site? To give a different example, pls see mathoverflow.net/questions/376672/…. There it was noted that "f maximum (minimum) area among n convex pieces is to be minimized (maximized), then, it is easy to see all pieces should have same area." but that similar statements are not obvious for quantities such as perimeter, diameter,... $\endgroup$
    – Nandakumar R
    Commented May 7, 2021 at 6:43
  • 1
    $\begingroup$ Thanks for pointing out that nice example! And it seems even if one replaces the big circle being tiled with a manifold such as a real projective plane, the packing behavior might be similar. So the claim of an optimal dispersion arrangement being an optimal maximin one too might not hold for all n even on manifolds that are both homogeneous and isotropic . $\endgroup$
    – Nandakumar R
    Commented May 8, 2021 at 18:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .