liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Order-k α-hulls and α-shapes
Institute for Geospheres Dynamics, Russian Academy of Sciences, Russian Federation.
Department of Computer Science, University of Helsinki, Finland.
2014 (English)In: Information Processing Letters, ISSN 0020-0190, Vol. 114, no 1, 76-83 p.Article in journal (Refereed) PublishedText
Abstract [en]

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.
Keyword [en]
Computational geometry;Statistical depth;Shape reconstruction
National Category
Computer Vision and Robotics (Autonomous Systems)
URN: urn:nbn:se:liu:diva-128026DOI: 10.1016/j.ipl.2013.07.023OAI: diva2:928737
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2016-05-25

Open Access in DiVA

No full text

Other links

Publisher's full text
Computer Vision and Robotics (Autonomous Systems)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 66 hits
ReferencesLink to record
Permanent link

Direct link