## ICPC 2015 World Final Problem B

This the the solution to Problem B from the International Collegiate Programming Contest. The list of problems can be found here. The idea is to find the maximal area of the intersection of two moving polygons. The inputs give the initial positions of two convex polygons and the vectors giving their speed in the plane.

One idea of a solution is as follows: take a maximal time and a discretization of the interval by dividing it into parts. Iterate over the translations at times given by this discretization, compute at each step the area of the intersection of the two polygons (if there is any intersection at all), and in the end find the time for which this area is maximized. Now, even if the discretization step is large (greater than the demanded precision of ), we can conclude that is an approximation of the final time with an error smaller than . This is due to the fact that the function representing the area of the intersection has two monotonicity intervals, as a consequence of the fact that the polygons are convex. On the first interval, the intersection area is increasing, on the second one it is decreasing. Thus, once we have a discrete maximum, we are close to the real maximum.

Now, all we are left to do in order to achieve any desired precision is to refine the search near this discrete maximum, find a new, better approximation, and refine again, until we have enough precision. Of course, one first problem with this algorithm is the initial search using a maximal time . It is possible that if or are not large enough, then we do not detect any intersection of the two polygons. Thus, an initial guess, based on a mathematical argument is needed in order to reduce the search of the optimal time to an interval which is small enough to have enough initial precision to detect the discrete maximum.

The algorithm presented below, uses Matlab’s predefined function polybool which can compute the intersection of two polygons. Of course, this is an overkill, since dealing with intersections of convex polygons is not that complicated (but still, I didn’t have enough time to play with the problem, in order to provide a more optimized version). I do not treat the search for the initial time interval. As I think about it, I guess a n argument based on finding some line intersections should give us a narrow enough time interval (with some care for the case when the two speed directions are collinear). The algorithm presented below solves the sample cases, but could fail in more general situations.

function Prob1_2015(p1,p2) % choose initial polygons; see the text of the problem p1 = [6 3 2 2 4 3 6 6 6 7 4 6 2 2 2]; p2 = [4 18 5 22 9 26 5 22 1 -2 1]; %p1 = [4 0 0 0 2 2 2 2 0 1 1]; %p2 = [4 10 0 10 2 12 2 12 0 -1 1]; np1 = p1(1); np2 = p2(1); cp1 = p1(2:1+2*np1); cp2 = p2(2:1+2*np2); vp1 = p1(end-1:end); vp2 = p2(end-1:end); cp1 = cp1(:); cp1 = reshape(cp1,2,np1); xp1 = cp1(1,:); yp1 = cp1(2,:); cp2 = cp2(:); cp2 = reshape(cp2,2,np2); xp2 = cp2(1,:); yp2 = cp2(2,:); %set precision prec = 1; %here there should be a clever initial choice of %the starting time and stopping time %this choice works well in this case start = 0; stop = 5; while prec>1e-6 n = 100; timex = linspace(start,stop,n); areas = zeros(size(timex)); for i = 1:n t = timex(i); xt1 = xp1+t*vp1(1); yt1 = yp1+t*vp1(2); xt2 = xp2+t*vp2(1); yt2 = yp2+t*vp2(2); [x,y] = polybool('intersection',xt1,yt1,xt2,yt2); areas(i) = polyarea(x,y); end [m,I] = max(areas); if m<1e-6 % if no polygonal intersection is detected % there is nothing further to do display('never'); break end tapp = timex(I); fprintf('Precision %f | Time %f\n',prec,tapp); start = tapp-prec; stop = tapp+prec; prec = prec/10; end clf %this draws the final position of the polygon %as well as their intersection fill(xt1,yt1,'blue') axis equal hold on fill(xt2,yt2,'red') fill(x,y,'green') axis equal hold off

Here’s what you get for the first sample test provided in the questions:

>> Prob1_2015 res = 4.193548