San*_*ari 5 geometry computational-geometry
在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(维度)的多项式时间中最大的圆/矩形.
谢谢.
一种可能的启发式解决方案是限制大矩形，使其轴对齐。在这种情况下，矩形最多可以由 2 * d 个点界定，其中每个点表示一维或多维的边界最小值或最大值。然后只需 O(d) 即可确定一个点是否在该矩形内部。
利用这一点的启发式方法是选取 2 个点，并使用它们形成初始边界框，然后随机添加点。如果该点位于框内，则缩小或分割框。如果点在框外，请尝试使框变大。如果盒子是收缩而不是分割，单次传递应该花费 O(d * N)。
通过确保没有点位于由两点形成的边界框内，也许可以稍微提高质量。找到所有点对使得没有点位于边界框内可能是理想的，因为当转换为图形时，它们应该有助于以不太随机的方式扩展解决方案。动态编程可能会导致算法优于 O(d*N^3) 或者 O(d*N^2) 或更好。