Efficient Method of Solving Convex Hull Related Problem

Long request, but appreciative of anyone who has a good idea. I have a large number of X-Y pairs that I need to fit a convex hull. The problem is, I need to fit a convex hull with 90% of the X-Y pairs such that the selected pairs yield the polygon with the smallest area.

For example, say we have 5 pairs: (1,1), (.1,.5), (0,0), (1,0), (3,1)

The convex hull from convhull(x,y) would give k = [1 3 4 5]. If I only wanted the convex hull that included 4 of the 5 points such that it would have the smallest polygon (area-wise), it would remove point 5 and the convex hull would be k = [1 3 4].

I have a brute force method of doing this, but it would take weeks to run. I have around 600,000 X-Y pairs. I want to remove 60,000 of them. One method is to calculate the convex hull and store the area. Then, take turns in removing each point of the convex hull (one at a time) from the X-Y pairs, recalculating the area of the new convex hull, and storing the difference between the original area and the new area. Then, permanently remove the point that showed the greatest difference in area. Repeat this 60,000 times.

Obviously this is inefficient. Does anyone have a better idea?

[Matt J]

The convex hull from convhull(x,y) would give k = [1 3 4 5].

No, it gives

>> convhull(x,y)

ans =

       1
       2
       3
       4
       5
       1

[Adam Montjoy]

I apologize for the poorly constructed example. The points should be (0,1), (.1,.5), (0,0), (1,0), (3,1).

The convex hull function would return k = [1 3 4 5 1]. The updated k when 5 is removed would be k = [1 3 4 1]. Thank you for clarifying, Matt.

[Matt J]

Sounds like a tough global minimization problem. Is there an ulterior motive for this?

[Adam Montjoy]

Yes, actually. It's a problem looking at a certain entity's location over a period of time. The question is, what is the area of the polygon that encloses 90% of the points (with the assumption being that the polygon is as small as possible).

Would you suggest a genetic algorithm?

[Matt Kindig]

Could you post your brute-force solution? Maybe we can offer some speed-ups for that approach.

Answer 1

[Matt J]

Maybe you can group the 600,000 original points into clusters. Then use the centers of the clusters to define a sparser set of points. Then run your brute force algorithm on the sparser set. Once you've found the smallest polyhedron in the sparse case, make the hypothesis that it's a good 1st-pass approximation to the dense case.

Refine the search by making the clusters smaller, each time eliminating points that are very far away from the 1st-pass polyhedron (e.g., farther away than the cluster diameter).