轮廓放置的最佳位置
Best position for contour placement
我有一个图表，其中节点代表城市（City 对象将人口和坐标作为字段），边代表它们之间的距离。如何计算圆形轮廓的中心，使其覆盖最多的人口（不是节点数！）？
1）该图用于表示基础设施状态，这与手头的问题无关。
2）圆本身受大小（半径）的限制。基本上，我正在尝试模拟核打击。
是否有开箱即用的算法？
加上R你要放置的圆的半径，N城市的数量，Pi第i个城市的人口，我们用这个一键观察:
An optimal circle can always be moved slightly so that it still covers the same cities but now touches two cities.
下图说明了这一点：虚线圆是最优的，可以稍微移动到恰好经过2个点的也是最优的圆
<head>
<title>Untitled Diagram</title>
</head>
<body style="background-color:#ffffff;">
<div class="mxgraph" style="position:relative;overflow:auto;width:100%;">
<div style="width:1px;height:1px;overflow:hidden;">1ZfNjtowEMefhjuJw9expdv2UqkSh7ZHb2ISa50YOWaBffod45kEhyDtIaQLSCj+2x6PfzNjnAlbl8cfhu+KXzoTahJPs+OEfZvE8WKVwK8TTl6YL6ZeyI3MvBS1wka+CRRp2F5mog4GWq2VlbtQTHVVidQGGjdGH8JhW63CVXc8pxVbYZNyda3+kZktvLqM563+U8i8oJWj+cr3PPP0JTd6X+F6k5htzx/fXXKyhRutC57pQyAdp2iUoc0TCQkKO14Fbr5pXQaCEXWDFK1uJfqK7WdtMmG8RJqS1cslOPYEITZaw0z3VB7XQrkwUwj9tO83ehuGRlTB2rcmQJeb8MrVHn1HRvZEcYEJkALQ+HoopBWbHU9dzwGSELTClgpaETyiKWGswJzscafdJOSx0KWw5uQCgO5QMmIOR5TDhzYjohlqxWU2kMgRZt7YbncPDwigHwYbEMZWKrXWSrtwV7pyMzJeF8ItNRQs1oFFDEaBNfsArCr74g4GaKWK17VMQ0awT3P6Cw0oNt/4Rz1HaZsOeCa9B6HIro6VDkDwSe/NOU5tkC03ucBRZ8+vMV9g7KNImhGKW/kaOtFHFlf4rSW410SRdVI+oaiSCe88zros5Y6hxiE0FC87hvyWrwydA91s+0OxxyN58EKBk3t6/g5UIHR6UIGsegqkrz4GKI/FYyBiM6xjShqG7REQLR8ki6iOKIvm4yHCy8ejIYrn4xUa2fj0lUY3vv/BCL399HmUdBgl45VaNORV+I6Mklt/82MwutcNeWBG0VUe3Y0RNNu3NX+Vat/O2dM7</div>
</div>
<script type="text/javascript" src="https://www.draw.io/js/embed-static.min.js"></script>
</body>
所以算法如下：
Iterate over all pairs of points at distance less than R.
For each pair, compute the two circles of radius R that go through them.
For each circle, compute the total population within by computing how many cities are contained inside.
这里是我所说的圆圈 the two circles of radius R that go through them :
<html>
<head>
<title>Untitled Diagram</title>
</head>
<body style="background-color:#ffffff;">
<div class="mxgraph" style="position:relative;overflow:auto;width:100%;">
<div style="width:1px;height:1px;overflow:hidden;">1ZXPkuIgEIefJvckzPjnOo67e9mThzljIIGS0CmCm8Snl0iTiKM3Z2pWqyz61zTdfN2FCdnU/W9DG/EXGFdJnrI+Ie9Jni/XL+53FAYvLJapFyojmZeyWdjJE0cxbDtKxttoowVQVjaxWIDWvLCRRo2BLt5WgoqzNrQKGWdhV1D1Wf2QzAqvrvLFrP/hshIhc7ZYe8+eFofKwFFjviQn5eXj3TUNZ+FFW0EZdJHUp96cYAwokHQqS0dlngDqSDC8nZDiIaXEWtHeg2HcYCbUlNSHa3Bk61psAFzkuKr7DVdjm0MLfdivB96pWMN1lPthwKuP+EfVEYtHSHYIjXERbgac8dYJafmuocXo6dwUOk3YWjkrc8tSKrUBBf6KJL18nY4puLEch/VOnfPt3YBzqLk1w9gZxEVCY7AvYbi7eVRC78T1lKBGkXE1nTxDcQvk8oARTuBPZ0TSG0brb2S0eiIjRlvBx4NvgWnQY/gz5inHxyOwSrHeiNVdWM+ghcn/G1oZhgRa4en9ClrOnN+/i+/q/45szw==</div>
</div>
<script type="text/javascript" src="https://www.draw.io/js/embed-static.min.js"></script>
</body>
</html>
这个简单的实现产生了一个 O(n^3) 算法（有 O(n^2) 对点，计算一个圆内的总人口需要时间 O(n)检查每个城市是否在里面）。
如果这种复杂性还不够好，您将需要尝试更复杂的东西。想到的一些改进以前解决方案的东西是：根据 x、y、任意方向对城市进行排序 and/or 它们的组合（你可以使用它测试更少的点对，也可以快速限制什么城市可能包含在您的圈子中），并将城市存储在四叉树中。围绕每个城市画圈，构建一个对应的组合地图也可以（不知道这个复杂度，确实很复杂。。。）.
我有一个图表，其中节点代表城市（City 对象将人口和坐标作为字段），边代表它们之间的距离。如何计算圆形轮廓的中心，使其覆盖最多的人口（不是节点数！）？ 1）该图用于表示基础设施状态，这与手头的问题无关。 2）圆本身受大小（半径）的限制。基本上，我正在尝试模拟核打击。
是否有开箱即用的算法？
加上R你要放置的圆的半径，N城市的数量，Pi第i个城市的人口，我们用这个一键观察:
An optimal circle can always be moved slightly so that it still covers the same cities but now touches two cities.
下图说明了这一点：虚线圆是最优的，可以稍微移动到恰好经过2个点的也是最优的圆
<head>
<title>Untitled Diagram</title>
</head>
<body style="background-color:#ffffff;">
<div class="mxgraph" style="position:relative;overflow:auto;width:100%;">
<div style="width:1px;height:1px;overflow:hidden;">1ZfNjtowEMefhjuJw9expdv2UqkSh7ZHb2ISa50YOWaBffod45kEhyDtIaQLSCj+2x6PfzNjnAlbl8cfhu+KXzoTahJPs+OEfZvE8WKVwK8TTl6YL6ZeyI3MvBS1wka+CRRp2F5mog4GWq2VlbtQTHVVidQGGjdGH8JhW63CVXc8pxVbYZNyda3+kZktvLqM563+U8i8oJWj+cr3PPP0JTd6X+F6k5htzx/fXXKyhRutC57pQyAdp2iUoc0TCQkKO14Fbr5pXQaCEXWDFK1uJfqK7WdtMmG8RJqS1cslOPYEITZaw0z3VB7XQrkwUwj9tO83ehuGRlTB2rcmQJeb8MrVHn1HRvZEcYEJkALQ+HoopBWbHU9dzwGSELTClgpaETyiKWGswJzscafdJOSx0KWw5uQCgO5QMmIOR5TDhzYjohlqxWU2kMgRZt7YbncPDwigHwYbEMZWKrXWSrtwV7pyMzJeF8ItNRQs1oFFDEaBNfsArCr74g4GaKWK17VMQ0awT3P6Cw0oNt/4Rz1HaZsOeCa9B6HIro6VDkDwSe/NOU5tkC03ucBRZ8+vMV9g7KNImhGKW/kaOtFHFlf4rSW410SRdVI+oaiSCe88zros5Y6hxiE0FC87hvyWrwydA91s+0OxxyN58EKBk3t6/g5UIHR6UIGsegqkrz4GKI/FYyBiM6xjShqG7REQLR8ki6iOKIvm4yHCy8ejIYrn4xUa2fj0lUY3vv/BCL399HmUdBgl45VaNORV+I6Mklt/82MwutcNeWBG0VUe3Y0RNNu3NX+Vat/O2dM7</div>
</div>
<script type="text/javascript" src="https://www.draw.io/js/embed-static.min.js"></script>
</body>
所以算法如下：
Iterate over all pairs of points at distance less than R.
For each pair, compute the two circles of radius R that go through them.
For each circle, compute the total population within by computing how many cities are contained inside.
这里是我所说的圆圈 the two circles of radius R that go through them :
<html>
<head>
<title>Untitled Diagram</title>
</head>
<body style="background-color:#ffffff;">
<div class="mxgraph" style="position:relative;overflow:auto;width:100%;">
<div style="width:1px;height:1px;overflow:hidden;">1ZXPkuIgEIefJvckzPjnOo67e9mThzljIIGS0CmCm8Snl0iTiKM3Z2pWqyz61zTdfN2FCdnU/W9DG/EXGFdJnrI+Ie9Jni/XL+53FAYvLJapFyojmZeyWdjJE0cxbDtKxttoowVQVjaxWIDWvLCRRo2BLt5WgoqzNrQKGWdhV1D1Wf2QzAqvrvLFrP/hshIhc7ZYe8+eFofKwFFjviQn5eXj3TUNZ+FFW0EZdJHUp96cYAwokHQqS0dlngDqSDC8nZDiIaXEWtHeg2HcYCbUlNSHa3Bk61psAFzkuKr7DVdjm0MLfdivB96pWMN1lPthwKuP+EfVEYtHSHYIjXERbgac8dYJafmuocXo6dwUOk3YWjkrc8tSKrUBBf6KJL18nY4puLEch/VOnfPt3YBzqLk1w9gZxEVCY7AvYbi7eVRC78T1lKBGkXE1nTxDcQvk8oARTuBPZ0TSG0brb2S0eiIjRlvBx4NvgWnQY/gz5inHxyOwSrHeiNVdWM+ghcn/G1oZhgRa4en9ClrOnN+/i+/q/45szw==</div>
</div>
<script type="text/javascript" src="https://www.draw.io/js/embed-static.min.js"></script>
</body>
</html>
这个简单的实现产生了一个 O(n^3) 算法（有 O(n^2) 对点，计算一个圆内的总人口需要时间 O(n)检查每个城市是否在里面）。
如果这种复杂性还不够好，您将需要尝试更复杂的东西。想到的一些改进以前解决方案的东西是：根据 x、y、任意方向对城市进行排序 and/or 它们的组合（你可以使用它测试更少的点对，也可以快速限制什么城市可能包含在您的圈子中），并将城市存储在四叉树中。围绕每个城市画圈，构建一个对应的组合地图也可以（不知道这个复杂度，确实很复杂。。。）.