Dimension Detection via Slivers
Siu-Wing Cheng, Man-Kwun Chiu · Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms · 2009
We present a novel approach to estimate the dimension m of an unknown manifold M ⊂ ℝ with positive reach from a set of point samples P ⊆ M. It works by analyzing the shape of simplices formed by point samples. Suppose that P is drawn from M according to a Poisson process with an unknown parameter λ. Let k be some fixed positive integer. When λ is large enough, we prove that the dimension can be correctly output in O(kd|P|1+1/k) time with probability greater than 1 − 2−-k. We experimented with a practical variant and showed that its performance is competitive with several previous methods.