将点集拆分，算法

Question

我正在备考考试，但是我遇到了一个问题：

我们有一个包含n个点（n < 1000）和一个整数d的集合。任务是创建两个不相交的点集A1和A2（它们的并集是给定的n个点），使得从Ai中的每一对点（i = 1或2）之间的欧氏距离小于或等于d。如果无法完成，则打印-1。

例如，输入为：

d = 3 和点集：

(5,3), (1,1), (4,2), (1,3), (5,2), (2,3), (5,1)

我们可以创建：

A1 = {(2,3), (1,3), (1,1)}

A2 = {(5,3), (4,2), (5,2), (5,1)}

因为A1和A2中的每一对点都足够接近。

我真的想知道如何解决这个问题，但是我不知道从哪里开始。由于n很小，算法甚至可以是O(n^2 log n)，但我不知道如何开始。我想也许可以先计算每对点之间的距离，然后选择距离最远的两个点，并将它们放在不同的集合中（如果它们的距离大于d）。然后重复此步骤，但问题是如何决定下一个点可以合法地放置在哪里。有人能帮忙设计这个算法吗？

- xan

---

k-means无法保证收敛到最优解。然而，更好的算法起始方式k-means ++有很大的机会：http://en.wikipedia.org/wiki/K-means%2B%2B - Andrew Mao

Answer 1

考虑一个简单图，有n个节点（对应n个点）。两个节点相连，如果它们之间的距离大于d。

如果可以创建两个不相交的集合，我们必须有一个二分图（如果某些节点与其他节点没有连接，则可以将它们放入任何一个集合）。

因此，我们只需要测试这个简单图的二分性：

http://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness

- Loïc Février

Answer 2

想象一个数组，顶部是所有点，侧面是所有点。

如果定义单元格的左侧和顶部两个点之间的距离大于d，则在任何单元格中填入零；如果这两个点之间的距离小于d，则填入一。

       (5,3), (1,1), (4,2), (1,3), (5,2), (2,3), (5,1)
(5,3),          0      1      0      1      1      1
(1,1),   0             0      1      0      1      0
(4,2),   1      0             0      1      1      1
(1,3),   0      1      0             0      1      0
(5,2),   1      0      1      0             0      1
(2,3),   1      1      1      1      0             0
(5,1)    1      0      1      0      1      0

（注意：您必须填写每个三角形，将其中的0和1翻转。）

忽略对角线。请注意右上角的三角形部分。

跳过第0列。

从第1列开始，如果它在顶部行中没有1，则将其与右侧具有顶部行中1的另一列交换。然后也要交换相同的行以保持对角线为空白。（如果没有，则没有解决方案。）[例如：交换第2列和第3列以及第2行和第3行]请注意，此行的选择可能成为优化因素。

移动到下一列，如果它在顶部行中没有1，则与右侧具有1的列交换并交换相应的行。如果没有，则尝试将其与下面的行交换，该行在该列中具有1，并进行相应的列操作。如果在对角线以下，则应忽略其下面的行。

我们正在收集位于三角形左上角的具有1的点。这些点可以全部放入其中一个集合中。

这是我在脑海中迷失的地方，但你必须从三角形的右下角开始类似的过程，并收集将在另一个集合中的点。交换行和相应的列以在三角形的右下角收集1。

一旦您交换了足够的行，可以在右上角形成一个矩形--一个真正的矩形，没有左下角被切掉--并且该矩形包含所有的0，您就有了一个解决方案。如果您无法做到这一点，则没有解决方案。

将三角形中具有1的最低行与具有1的最右列进行比较，并找到它们相遇的单元格。该单元格必须在三角形中才能存在解决方案。

（我留给您一个很大的“待办事项”，找出如何交错交换行和列以清除三角形的左上角和右下角的0。也许在这里的讨论可以解决如何使其工作。或者发现它不起作用。）

- Lee Meador

Answer 3

从距离矩阵开始似乎是个好主意。然后在这个距离矩阵中选择每个大于d的条目。这个条目意味着相应的点必须在不同的集合中。

从两个空集合开始，迭代所有相关的条目（> d）。

如果集合为空，请将这两个点放入它们。否则有三种选择：

1. 如果清楚知道点属于哪个集合，请将它们放入该集合中（也就是说，插入点会保留最大距离标准，这可以从距离矩阵中获得）。
2. 如果点不能插入到任何一个集合中，则问题无法解决。
3. 如果两个点都可能属于两个集合，则我们有一个问题。我建议开始一对新的点集，并将这些点放入其中。然后，如果随后的点对再次不明确，请检查第二个点集对。如果仍然不清楚，请检查第三个点集对等等。如果一对点被插入到先前的集合中，请检查以下集合，以确定点是否现在已经清晰。最后，您将拥有一组点集对的列表，可以根据需要合并。

---

我刚想到了第二种方法，它与第一种方法类似，但应该会更快一些。

我们同样从距离矩阵开始。

除了这两个集合，我们还要维护一个新添加条目的堆栈、队列或其他数据结构。

因此，如果我们从距离矩阵中选择第一个相关条目，则这些点将被添加到两个队列中。只要其中一个队列中有条目，就执行以下操作：

从队列中删除该点并将其插入集合中。如果插入违反了最大距离标准，则问题无法解决。检查该点所在行或列的距离矩阵，并提取该行/列中的每个相关条目。将配对点添加到另一个集合的队列中（因为它必须在不同的集合中）。

如果两个队列都为空，则将下一个尚未访问的相关条目添加到队列中并重新开始。

这种算法的优点是按照它们相互影响的顺序处理点。因此，不需要超过一对集合。

- Nico Schertler