Consider all \(n^2\) vectors that point from an emitter to a receptor. We claim that a necessary (but not sufficient) condition for the validity of a solution is that the directions of these vectors must be mutually distinct.
This is easily shown: whenever two vectors have the same direction, either they share the same endpoint (in which case they overlap) or we have two distinct pairs of points. In the latter case all four points are clearly coplanar and in that plane the line segments that form the diagonals of their convex hull have to intersect.
If we have chosen a box with dimensions \(a\times b\times c\), how many possible vectors are there? The first coordinate of any vector will be between \(-(a-1)\) and \(+(a-1)\), inclusive, because it’s the difference of two values that are both in the range \([0,a-1]\). Similarly, we have \(2b-1\) options for the second and \(2c-1\) for the third coordinate. This gives us a total of \((2a-1)(2b-1)(2c-1) < 8abc\) directions.
Any valid solution will have to contain \(n^2\) distinct directions. Hence, we need a box with volume strictly greater than \(n^2/8\). This gives us the lower bound that the optimal solution is \(\Omega(n^2)\).
We will now show that the optimal solution is always \(\Theta(n^2)\) by showing an asymptotically matching upper bound.
We can choose \(a=n\), \(b=n\), and \(c=2\). The volume of this box is \(2n^2\).
Within this box we can choose the points \((x,0,0)\) as the emitters and points \((0,y,1)\) as the receptors.
These points form a valid solution.
(Imagine a blue line segment from \((0,0,0)\) to \((99,0,0)\) and a red line segment from \((0,0,1)\) to \((0,99,1)\). We claim that even in this continuous case there are no two intersecting line segments, each from a different blue to a different red point. Why? Such two line segments define a plane. That plane would have to contain two blue and two red points. But any plane that contains two blue points contains the entire blue segment, and the same is true for the red points. And there is no plane that contains both our line segments.)
This pattern, once discovered, is easy to implement and scores about 63 points.
The authors’ opinion is that the best thing to do with this problem is to gain a quick stroke of genius to discover the 63-point solution, take those points and avoid the rest of this problem like a plague because the payoff you’ll get will most likely be negligible when compared to the amount of effort you’ll have to expend to make some progress :)
That being said, the above solution is certainly not the best one, and we can still be clever about how we search for better solutions. For instance, the above observation about vectors being distinct is a very powerful way to quickly prune all kinds of search for a better solution.
(Note that checking the validity of a solution takes \(O(n^4)\) time, and recalculating the number of intersecting pairs when we add or remove a point still takes \(O(n^3)\) time. On the other hand, we can maintain the set of directions that correspond to our current set of points, and whenever we remove or want to add a new point we can do the update or check in \(O(n)\) time.)
The best solution found by authors in time roughly proportional to contest time had dimensions \(11\times 15\times 101\).
