Suppose we have a set of points $(x,y)$ in the plane where each point is either boy or a girl. Does there exists a randomized linear-time algorithm to determine if we can fit a parabola (given by a polynomial $ax^2+bx+c$) that separates the boys from girls in the plane?

In addition to finding such a parabola if one exists, how can the algorithm detect if no such parabola exists and terminate?

  • 2
    $\begingroup$ Do you have reason to believe that there is such a randomized algorithm that can determine if a suitable curve exists? After thinking for a bit, none of my (linear time) approaches to this problem will terminate if such a curve does not actually exist. $\endgroup$ – Mike Pierce Mar 2 '16 at 6:27
  • $\begingroup$ @MikePierce Yes I do believe so. I'm interested in hearing what your approach is if such curve does exist. $\endgroup$ – kenny Mar 2 '16 at 7:04
  • 2
    $\begingroup$ I was kinda hoping for a reason why you believe such an algorithm exists. Also, there is a difference between a parabola and a more general quadratic curve. Which one do you actually mean? And if you mean a parabola, do you mean a typical $y = ax^2+bx+c$ parabola, or a parabola in the plane with its axis of symmetry at any arbitrary angle? $\endgroup$ – Mike Pierce Mar 3 '16 at 4:05
  • $\begingroup$ @MikePierce Yes, the typical $y=ax^2 +bx+c$ is what I'm asking. $\endgroup$ – kenny Mar 3 '16 at 4:14
  • $\begingroup$ @MikePierce I suppose after all this time maybe you would like to hear what I have so far. If we represent this as a LP problem as an existence problem where $y$ and $x$ are fixed constants in $y=ax^2+bx+c$ and find an optimal $a,b,c$ such that we can stretch parabola to separate the boys from the girls. We are finding an valid distance that satisfied the following contraints. If $a$ is positive and boys are within the parabola's curve, then we want to make sure that all points $d_{bi} \leq y_{bi} - (ax_{bi}^2+bx_{bi} + c)$ for points $(x_{bi}, y_{bi}$, for read, the distance $d_{ri}$ must be $\endgroup$ – kenny Mar 9 '16 at 23:47

A Support Vector Machine might be able to do it. Suppose we map your 2D $(x,y)$ space to 3D $(x,x^2,y)$. An SVM will find a plane in this space, of the form $a x + b x^2 + c y = d$ which optimally separates the classes. Solving for y we get $y = \frac{d}{c} - \frac{a}{c} x - \frac{b}{c} x^2$ which is indeed the equation of a parabola. SVMs can be made robust against the possibility that a separating plane (parabola) does not exist, they will still find the "best" solution in some sense, and afterwards you can check (in linear time) whether the solution actually separates the classes (also see this question).

I am not certain whether you can train such an SVM in linear time. This paper suggests that it can be done.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.