TY - GEN
T1 - Dimension detection via slivers
AU - Cheng, Siu Wing
AU - Chiu, Man Kwun
PY - 2009
Y1 - 2009
N2 - We present a novel approach to estimate the dimension m of an unknown manifold M ⊂ ℝd 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.
AB - We present a novel approach to estimate the dimension m of an unknown manifold M ⊂ ℝd 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.
UR - https://openalex.org/W4250483685
UR - https://www.scopus.com/pages/publications/70349152159
U2 - 10.1137/1.9781611973068.109
DO - 10.1137/1.9781611973068.109
M3 - Conference Paper published in a book
SN - 9780898716801
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1001
EP - 1010
BT - Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
PB - Association for Computing Machinery (ACM)
T2 - 20th Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 4 January 2009 through 6 January 2009
ER -