# Check if intersection of several 2D half-planes is empty

I have a large set of half-planes $$a_ix+b_iy + c_i \geq 0$$.
What I need is is the fastest way to determine if they have at least one common point.
Currently I build a convex polygon by adding half-planes sequentially, there are $$O(n^2)$$ checks if a point belongs to a half-plane.
I need an algorithm that does $$O(n \log n)$$ or $$O(n)$$ checks.

This paper describes a method to solve a system of $$n$$ linear inequalities with at most two variables per inequality and $$m$$ distinct variables in total in $$O(n m^3 \log m)$$ time. (I am swapping the meaning of $$n$$ and $$m$$ with respect to the paper in order to keep the name $$n$$ consistent with your question).
In your case $$m=2$$ therefore the resulting time complexity is $$O(n)$$.