识别高维点的凹包

Question

我有一组更高维度（30d 到 100d）的点（簇）。我需要以有效的方式识别这些点的凹包。 有没有办法得到这些点集的精确凹包或至少近似凹包？ 此外，如果我们有一组点被识别为边界点，有没有办法验证这些点是否真的是边界点？

Answer 1

在100d内，几乎所有的点都会在凸包上

请记住，2d 的矩形有 4 个角，但 100d 的矩形有 2^100 个角。

作为一个非常粗略的近似值，沿每个轴取最小值和最大值。如果它是唯一的，则点在船体上。对于额外的点，您可以采样一些随机投影。

但同样，预期的行为是几乎每个点都在船体上，因为它是某些线性特征组合中最小或最大的。