logo标签列表

用半径为r的圆覆盖n个点，最少需要多少个圆？

algorithmcomputational-geometry
23
什么是覆盖所有n个点所需的最小半径为r的圆圈数？ 输入将给出r和n，接着是n对表示n个点的x-y坐标的整数。 r是大于0的实数，n小于20。
如果一个点在圆内，则该圆覆盖了该点。 如果点与圆心之间的距离小于或等于r，则该点位于圆内。
5
这不是一个编程问题吗？你知道有一种叫做竞赛编程的东西吗？我正在尝试解决一个问题，发现我必须先解决这个子问题。你为什么认为每个人都让你替他们做家庭作业呢？ - user2040997
4
通常情况下这样的问题是可以被接受的，但是在提出问题之前先尝试解决问题通常会更有帮助。@PhillipSchmidt 这听起来像是一个编程问题。 - Bernhard Barker
1
@Dukeling 我想到了一个2^n * 2^n的解决方案，但是由于n可能为20，这不会起作用。我认为存在一个n * 2^n或n^2 * 2^n的算法，但是无法弄清楚。 - user2040997
3
SO上提出的问题旨在能够在编程上下文中回答。请参见这里。这个问题更适合在math.SO上提问。 - Phillip Schmidt
4
我会很高兴，如果你能展示一些努力，或者提供一些背景信息，以证明这不仅仅是“请帮我做作业”。 - agentp
显示剩余10条评论
9个回答
14

这可能不是最佳解决方案，但它是对其进行优化的尝试。

算法基于随机取样：

  1. 在地图上生成N个圆
  2. 去除未覆盖任何点的所有圆
  3. 按覆盖点数降序对圆进行排序
  4. 对于每个圆（已排序）- 将由圆覆盖的点标记为已覆盖。如果圆不覆盖任何新点，请从列表中删除。

这里有一些代码，您可以预览它：http://jsfiddle.net/rpr8qq4t/ 示例结果（30个点的13个圆）： 13 circles per 30 points

参数化：

  var POINTS_NUMBER = 30;
  var RADIUS = 50;
  var SAMPLE_COUNT = 400;

它可以添加一些优化（例如，有些圆可能太早从列表中排除）

编辑：

  1. 步骤1的变化带来更好的结果：为每个点生成N个圆（至少覆盖一个点的圆） 新版本：http://jsfiddle.net/nwvao72r/3/

编辑2（最终算法）

最终版本：

  1. 对于每个点，在距离该点小于R（圆的半径）的随机距离内生成N = 10个圆（确保每个圆至少有一个点属于它，每个点属于至少一个圆）
  2. 重复直到所有点都被覆盖：
    • 获取覆盖最多未覆盖点的圆。 将点标记为已覆盖。

这是最适合我的版本，您可以在此处查看：http://jsfiddle.net/nwvao72r/4/，平均每30个点使用12个圆。

enter image description here

你的算法1和2似乎不能给出最小圆。但是算法3可以。尝试调整半径和点数。干得好。JSfiddle加1分。 - Anudeep Bulla
10
我确定这个问题是NP难的，但我不打算在这里尝试证明。
如果它是NP难问题，则为了找到保证最优解，我建议采用以下方法：
1.找到所有“好”的潜在圆形位置，并记录其中包含哪些点。
2.使用这些点集解决集合覆盖问题。（这个问题是NP难的。）
好的圆形位置
对于任何距离小于2r的2个点，存在恰好两个半径为r的圆通过这些点：

2 circles through 2 points

[编辑：我的“最佳可能”圆的原始描述是错误的，尽管这不会导致问题 - 感谢评论者乔治描述了正确的思考方式。]

如果一个圆覆盖了一组最大点（意思是该圆不能重新定位以覆盖相同的点集加上至少1个），那么该圆可以滑动直到其边界恰好接触到它覆盖的两个点中的任意两个 - 比如说，通过将其向左滑动直到它接触到已经覆盖的点，然后顺时针围绕这个接触点旋转直到它接触到另一个已经覆盖的点。这个移动的圆将完全覆盖原始圆覆盖的点集。此外，我们永远不需要考虑覆盖非最大点集的圆，因为覆盖这些点和更多点的最大圆至少同样有用而且成本不高。这意味着我们只需要考虑接触两个点的圆。只要为输入中每对足够接近的点生成两个圆，我们就已经生成了所有可能需要的圆。

