Convex Bulkhead

We all know what a ConvexHull? is, and that clever people have worked out how to compute them efficiently.

I'm going to define a 'convex bulkhead' as a sort of internal version of a convex hull. Like a convex hull, it's a convex polygon drawn on a set of points, such that all the vertices are points from the set; however, rather than being the smallest such polygon that has all the points inside it, it's the largest such polygon that has all the points outside it.

Let's say your point set is all the points on TheEarth? which are on a continental landmass. The convex bulkhead would then be most of the South Pacific (or something). If you were to take the tube and railway stations of inner London, you might well find that the bulkhead was a large chunk of Walworth (see http://www.openstreetmap.org/?lat=51.4848&lon=-0.0853&zoom=14&layers=B0T for a map). It's actually this latter application i'm interested in - make a list of the coordinates of every railway, underground and tram station in London, and find the 'rail deserts', the areas most poorly served by the fast, efficient kind of public transport that comes on rails.

So, given a point set, how do i compute the ConvexBulkhead?

Extra credit: compute all the convex point-free regions within the point set, or the biggest M of them, or all the ones over a given size. Now do this without the regions overlapping. This last problem is almost certainly ill-defined.

My gut feeling is that this is related to the DelaunayTriangulation and the InCircle? of a polygon (see http://en.wikipedia.org/wiki/Incircle_and_excircles_of_a_triangle for info about that).

-- TomAnderson

Best idea so far is as follows. Firstly, guess that the bulkhead will be made of triangles of the DelaunayTriangulation, so compute that. Then do an exhaustive BranchAndBound search, picking a starting triangle and trying to grow a polygon outwards from it by adding neighbouring triangles while maintaining convexity. Use backtracking to exhaustively try every combination. Report the biggest one found. -- ta