We are dissuaded from the convex-hull intersection approach by its \(\Omega(n\log h)\) complexity. Instead given the low dimensionality we seek to rephrase it as a linear-programming problem.

A line in the plane \(\mathbf{ux}+v=0\) with \(\mathbf{u,x}\in\mathbb{R}^{2}\) splits our plane into two regions: \(\mathbf{ux}+v>0\) and \(\mathbf{ux}+v<0\) referred to as \(h^{+}\) and \(h^{-}\) respectively.

We seek a line whose split ensures all \(q\in\mathcal{Q}\) are on one side and all \(p\in\mathcal{P}\) the other. We can always invert half-space ownership by multiplying our line by \(-1\), so WLOG we seek to ensure all \(p\in h^{+}\) and \(q\in h^{-}\). That is,

This is a system of linear constraints in three-dimensions: \(u_{1},u_{2}\) and \(v\). We only need a feasible solution, so we set our objective function to be constant.

In class we were shown a randomised algorithm which solved fixed-dimension linear problems in expected \(O(n)\) time. This was demonstrated in the plane, but we will that the same approach also works in three-dimensions.

The algorithm iteratively adds constraints and maintains an optimal solution on the shrinking feasible region. The running time is dominated by when our current optimal solution is not in the region defined by our new half-space. The probability of this occurring is \(\leq\frac{3}{i}\) for the \(i\)-th constraint. This follows by the exact same backward-analysis conducted in class. The difference in numerator is a result of the fact that three of our linear constraints determine the optimal vertex in \(\mathbb{R}^{3}\).

So what’s our computational complexity when we have to update our optimum? Well as in class, we’re only concerned with the intersection of our feasible region and new constraint. In three dimensions this takes the form of a 3D polyhedron and a plane. It’s easy to see either geometrically or algebraically that this intersection is in fact a polygon with \(O(i)\) edges. As such, finding our optimal value on this intersectional plane is a two-dimensional linear problem. This is exactly the class of problems we handled in-lecture, and our runtime is expected \(O(i)\).

Putting everything together, we have that the expected runtime is:

Correctedness of the algorithm follows from the fact that: 1) None of the lemmas presented in-class we relied upon for correctness were dimension-dependent, and 2) As argued above our linear-programming formulation was entirely equivalent to the problem statement.