Multi-region Delaunay complex segmentation

We focus on the problem of segmenting scattered point data into multiple regions in a single segmentation pass. To solve this problem, we begin with a set of potential boundary points and use a Delaunay triangulation to complete the boundaries. We then use information from the triangulation and its dual Voronoi complex to determine for each face whether it resembles a boundary or interior face, allowing a user to choose a specific segmentation by keeping only faces where our parameter is above a threshold. The resulting algorithm has time complexity in O(nd)O(nd), where n is the number of Delaunay simplices.

► Segments scattered point data into multiple regions in a single pass. ► Segmentations of any number of regions without topological restrictions. ► Provides the user with a set of possible segmentations from which to choose. ► Time complexity in O(nd)O(nd), where n is the number of Delaunay simplices. ► Evaluated for both analytic and real-world data sets.