faster than O(n^3) algorithm for solving the following problem

Question

Consider the following problem:

Given a set of n inequalities each of the form ax+by≤c for some a,b,c in Q, determine if there exists x and y in Q that satisfy all the inequalities.

Here is an O(n³) algorithm for solving this: for each pair of inequalities, if they are non parallel, intersect their corresponding lines to get a point (x,y). test each of these points against all the inequalities. There are O(n²) such points and there are n inequalities thus the algorithm is O(n³).

I would like a faster algorithm for solving this (eg: O(n²), O(n*logn), O(n)). If you can provide such an algorithm in an answer that would be great. Alternatively, if this problem or a super set of it has a name and has been well researched giving the name would be sufficient. Thanks.

Answer 1

Here is the sketch of such an algorithm. First consider all inequalities which are upper bounds, i.e. $ax + by \leq c$ where $b > 0$ (so they can be written in the form $y \leq mx + k$). This doesn't really handle edge cases, where $b = 0$, but it should be easy to adapt.

Note that the bounding curve is composed of a series of lines strictly decreasing in slope. You can argue about convexity, or convince yourself of this with a drawing. So we may first sort the lines in order of decreasing slope (in $O(n \log n)$ time) and then check the intersections between pairs of lines consecutive in this ordering to find the actual vertices of the bounding curve. Also note that these constraints alone will always have some point which satisfies all the inequalities, as we can just make $y$ arbitrarily small.

You can do the same thing with the lower bounds (where $b < 0$) and get another region containing all the points which satisfy these inequalities in $O(n \log n)$ time. Then it's just a matter of finding the intersection of these two regions, if we add in vertical constraints. But you can do this by comparing the bounding curves, traversing from left to right (start where the leftmost constraints of the two regions meet, and end where the rightmost constraints meet). This is really a matter of checking if the line between two adjacent vertices on the bottom intersects the line between the corresponding vertices on the top (which vertices matter is entirely decided by $x$-value). Since there are $O(n)$ such pairs of lines to compute, and we only need to recompute once at each vertex, this step takes $O(n)$ time as well. This gives an $O(n \log n)$ algorithm.