How can I say if I can separate two groups of points with a line?

Question

What is the algorithm to determine if I can split an array of points with a line?

Input: array of (x ,y, TYPE)   # TYPE in (0, 1)
Output: True/False

Or how can I say if this is not possible? When 1 (or more) points are always somewhere in another group of points.

Answer 1

Here are some crazy ideas:

• Construct a “convex hull” for each point set (see, for example, https://en.wikipedia.org/wiki/Graham_scan ). Then check if the two convex hulls intersect or not. If it does not intersect, than (frankly, I'm not sure) the answer is YES (dividing line exists).

• (). - . .