我们的潜在圆池最多包含每对点之间的2个圆，总共最多可能有n*(n-1)个潜在圆。(通常会更少，因为某些点对通常会相距超过2r，因此无法被半径为r的单个圆覆盖。)此外，我们还需要一个额外的圆，用于每个距离任何其他点都超过2r的点——这些圆可以放置在那些远离的点上。
集合覆盖
实际上，我们只关心每个潜在圆所覆盖的点集。因此，对于每个潜在圆，找到它覆盖的点。总体上可以使用O(n^3)时间完成，对于每个潜在圆，需要进行一次O(n)的遍历。为了稍微加快速度，如果我们发现两个不同的圆恰好覆盖相同的点集，我们只需要保留其中一个圆(即被覆盖的点集)。此外，我们可以丢弃任何被其他被覆盖点集的子集所包含的被覆盖点集——在这种情况下，选择更大的被覆盖点集总是更好的。

最后，我们有一组覆盖点集，并且我们想要找到覆盖每个点的最小子集。这就是集合覆盖问题。我不知道解决这个问题的具体算法，但分支定界法是解决这类问题的标准方法——它通常比简单的穷举回溯搜索快得多。我首先会通过先找到一个（或多个）启发式解来为搜索做好准备，希望能产生一个良好的上界，以减少分支定界搜索时间。我认为即使是这个问题的最佳算法在最坏情况下也需要指数时间，但对于n<20，我认为这将是可管理的，因为最多有19*18=342个不同的点集。

1
很好，一个简单的思考方式是假设你有一个解决方案。解决方案圆可以任意移动（仍然是有效的解决方案），只要它们包含原始点即可。因此，它们都可以移动到接触两个点，这样上述描述的集合必须包含一个解决方案。 - agentp
@george：你说得对，我目前关于“最佳可能”的解释实际上是错误的——我会编辑更新。 - j_random_hacker
8

来自Gautam K. Das等人的论文"On the Discrete Unit Disk Cover Problem":

最小几何圆盖问题。在最小几何圆盖问题中，输入由平面上的一组点组成，问题是找到一组单位圆的最小基数，使其并集覆盖这些点。与DUDC不同，圆心不受限于从给定的离散集合中选择，而可以位于平面上的任意点上。同样，这个问题是NP-hard [9]，但有PTAS解决方案[11, 12]。

参考文献:

  1. R. Fowler, M. Paterson和S. Tanimoto，“Optimal packing and covering in the plane are NP-complete”，Information Processing Letters，vol 12，pp. 133-137，1981年。
  2. G. Frederickson，“Fast algorithms for shortest paths in planar graphs, with applications”，SIAM J. on Computing，vol 16，pp. 1004-1022，1987年。
  3. T. Gonzalez，“Covering a set of points in multidimensional space”，Information Processing Letters，vol 40，pp. 181-188，1991年。
  4. D. Hochbaum和W. Maass，“Approximation schemes for covering and packing problems in image processing and VLSI”，J. ACM，vol 32，pp. 130-136，1985年。
5

平铺然后晃动

  1. 平铺：找到包含所有点的矩形。
  2. 用距离为r * sqrt(2)的圆形覆盖矩形区域。
  3. 对于每个点，计算它所在的圆以及每个圆中包含的点。
  4. 删除没有点的圆。
  5. 删除只包含多个圆中已经包含的点的圆。
  6. 重复步骤5直到没有更多的圆可删除。
  7. 晃动：针对每个圆：尝试将其移动以查看是否可以覆盖其原始点加上最大数量的新点，并执行此操作。
  8. 再次执行步骤4和5。
  9. 重复步骤7，直到晃动不再改变圆内部包含的点或时间用尽。

步骤2中，可以通过遍历每个点并计算/仅保留那些如果平铺非常稀疏，则会包含点的圆来优化平铺。

4

我意识到圆不一定要在点上居中，因此计算通过任何两个点的所有圆，包括以每个点为中心的圆。 然后找出每个圆覆盖的点，并使用贪心算法找到覆盖所有点的最小圆集，但是这可能不是最小圆集，但计算起来相对容易。

from collections import namedtuple
from itertools import product
from math import sqrt
from pprint import pprint as pp

