将平面上的点分成三个骰子

Question

我有一个（从上往下）的图像，一卷3（6面）骰子，我已经提取了点的坐标，留给我3..18点。

我怎样才能找到骰子上滚动的是什么，或者换句话说，是哪几个点组合在一起形成一个骰子呢？

到目前为止，我已经把它简化为一个求3个圆的问题，这样每个点正好位于一个圆中，最大的圆的大小被最小化。

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

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

有没有更有效的算法来解决这个问题，因为我只想出了大部分暴力的解决方案？我需要一个最坏的情况下的时间约1s，理想的平均时间高达10ms。

Answer 1

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

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

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

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

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