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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
Your problem can be solved in linear time.
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)$.