Pt = namedtuple('Pt', 'x, y')
Cir = namedtuple('Cir', 'x, y, r')

def circles_from_p1p2r(p1, p2, r):
    'Following explanation at http://mathforum.org/library/drmath/view/53027.html'
    (x1, y1), (x2, y2) = p1, p2
    if p1 == p2:
        #raise ValueError('coincident points gives infinite number of Circles')
        return None, None
    # delta x, delta y between points
    dx, dy = x2 - x1, y2 - y1
    # dist between points
    q = sqrt(dx**2 + dy**2)
    if q > 2.0*r:
        #raise ValueError('separation of points > diameter')
        return None, None
    # halfway point
    x3, y3 = (x1+x2)/2, (y1+y2)/2
    # distance along the mirror line
    d = sqrt(r**2-(q/2)**2)
    # One answer
    c1 = Cir(x = x3 - d*dy/q,
             y = y3 + d*dx/q,
             r = abs(r))
    # The other answer
    c2 = Cir(x = x3 + d*dy/q,
             y = y3 - d*dx/q,
             r = abs(r))
    return c1, c2

def covers(c, pt):
    return (c.x - pt.x)**2 + (c.y - pt.y)**2 <= c.r**2

if __name__ == '__main__':
    for r, points in [(3, [Pt(*i) for i in [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]]),
                      (2, [Pt(*i) for i in [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]]),
                      (3, [Pt(*i) for i in [(-5, 5), (-4, 4), (3, 2), (1, -1), (-3, 2), (4, -2), (6, -6)]])]:
        n, p = len(points), points  
        # All circles between two points (which can both be the same point)
        circles = set(sum([[c1, c2]
                           for c1, c2 in [circles_from_p1p2r(p1, p2, r) for p1, p2 in product(p, p)]
                           if c1 is not None], []))
        # points covered by each circle 
        coverage = {c: {pt for pt in points if covers(c, pt)}
                    for c in circles}
        # Ignore all but one of circles covering points covered in whole by other circles
        #print('\nwas considering %i circles' % len(coverage))
        items = sorted(coverage.items(), key=lambda keyval:len(keyval[1]))
        for i, (ci, coveri) in enumerate(items):
            for j in range(i+1, len(items)):
                cj, coverj = items[j]
                if not coverj - coveri:
                    coverage[cj] = {}
        coverage = {key: val for key, val in coverage.items() if val}
        #print('Reduced to %i circles for consideration' % len(coverage))

        # Greedy coverage choice
        chosen, covered = [], set()
        while len(covered) < n:
            _, nxt_circle, nxt_cov = max((len(pts - covered), c, pts)
                                         for c, pts in coverage.items())
            delta = nxt_cov - covered
            covered |= nxt_cov
            chosen.append([nxt_circle, delta])

        # Output
        print('\n%i points' % n)
        pp(points)
        print('A minimum of circles of radius %g to cover the points (And the extra points they covered)' % r)
        pp(chosen)

三次运行的输出如下：
5 points
[Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=4, y=5), Pt(x=2, y=4), Pt(x=0, y=3)]
A minimum of circles of radius 3 to cover the points (And the extra points they covered)
[[Cir(x=2.958039891549808, y=2.5, r=3),
  {Pt(x=4, y=5), Pt(x=0, y=3), Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=2, y=4)}]]

5 points
[Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=4, y=5), Pt(x=2, y=4), Pt(x=0, y=3)]
A minimum of circles of radius 2 to cover the points (And the extra points they covered)
[[Cir(x=1.9364916731037085, y=2.5, r=2),
  {Pt(x=0, y=3), Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=2, y=4)}],
 [Cir(x=4, y=5, r=2), {Pt(x=4, y=5)}]]

7 points
[Pt(x=-5, y=5),
 Pt(x=-4, y=4),
 Pt(x=3, y=2),
 Pt(x=1, y=-1),
 Pt(x=-3, y=2),
 Pt(x=4, y=-2),
 Pt(x=6, y=-6)]
A minimum of circles of radius 3 to cover the points (And the extra points they covered)
[[Cir(x=3.9951865152835286, y=-0.8301243435223524, r=3),
  {Pt(x=3, y=2), Pt(x=1, y=-1), Pt(x=4, y=-2)}],
 [Cir(x=-2.0048134847164714, y=4.830124343522352, r=3),
  {Pt(x=-4, y=4), Pt(x=-3, y=2), Pt(x=-5, y=5)}],
 [Cir(x=6.7888543819998315, y=-3.1055728090000843, r=3), {Pt(x=6, y=-6)}]]
