Incising balls

A local intrinsic dimensionality estimator that does not explicitly require a neighbourhood size value is the incising balls method [22], The basic premise of the algorithm is to use a set of balls that incise the manifold, with each of these incising balls containing a set number of data points and a radius. The intrinsic dimensionality of the dataset can then be estimated by evaluating the polynomial relationship of the radius of a ball and the number of data points within the ball [22]. 

The basic incising balls algorithm contains three main steps ... 

A set of m incising balls are then formed with radius... 

The incising balls method is more robust at dealing with high-dimensional data than the MLE [21] however the computational cost is higher. The overall complexity of the incising balls method is 0 n ) which can be reduced to 0(nL) if an approximation method is used whereby the distances between n and L landmark points is used in Step 1. 

Fan, M., Qiao, H., Zhang, B. Intrinsic dimension estimation of manifolds by incising balls. Pattern Recognition 42, 780-787 (2009)... 

---