Order-k α-hulls and α-shapes
2014 (English)In: Information Processing Letters, ISSN 0020-0190, Vol. 114, no 1, 76-83 p.Article in journal (Refereed) PublishedText
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.
Place, publisher, year, edition, pages
2014. Vol. 114, no 1, 76-83 p.
Computational geometry;Statistical depth;Shape reconstruction
Computer Vision and Robotics (Autonomous Systems)
IdentifiersURN: urn:nbn:se:liu:diva-128026DOI: 10.1016/j.ipl.2013.07.023OAI: oai:DiVA.org:liu-128026DiVA: diva2:928737