如何确定实体是否适合O(N ^ 2)中给定的盒子？

Question

我正在寻找一种算法,让我可以确定一个实体对象是否适合具有给定尺寸的盒子(矩形棱镜).可以旋转和平移固体以适合盒子内部.

我已经有了解决这个问题的方法:

1. 计算实体的最小边界框(已知算法).
2. 确定最小边界框是否适合另一个框(简单).

(编辑:这不是一个有效的解决方案)

这有效,但我正在寻找更有效的解决方案.最小边界框算法在O(n ^ 3)时间内运行,其中n是顶点数.我希望有一个O(n ^ 2)算法.

请注意,除了"实体对象"之外,我也可以询问形成实体凸包的点集是否适合框内.

Answer 1

您可能想看一下这篇论文。它给出了一种算法，可以在 O(n log n + 1/epsilon^3) 时间内计算 3D 最小边界框的 1+epsilon 近似值。