# constructing a curve dividing two sets of points

Lets assume I have two sets of points, each characterized as being "A" or "B", respectively, that are in a Euclidean plane. Theoretically these two sets are samplings from a space that has boundaries. Now I want to construct a boundary. So I want to construct the simplest curve that divides the two sets of points.

A simple example would be a space where x< 0 is the A region, x>0 is the B region. Generate 100 random points in a unit box centered on the origin. Now you want to find a line that divides the "A" points from the"B" points (forgetting that you know what the original answer was). How would you do this?

How would you do this in general?

-
Are A and B finite or not? what if e.g. A is the set of points with rational coortinates and B is its complement? – Pietro Majer Jul 2 '12 at 17:39
There certainly are sets of points for which this would generate either an infinite in complexity or non-definable boundary. However, in this case, A and B are finite. For heuristic purposes one can assume that they are actually random points drawn from two domains that do have a well-defined boundary between them. (e.g. the interior and exterior of a circle in a plane.) Currently I am considering something functional, but less than completely satisfying involving convex hulls and subtractions of the overlaps. – Carolyn Jul 2 '12 at 17:53
If you need to do this in practice, this is known as a binary classification problem. The fashionable tool at the moment is a support vector machine. en.wikipedia.org/wiki/Support_vector_machine – Douglas Zare Jul 2 '12 at 18:02
Does it matter if I have five sets of points? And one set is completely bound by the other sets? Can SVMs still address this problem? – Carolyn Jul 2 '12 at 23:46
Yes, they can help. It is no longer a binary classification problem, but there are a few standard ways to use multiple binary SVMs, and knowledge of the specific properties of the set may give you reasons to choose one method over another. – Douglas Zare Jul 3 '12 at 0:55

Assuming the size of A and B are less than 10000 points, I would use a Support Vector Machine with a Gaussian Kernel.

http://en.wikipedia.org/wiki/Support_vector_machine

-

This is not directly responsive to your question, but it might be relevant to what you're trying to accomplish.

Suppose you find a curve that correctly classifies all 100 of your points. You'd like this curve to have a high probability of correctly classifying a large fraction of the points in the much larger sample from which your 100 points were drawn.

In particular, suppose you'd like your curve to have probability at least $1-\delta$ of correctly classifying a fraction at least $1-\epsilon$ of that larger set of points (where $\delta$ and $\epsilon$ are some fixed --- and presumably small --- constants).

A sufficient condition for this is

$$100 > {N\over\epsilon}Log(1/\delta)$$

where $N$ is the maximum number of points that can always be successfully separated by some member of your class of allowable curves. E.g. if you restrict your curves to be lines, then $N=3$, because any 3 points, no matter how they are labeled $A$ and $B$, can be successfully separated by a line.

I wish I could remember where I learned this, so that I could point you to a source. I have a reasonably powerful (but perhaps faulty) memory that Scott Aaronson had something to do with it.

-