5
$\begingroup$

It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It seems this can be done in linear time. Algorithms that solve linear programs are also capable of deciding whether the LP is feasible or not and 2-d linear programs can be solved in linear time (linear in terms of the number of constraints). So to decide whether a set of n halfplanes is non-empty or not, just solve the LP that has those halfplanes as its constraints with any objective function.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .