Xavier Holt edited subsection_Linear_Separability_We_are__.tex  about 8 years ago

Commit id: a71dd462c8df9f81d3ba0970b24eb19e185898a5

deletions | additions      

       

We are dissuaded from the convex-hull intersection approach by its $\Omega(n \log h)$ complexity. Instead given the low dimensionality we seek to rephrase it as a linear-programming problem.  A line in the plane $\mathbf{ux} + v = 0$ with $\mathbf{u,x}\in \mathbb{R}^2$ splits our plane into two regions: $\mathbf{ux} + v > 0$ and $\mathbf{ux} + v < 0$  What we are seeking is a line which separates the plane into two half-spaces such that all of