# Find the area of the largest convex polygon

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.

• Do you know of a fast algorithm for the worst case?
– xnor
Aug 12, 2015 at 21:28
• If you want to enforce a time limit on 100 vertices, you should probably include at least one such test case (ideally several, e.g. one where all 100 vertices are part of the solution, one where 99 are, and one where only 10 are). Aug 12, 2015 at 21:35
• @MartinBüttner Sadly, I can not generate this test case as I do not have a working implementation myself. The problem is rather tricky :)
– orlp
Aug 12, 2015 at 21:45
• @xnor A couple examples can be found here.
– orlp
Aug 12, 2015 at 21:48
• "rounded to no less than 2 digits after the decimal point"? Aug 16, 2015 at 21:49

# 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,y:p}));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);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,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&&!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,y:p}});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);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,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&&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.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.

• +1, this is an amazing answer. You might be able to replace === and !== with == and !=, but I couldn't be sure without understanding your code... Aug 25, 2015 at 18:19
• Thanks! Those particular === and !== are comparing objects, so nope, sadly. It used to compare indices, but (x,i)=>p.i==i (13 chars) is quite a bit longer than x=>p===x (8 chars) even after optimization. Aug 25, 2015 at 19:31
• There's an explanation for you @Lembik Aug 27, 2015 at 13:26
• You seem to have beaten the O(n^3) record mentioned in the comments of the linked SO question!
– user9206
Aug 27, 2015 at 14:04
• Alright, I'm getting to where I don't believe it is possible that this runs in less than O(n^3). I'm very new to algorithmic complexity. Aug 28, 2015 at 7:31