Linear Programming - Algorithms

Question

Given two sets P1, P2 of points in a plane.

Solution: If there is a line which separates the points of P1 from P2, a line that holds that all points in P1 are on one side and all points in P2 are on the other side, return 'There is such line', otherwise return 'There is no such line'.

Example: consider these points: 5 = (−2,1) ,4 = (6,2) ,3 = (2, −2) ,2 = (1,5) ,1 = (−2, −1).

P1 = {1,2} and P1 = {3,4} ---> return 'There is such line' y = 2x-3 for example.

whereas P1 = {1,2} and P1 = {3,4,5} ---> return 'There is no such line'.

Is there a linear designed based algorithm which doesn't use convex hulls to solve this problem? I'll be happy for suggestions!

Answer 1

One solution would be to design the two convex hulls of P1 and P2 respectively. You can use one of the algorithms listed on Wikipedia. The Graham scan is quite simple to implement and has O(nlogn) time complexity.

Then check whether those two polygons are overlapping. For that you can take these steps:

1. For each vertex on the first convex hull, check whether it is fully inside the second. This means checking that a vertex is on the same side of every (directed) edge of the other convex hull. If this is true for at least one vertex, then the polygons overlap. We can stop here.
2. Do the same, but now with each vertex of the second convex hull.

If none of these steps gives the conclusion that they overlap, then they don't.

Answer 2

Step 1: Create convex hull for set of points p1. Check if any points of set P2 are inside the convex hull for points P1.

Step 2: Create convex hull for set of points p2. Check if any points of set P1 are inside the convex hull for points P2.

If in either of the steps, a point lies inside the polygon, 'There is no such line'. Otherwise, 'There is such line'.

You have to do both the steps. One can't just create a convex hull for P1 and check if points in P2 are inside convex hull of P1 and vice versa. As shown in example in above image, you can't just have a convex hull for red points and check if yellow points are inside that convex hull.

Time complexity for convex hull: O(nlogn).

References:

• Convex hull algorithms
• Check if a point lies inside the convex hull.
• Another resource for Check if a point lies inside the convex hull

You can also find some interesting approaches on stack overflow and computer science stack exchange. These mention some approaches that don't use convex hull approach.

Answer 3

It's true that there is a line separating the two sets of points if and only if there is a line that separates their convex hulls, but you don't need to go through all the work of generating the hulls and intersecting polygons in order to solve this problem.

First, check to see if the point sets overlap in their x coordinates, i.e., if min_x(P1) <= max_x(p2) and max_x(p1) >= min_x(p2)

If they do not overlap in their x coordinates, then there is a vertical line that separates them and you're done. Otherwise...

Find the upper and lower hulls of P1 and the upper and lower hulls of P2 using the monotone chain algorithm: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

If there is a line separating P1 and P2, then in the region of overlapping x coordinates, either the lower hull of P1 will be entirely above the upper hull of P2, or vice-versa. You can check this by processing the points on the upper and lower hulls in order of their x coordinates.

This algorithm does use the monotone chain method, which is used to generate convex hulls, but it avoids the general polygon intersection and is pretty easy to implement in O(N log N) time.