algorithm - 如何确定一个实体是否适合 O(N^2) 中的给定框？

Question

我正在寻找一种算法，可以让我确定一个固体物体是否可以放入具有给定尺寸的盒子(矩形棱柱)内。实体可以旋转和平移以适合盒子。

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

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

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

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

请注意，除了“实体对象”之外，我还不如问构成实体凸包的点集是否适合盒子。

Answer 1

您可能想看看 this paper .它给出了一种算法，而不是在 O(n log n + 1/epsilon^3) 时间内计算 3D 最小边界框的 1+epsilon 近似值。