5

在 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（维度）中确定多项式时间内的最大圆/矩形。

谢谢你。

4

1 回答 1

1

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

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

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

于 2013-07-13T10:05:40.550 回答