A practical algorithm for weighted k ‐hulls

Abstract

The convex hull is a central concept in computational geometry, geometry processing, and generally for summarizing sampled data. Its descriptive power suffers significantly in the presence of noise. The k‐hull, also known as the k‐depth contour in statistics, is the intersection of all half‐spaces that contain all but k data points, i.e. it is a convex hull ignoring k points in any direction. While it is well established theoretically, the lack of a robust and efficient algorithm, especially for the 3D case, limits applications. We combine ideas of an intuitive algorithm for the 2D case with gift wrapping and improve efficiency using established spatial data structures. The clear concept also facilitates a generalization to weighted data, allowing us to ignore points whose weights sum up to at most a given tolerance. For the case of unweighted data with unknown noise characteristics, we determine a simple heuristic for estimating k to adjust to outliers in the data. We demonstrate the effectiveness of the algorithm on the examples of computing convex hulls for data with noise and for visibility determination via convex hulls.