我不是很懂Python，但这看起来像是一个不错的启发式解决方案。加一。 - j_random_hacker
并且也感谢@j_random_hacker指出圆圈不一定要以点为中心 - 阅读规范是一门艺术，我在不断学习中。谢谢！ - Paddy3118
2

我不确定这是否正确，但如果我们不需要解的圆的确切位置，那么看起来我们可以通过查看点簇来解决这个问题：在任何一个解的圆中，任意两点之间的距离应小于或等于2*r。

算法：

1. j_random_hacker indicated that any solution-circle could be shifted so that
   two of its covered-points lay on its circumference without changing the 
   original covered-points. Since the solution-circle radius is given, for each 
   point: (a) calculate potential circle-centers using the point, radius, and 
   each other point that is at a distance of 2*r or less, (b) for each circle, 
   list the cluster of points that it could cover. Sort each cluster and, for
   each point, remove duplicate clusters. 

2. For each cluster group in 1., choose the cluster that has the greatest point-
   count, that is, the cluster that is most shared.

3. Remove duplicates and clusters that are sub-sequences of other clusters 
   from 2., and present the resulting size of 2. (perhaps together with the 
   chosen clusters) as the solution.


对于等边三角形，r=3，[(0,0),(5.196152422706632,3),(5.196152422706632,-3)] 的输出结果为：

*Main> solve
(2,[[(0.0,0.0),(5.196152422706632,3.0)],[(0.0,0.0),(5.196152422706632,-3.0)]])


Paddy3118的例子输出，r=3，[(1,3),(0,2),(4,5),(2,4),(0,3)]:

*Main> solve
(1,[[(0.0,2.0),(0.0,3.0),(1.0,3.0),(2.0,4.0),(4.0,5.0)]])


当 r=3 时，[(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6,-6)] 的输出结果为：

*Main> solve
(3,[[(-5.0,5.0),(-4.0,4.0),(-3.0,2.0)],[(1.0,-1.0),(3.0,2.0),(4.0,-2.0)],
    [(4.0,-2.0),(6.0,-6.0)]])


Haskell代码：

import Data.List (delete, nub, nubBy, isInfixOf, sort, sortBy, maximumBy)

points = [(0,0),(5.196152422706632,3),(5.196152422706632,-3)]--[(1,3),(0,2),(4,5),(2,4),(0,3)]--[(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6,-6)]
r = 3
twoR = 2*r

circleCenters (x1,y1) (x2,y2) =
  let q = sqrt $ (x2-x1)^2 + (y2-y1)^2
      (x3, y3) = ((x1+x2)/2,(y1+y2)/2)
      first = (x3 + sqrt(r^2-(q/2)^2)*(y1-y2)/q, y3 + sqrt(r^2-(q/2)^2)*(x2-x1)/q)
      second = (x3 - sqrt(r^2-(q/2)^2)*(y1-y2)/q, y3 - sqrt(r^2-(q/2)^2)*(x2-x1)/q)
  in [first,second]

isInCircle (center_x,center_y) (x,y) = (x-center_x)^2 + (y - center_y)^2 <= r^2

findClusters (px,py) = 
  nub [sort $ [(px,py)] ++ filter (isInCircle a) potentialPoints | a <- potentialCircleCenters]
    where
      potentialPoints = filter (\(x,y) -> (x-px)^2 + (y-py)^2 <= twoR^2) (delete (px,py) points)
      potentialCircleCenters = concatMap (circleCenters (px,py)) potentialPoints

solve = (length bestClusters, bestClusters) where
  clusters = map findClusters points
  uniqueClusters = nub . concat $ clusters
  bestClusterForEachPoint = map (maximumBy (\a b -> compare (length a) (length b))) clusters
  bestClusters = nub . nubBy (\a b -> isInfixOf a b) . sortBy (\a b -> compare (length b) (length a)) 
                 $ bestClusterForEachPoint
