Let $ C $ be a connected and simply connected compact subset of the plane $ \mathbb{R}^{2} $. How can we pick $ n $ points, denoted $ x_{1},\ldots,x_{n} $, lying in $ C $ such that the total sum $ \displaystyle D \stackrel{\text{df}}{=} \sum_{i,j = 1}^{n} d(x_{i},x_{j}) $ of their pairwise distances is maximized? For example, $ C $ could be the region consisting of a simple closed curve and its interior.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ The question is unclear: how is the domain given in the input? How efficient you want your algorithm be (exact? approximate in some sense?). Also, what do you already know? $\endgroup$– Boris BukhFeb 23, 2015 at 1:06
-
5$\begingroup$ I don't think your question is easily answered. Here's an old paper on the topic: "On the sum of distances determined by a pointset"; Acta Mathematica Academiae Scientiarum Hungarica, Volume 7, Issue 3-4, pp 397-401. (Springer link) $\endgroup$– Joseph O'RourkeFeb 23, 2015 at 1:10
-
4$\begingroup$ When $n=1$, the solution can be found at sleepingcatsw.com/images/cats/luther_bed.jpg $\endgroup$– MartyFeb 23, 2015 at 10:14
-
1$\begingroup$ In the case n=2, a Google image search indicates that pairs of cats in a bed tend not to maximize their pairwise distance. This may be a case of sampling bias however. $\endgroup$– MartyFeb 24, 2015 at 0:41
-
$\begingroup$ I love the title which suggests an obvious near-solution: put $n$ unfriendly cats in room of shape $C$. $\endgroup$– Roland BacherMay 7, 2015 at 12:02
Add a comment
|