Minimum Convex Hull algorithm

[mattrdowney]

Concept: take a given point in a point cloud and find the minimum number of points that produce a convex hull encapsulating the object (ties go to minimum volume). Essentially this is finding the nearest neighbors that produce an adjacency graph.

[mattrdowney]

I feel like my prior description is inaccurate, since a triangle in 2D would always be the solution.

[mattrdowney]

Rough algorithm: start at point "origin". Find closest point and create a convex hull going from origin to closest point. for rest of points in non-decreasing (ascending) distances: if convex hull does not include origin break (in 2D) get "left" and "right" point in convex hull (relative) if dot product of current point and "left"/"right" are both less relative to the origin (after normalization) expand convex hull to include point

I know this algorithm is broken, partially because a point with a circle of points around it should return the circle of points (this algorithm has an order dependency, which might be fixed by incorporating an epsilon).

[mattrdowney]

I think another way of describing my goal for this algorithm is:

Initialize an adjacency graph For each point (as long as a point was added in last loop): if point already has a complete convex hull continue find next closest point not already included as a link in graph and create a connection so long as the dot product isn't greater than any adjacent point

[mattrdowney]

Notably, you can imagine going through the closest points in order (closest to furthest) and striking out items with a dot product greater than 1 relative to any previous convex hull point. After that process is done, find the (inverse? - think a minimum rubber band surrounding the points remaining) convex hull of those points that remain (often this would not be different).

[mattrdowney]

This whole process feels very similar to a "skyline" operator.