Find the area of the largest convex polygon

Question

Given a list of integer coordinates, find the area of the biggest convex polygon you can construct from the list such that -

• every vertex is in the list
• no element of the list is contained within the polygon.

Example:

(0, 0) (8, 0) (0, 1) (3, 1) (7, 1) (1, 2) (5, 2) (9, 2) (2, 3) (5, 3) (7, 3) (3, 4) (5, 5) (11, 5)

Visualized:

o       o
o  o   o
 o   o   o
  o  o o
   o
     o     o

The biggest convex polygon you can make from this is this:

o     
o  o  
 o   o
  o  o
   o
     o

With an area of 12.

---

You may take the list of coordinates in any reasonable format, and should output (in an appropriate way for your language of choice) the area of the largest convex polygon, rounded to no less than 2 digits after the decimal point.

Additionally, you must employ some sort of algorithm, and not simply brute force all subsets of the points. To enforce this, your program must solve a list of 50 vertices in under a minute on a modern PC.

Shortest code in bytes wins.

Answer 1

Javascript ES6, 738 bytes

((V,C,L,r,k,n,A,G,F,e,i,j,q)=>p=>{p=p.map((p,i)=>({i:i,x:p[0],y:p[1]}));A=(f,p,a,b,v,i)=>{for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))return 1};G=(p,i,a)=>{for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=(p,s,l,f,a,b,v)=>(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A((a,b)=>C(a,b)?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b),p,a,b)?0:(p=(v=V(a,b),p[k](x=>C(v,V(a,x))>=0)),A((a,b)=>C(a,b)>0,p,b,f)?0:(p.map(q=>F(p[k](r=>q!==r),[...s,q])),s[2]&&!p[n]&&!e[b.i][f.i]?G(s):0)));e=p.map(x=>p.map(y=>x===y));for(i=p[n];i--;){for(j=i;j--;){q=p[k]((p,x)=>x-i&&x-j);F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)})((a,b)=>({x:b.x-a.x,y:b.y-a.y}),(a,b)=>a.x*b.y-a.y*b.x,v=>v.x*v.x+v.y*v.y,0,'filter','length')

Here's an ES5 or less version that should work in most browsers and node without tweaking: 827 bytes

eval("(%V,C,L,r,k,n,A,G,F,e,i,j,q){@%p){p=p.map(%p,i){@{i:i,x:p[0],y:p[1]}});A=%f,p,a,b,v,i){for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))@1};G=%p,i,a){for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=%p,s,l,f,a,b,v){@(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A(%a,b){@C(a,b)!=0?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b)},p,a,b)?0:(p=(v=V(a,b),p[k](%x){@C(v,V(a,x))>=0})),A(%a,b){@C(a,b)>0},p,b,f)?0:(p.forEach(%q){@F(p[k](%r){@q!==r}),s.concat([q]))}),s[2]&&p[n]==0&&!e[b.i][f.i]?G(s):0)))};e=p.map(%x,i){@p.map(%y,j){@i==j})});for(i=p[n];i--;){for(j=i;j--;){q=p[k](%p,x){@x!=i&&x!=j});F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)}})(%a,b){@{x:b.x-a.x,y:b.y-a.y}},%a,b){@a.x*b.y-a.y*b.x},%v){@v.x*v.x+v.y*v.y},0,'filter','length')".replace(/%/g,'function(').replace(/@/g,'return '))

Code returns an anonymous function. As a parameter, it takes an array of points, like [[0,1],[2,3],[4,5]]. To use it you can place var f= before it, or if you want to use it from the command line, add (process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(','))) to the end, and call it like node convpol.js '(1,2)(3,4)(5,6)'

Thanks for the challenge! As there is no reference implementation, I can't prove this is correct, but it is consistent at least for permutations of the point list. I almost didn't think this was going to work, as versions with debugging code, even disabled, were way too slow with exponential time increase. I decided to golf it anyway, and was pleased to see that it dropped down to under 2 seconds for 50 points on my machine. It can calculate approximately 130 points in 1 minute.

The algorithm is similar to the Graham scan, except that it has to search for empty convex hulls everywhere.

Explanation

Here's a high-level overview of how the algorithm works. The meat of this algorithm is just searching for counter-clockwise convex loops that don't enclose a point. The procedure is something like this:

1. Start with a pair of points, and a list of all other points.
2. If the current pair of points goes exactly through any point in the list, stop.
3. Filter out all points clockwise of the current pair, since they would make the polygon concave.
4. For all points left, do the following:
   1. If a line from this point to the first point of the chain goes through or encloses any points counter-clockwise, skip this point, since any polygons would enclose the point.
   2. Add this point to the chain, recurse from step 1 with the current chain and list of points.
5. If there were no points left, and the chain has at least 3 points, this is a valid convex polygon. Remember the largest area of these polygons.

Also, as an optimization, we record the initial pair of the chain as checked, so any searches afterwards upon seeing this pair anywhere in the chain can immediately stop searching, since the largest polygon with this pair has already been found.

This algorithm should never find a polygon twice, and I've experimentally verified this.