geometry - 最大的空球体或矩形

Question

在 N (~ 500) 维中，我希望找出最大的球体或矩形，使球体/矩形不包含现有的点。整个点集以轴对齐的矩形框为界(值的下限和上限)。

是否有任何已知的多项式时间方法/代码可以用来解决我的问题？

两个众所周知的算法:i)矩形内最大的空矩形( http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf )和，ii)在位置约束( http://www.cs.dartmouth.edu/reports/TR86-130.pdf )内找到最大的空圆不起作用。

虽然上述算法的复杂度是 N log N 或 N^2 log N，其中 N 是已经存在的点的数量，但复杂度也是凸包或边界多边形的顶点数量的线性函数。一个 500 维的矩形将有 2^500 个角，这使得上述技术不可行。

理想情况下，我正在寻找一种方法(它不一定是精确的)，它可以在多项式时间内以 N(点数)和 D(维度)确定最大的圆/矩形。

谢谢你。

Answer 1

一种可能的启发式解决方案是限制大矩形使其与轴对齐。在这种情况下，一个矩形最多可以有 2 * d 个点，其中每个点代表一个或多个维度的最小或最大边界。然后可以仅在 O(d) 内确定一个点是否在该矩形内。

利用这个的启发式方法是选取 2 个点，并使用它们形成一个初始边界框，然后随机添加点。如果点在框内，则缩小或拆分框。如果点在框外，请尝试将框变大。如果框缩小而不是拆分，则单次传递应该花费 O(d * N)。

通过确保两点形成的边界框内没有任何点，质量可能会有所提高。找到所有点对使得边界框内没有点可能是理想的，因为当转换为图形时，它们应该有助于以较少随机的方式扩展解决方案。动态规划可能会导致算法优于 O(d*N^3) 或 O(d*N^2) 或更好。