algorithm - 将平面上的点组合成 3 个骰子

我有一个 3（6 面）骰子卷的（自上而下）图像，从中提取了点的坐标，剩下 3..18 点。

我怎样才能找到掷在骰子上的东西，或者换句话说，哪些点组合在一起形成一个骰子？

到目前为止，我已经将其简化为找到 3 个圆的问题，这样每个点都恰好位于一个圆内，并且最大圆的大小被最小化。

我已经想到了两种可能的方法，但两者都只是太慢了。

方法 1：
找到所有可能的不相交点集三元组和每个点集的最小边界圆。如果一个圆包含的点不是其集合中的点，或者一个圆大于已找到的最佳解决方案中的最大圆，则丢弃任何解决方案。

方法 2：找到所有可能的圆三元组（由 1-3 个点定义）。丢弃任何包含包含超过 6 个点的圆、其他圆中已有点、大于已找到的最佳解决方案中最大圆的圆或未包围每个点的解决方案的任何解决方案。

有没有更有效的算法来解决这个问题，因为我只设法想到了大多数蛮力解决方案？我需要大约 1 秒的最坏情况时间，理想情况下平均时间可达 10 毫秒。

标签： algorithmcomputational-geometry

在 18 点的最坏情况下，最多有

>>> sum(math.comb(18, i) for i in range(1, 7))
31179

1 到 6 个点之间的可能子集。丢弃所有这些最小的封闭圆（使用Emo Welzl 的随机算法）包围一个不在子集中的点。使用Sauer-Shelah 引理和磁盘的 VC 维数为 3 的事实，我们观察到剩余子集的数量最多为

>>> sum(math.comb(18, i) for i in range(4))
988

（编辑：实际上我们可以尝试由点的三元组生成的磁盘、由点对生成的磁盘和单个点生成的磁盘。）现在我们寻找三个成对的不相交子集，它们的并集就是一切。这可以通过按位图索引子集、循环子集对并测试 1）这些子集是否不相交 2）它们的并集的补集是否也是子集来有效地完成。

如果您使用的是体面的编译器，我很确定这可以在 10 毫秒的最坏情况下运行。