Nonconvex polygon

[d31mOZ]

Hello to all:
I am a student of a University of Computer Science, and in my project have put me a tasks and is one me is returning crazy :

Initially they gave one, that given a cloud me of points, is needed that my program gives back the convex polygon, and I already did it, with a mathematical solution, but they have put me other than it has to me throwing of the hair , he is the following one, with the same cloud of points, is needed that make "nonconvex" polygon of this cloud. I explain myself better, this application is for a medical software, the reconstruction of parts of the head, if they pay attention to the image can see an example,

For these points:


Must be something similar to this:


For example for an ear:


I must give this result (so so): (of course with more points the image its better)


I have investigated and I have not given with the solution, I do not see any mathematical algorithm that it solves this, if somebody can help me would thank for much.

Best Regard

[Krzysztof Duleba]

There are many solutions (even up to n!). How do you tell which one is the best?

[d31mOZ]

Yes, i think that, but, the problem will be apply to application medic, and the point should will be border, trying of conform an image of part of the body.

I believe that it will give me point of medical figure.

Thank, your interest of help me.