Simply search for convex hull for both the X points and the O points separately. You just need to check whether any segments of the hulls intersected or whether either hull was enclosed by the other.
If the two hulls were found to be totally disjoint the two data-sets would be geometrically separable.
Since the hulls are convex, any separator would be a straight line.
There are efficient algorithms that can be used to find the convex hull, and to perform line-line intersection tests for a set of segments, so overall it seems that an efficient O(nlog(n)) algorithm should be possible.
This type of approach should also generalize to general k-way separation tests (where you have k groups of objects) by forming the convex hull and performing the intersection tests for each group.
It should also work in higher dimensions, although the intersection tests would start to become more challenging...
For more details on this, study Machine Learning Online Course.
Hope this helps.