29
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do you know of a fast algorithm for the worst case? \$\endgroup\$ – xnor Aug 12 '15 at 21:28
  • 3
    \$\begingroup\$ 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). \$\endgroup\$ – Martin Ender Aug 12 '15 at 21:35
  • \$\begingroup\$ @MartinBüttner Sadly, I can not generate this test case as I do not have a working implementation myself. The problem is rather tricky :) \$\endgroup\$ – orlp Aug 12 '15 at 21:45
  • \$\begingroup\$ @xnor A couple examples can be found here. \$\endgroup\$ – orlp Aug 12 '15 at 21:48
  • \$\begingroup\$ "rounded to no less than 2 digits after the decimal point"? \$\endgroup\$ – DavidC Aug 16 '15 at 21:49
12
+50
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ +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... \$\endgroup\$ – jrich Aug 25 '15 at 18:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ricochet1k Aug 25 '15 at 19:31
  • 2
    \$\begingroup\$ There's an explanation for you @Lembik \$\endgroup\$ – ricochet1k Aug 27 '15 at 13:26
  • 1
    \$\begingroup\$ You seem to have beaten the O(n^3) record mentioned in the comments of the linked SO question! \$\endgroup\$ – user9206 Aug 27 '15 at 14:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ricochet1k Aug 28 '15 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.