我还没有理解您的第2步和第3步，但有一个更大的问题：虽然任何由同一个圆覆盖的两个点之间的距离<= 2r，但反过来（“任何一组点都小于等于2r，从而可以被一 个单独的圆覆盖”）不幸的是并不总是成立-请参见我对M C回答中的第一个评论以获得具体示例（以及图像！）顺便说一句，如果我们通过在距离<= 2r的每对点之间放置边缘来形成图形，则您的“群集”（至少来自步骤1）是团。 - j_random_hacker
搜索孤立簇（可以在步骤<=2r中彼此绑定的点）肯定是第一步--但你仍然会面临最坏情况，即所有点都在一个簇中。 - agentp
不客气，Groovy！我似乎总是找到问题所在——请不要灰心，这些挫折会让你成为更好的程序员 :) - j_random_hacker
@j_random_hacker，一点也不，我很感激有机会学到更多，这也是我为什么要求你的反馈意见的原因。 - גלעד ברקן
@j_random_hacker 好的，我把我的“簇”修改成了从每两个足够接近的点和给定半径派生出的圆内的点 - 我认为这是根据你的观察。请看算法的第一步。 - גלעד ברקן
显示剩余7条评论
1

这是我的第一个答案，我会保留它，因为另一个答案引用了它。 但请看我的后续答案，该答案考虑了两点之间的圆而不是这种方法。 以下是用Python编写的贪心算法，可以找到a的最小值，但我不知道它是否是the最小解。

dbg = False
if not dbg:
    r, n = (int(s) for s in input('r n: ').split())
    points = p = [ tuple(int(s) for s in input('x%i y%i: ' % (i, i)).split())
                   for i in range(n) ]
else:
    r, n, points = 3, 5, [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]; p = points

# What a circle at each point can cover
coverage = { i: frozenset(j
                          for j in range(i, n)
                          if (p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2 <= r**2)
             for i in range(n)}

# Greedy coverage choice
chosen, covered = [], set()
while len(covered) < n:
    # Choose the circle at the point that can cover the most ADDITIONAL points.
    _, nxt_point, nxt_cov = max((len(pts - covered), i, pts)
                                for i, pts in coverage.items())
    covered |= nxt_cov
    chosen.append(nxt_point)
print('Cover these points:\n  %s' % '\n  '.join('%s, %s' % p[i] for i in chosen))

这里是一个示例运行：

r n: 3 5
x0 y0: 1 3
x1 y1: 0 2
x2 y2: 4 5
x3 y3: 2 4
x4 y4: 0 3
Cover these points:
  1, 3
  4, 5

注意：数据的输入/输出很简陋，但算法应该很清晰。
每次都不一定返回最优解（例如，想象一组仅有2个点的数据集，它们之间的距离为r + epsilon，其中epsilon很小--这些可以被一个圆覆盖，但是您的算法将需要2个）。尽管如此，这是一个不错的启发式方法。 - j_random_hacker
是的，我在阅读上面关于从两个点和半径绘制两个圆的文章后就知道了，并且正在进行更新。 - Paddy3118
1
如果以中心为C（cx，cy）的圆覆盖点P（px，py），则距离|CP|<r（r-半径）。因此，覆盖点P的圆心可能在圆心为P且半径为r的圆内。现在让我们画出所有以给定点为圆心且半径为r的圆。如果一些圆相交，则我们可以画一个新的圆，其圆心位于这种相交处，并覆盖相应的点。因此，对于每对输入点，我们检查圆是否相交。
假设输入点是顶点，并且交点得到它们之间的边缘。现在我们有一个已知的图形问题最小边缘覆盖http://en.wikipedia.org/wiki/Edge_cover，可以在多项式时间内解决（尽管有限制n<20，暴力方法可能是可接受的）
更新。那不是边缘覆盖。我的错误。
不幸的是，它与边缘覆盖不等价，因为一个圆可以覆盖多对点（即一个圆可以对应多条边）。此外，它们不需要以现有点为中心，而且不这样做可能更有优势（例如，三个边长等于r + epsilon的等边三角形上的3个点，其中epsilon是某个小值）。 - j_random_hacker
0
如果您在每个点上放置半径为r的n个圆，找到最大重叠的区域/点并在该区域中心放置新的半径为r的圆。我不确定这是否是解决方案的最佳方式（除了暴力方法之外），但我相信您可以用相当多的数学实现它，从而降低解决方案的运行时间复杂度。希望这有所帮助。请给予反馈。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接