Order-k alpha-hulls and alpha-shapes
We introduce order-k alpha-hulls and alpha-shapes - generalizations of alpha-hulls and alpha-shapes. Being also a generalization of k-hull (known in statistics as "k-depth contour"), order-k alpha-hull provides a link between shape reconstruction and statistical depth. As a generalization of alpha-hull, order-k alpha-hull gives a robust shape estimation by ignoring locally up to k outliers in a point set. Order-k alpha-shape produces an "inner" shape of the set, with the amount of "digging" into the points controlled by k. As a generalization of k-hull, order-k alpha-hull is capable of determining "deep" points amidst samples from a multimodal distribution: it correctly identifies points which lie outside clusters of samples. The order-k alpha-hulls and alpha-shapes are related to order-k Voronoi diagrams in the same way in which alpha-hulls and alpha-shapes are related to Voronoi diagrams. This implies that order-k alpha-hull and alpha-shape can be readily built from order-k Voronoi diagram, and that the number of different order-k alpha-shapes for all possible values of a is proportional to the complexity of order-k Voronoi diagram. (C) 2013 Elsevier BM. All rights reserved.
shape reconstruction statistical depth computational geometry