Xavier Holt edited subsection_Linear_Separability_We_are__.tex  about 8 years ago

Commit id: b81f4aefb114c879c4b236c3918bf84cced14029

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 want is 0$ referred to as $h^+$ and $h^-$ respectively.  We seek  a line whose split ensures all $q\in\Q$ are on one side and all $p\in\P$ the other. We can always invert half-space ownership by multiplying our line by $-1$, so WLOG we seek to ensure all $p\in h^+$, $q\in h^-$ .  What we are seeking is a line which separates the plane into two half-spaces such that all of