patternMinor
Check if intersection of several 2D half-planes is empty
Viewed 0 times
emptyseveralplanesintersectioncheckhalf
Problem
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.
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.
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#126609, answer score: 4
Revisions (0)
No revisions yet.