Modifying a convex hull to exclude unwanted points

Question

Hi folks,

In my C#-Silverlight 3 program, I have a set of points. Those points can be of a different color, green, red or blue. Then I create a convex hull for the different points: A hull for green, a hull for red and a hull for blue. Now it can happen, that within the hull of each color are points from another color, like red points within the green hull.

Are there any algorithms to modify the hull, so that those other-colored points would be excluded from the hull (which wouldn't be convex anymore at this point)?

Thanks in advance, Frank

Answer 1

Translate to classic travelling salesman problem.

Use points that generates this hull and add the other points that you want them to exclude. Now find shotrest path over this points and you have this new hull