How do I find the most complex convex polygon enclosing a set of points?

Question

I have a list of (about 200-300) 2d points. I know needs to find the polygon that encloses all of them. The polygon has to be convex, and it should be as complex as possible (i.e. not a rectangular bounding box). It should find this in as low as possible time, but there are no restrictions on memory.

You may answer in pseudocode or any language you want to use.

Answer 1

Take a look at Graham's Algorithm.

Answer 2

Sounds like you're looking for a convex hull algorithm? It's been more than a decade since I was taught about these, but the name Graham Scan sticks in my mind and would probably be where I'd start.

Answer 3

If it is a real world problem - as in, not an academic one - there's never really a reason to solve such a generic problem yourself.

Answer 4

Qhull is good software for computing 2D convex hulls.