列出由給定半徑的圓所包圍的所有點集

Question

我的問題是：給定平面中的N個點和數字R，列出/列舉所有點的子集，其中每個子集中的點由圓圈包圍半徑爲R.兩個子集應該是不同的，而不是彼此覆蓋。

效率可能並不重要，但算法不應該太慢。

在特殊情況下，我們可以找到最多點的K個子集嗎？近似算法可以接受。

感謝，

編輯：看來這個說法是不明確的理解。我的錯！

所以我重申我的問題如下：給定N個點和一個固定半徑爲R的圓，用圓來掃描整個空間。一次，該圈子將覆蓋點的一個子集。目標是列出可以被這種R半徑圓所覆蓋的點的所有可能子集。一個子集不能是其他子集的超集。

Answer 1

我不確定我是否明白'你不知道'的意思。如果你放棄了這一點，你所尋找的是一個Cech複雜的複雜性很高的複雜性，如果你對採樣沒有條件（採樣應該足夠稀疏且R不能太大，否則你可能有2 ^有n個點的n個子集）。您必須枚舉所有子集並檢查它們的最小包圍球半徑是否小於R.您可以將搜索縮小到所有直徑小於R的子集（例如，成對距離小於R），這對您的情況可能足夠了。

如果兩個子集的「未覆蓋」表示一個未包含在另一個子集中，則可以有許多不同的分解。其中一個值得關注的是alpha複合體，因爲它可以在維度2-3（我會建議使用CGAL來計算它，你也可以看到它對圖片意味着什麼）O（nlogn）中有效地計算。如果你的觀點是高維的，那麼你可能最終計算一個切赫綜合體。

Answer 2

不失一般性，我們可以假設所考慮的封閉圓通過至少兩個點（忽略沒有點或一點的微不足道的情況，並假設你的動機是最大化密度，所以你不關心如果省略非最大子集）。在輸入點上構建一個鄰近結構（kd-tree，cover tree等）。對於每個輸入點p，使用該結構查找所有點q，使得d（p，q）≤2R。對於每個點q，有一個或兩個圓圈在其邊界上包含p和q。通過求解一些二次方程來找到它們的中心，然後查看q的其他選擇來確定子集。