algorithm - 给定 2d 中的一小组点，如何绘制在每个点周围不重叠的圆，以便它们的半径最大化？

Question

一个农夫有n只山羊。巧合的是，他在一 block 他想让山羊放牧的田地里也有 n 个固定岗位。他想用一根绳子把每只山羊拴在柱子上。他想给每只山羊尽可能多的空间——但是，山羊的绳索是出了名的容易缠在一起，所以他不能允许任何一只山羊能够闯入另一只山羊的领地。他最多可以使用多少根绳子？ (本题最多会有50只山羊)

想了想也不知道怎么解决这个问题。谢谢回答。

(原题:https://open.kattis.com/problems/goatropes)

Answer 1

考虑只有 2 个极点 p1、p2 位于距离 d(1,2) 的情况。让我们称 r1 为山羊在第 1 根杆上的绳子长度，r2 为山羊在第 2 根杆上的绳子长度。那么简单的关系是:

r1 + r2 <= d(1,2)

如果我们添加第三个极点(还有一只山羊)，那么我们可以再添加两个关系:

r1 + r3 <= d(1,3)
r2 + r3 <= d(2,3)

n 根杆子和 n 只山羊的处理方法是显而易见的。在任何情况下，它都会导致 (n x (n-1))/2 如上所述的不等式。现在让我们尝试最大化总绳索的尺寸。总绳会

R=r1+r2+r3+...+rn

现在问题表述为:

Maximize R=r1+r2+r3+...+rn

受到约束:

ri + rj <= d(i,j)  where i<j

这是线性规划问题的经典公式，搜索单纯形或任何其他合适的算法。