We introduce order-k α-hulls and α-shapes – generalizations of α-hulls and α-shapes. Being also a generalization of k-hull (known in statistics as “k-depth contour”), order-k α-hull provides a link between shape reconstruction and statistical depth. As a generalization of α-hull, order-k α-hull gives a robust shape estimation by ignoring locally up to k outliers in a point set. Order-kα-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 α-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 α-hulls and α-shapes are related to order-k Voronoi diagrams in the same way in which α-hulls and α-shapes are related to Voronoi diagrams. This implies that order-k α-hull and α-shape can be readily built from order-k Voronoi diagram, and that the number of different order-kα-shapes for all possible values of α is proportional to the complexity of order-k Voronoi diagram.