Complexity of finding a consistent hyperplane Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample point $d$-tuples which span all candidate hyperplanes, and the dimension $d$ is the hardness parameter (see the paper by Höffgen et al.)
What about the realizable case? Here two natural algorithms come to mind: the Perceptron and Linear Programming. The Perceptron has runtime quadratic in inverse margin. Since we currently don't know of any strongly polynomial LP solvers, all current methods depend, in the worst case, on the configuration of the labeled points -- i.e., the runtime also depends on the margin.
Question: Is there a strongly polynomial algorithm for finding a consistent hyperplane?
Edit (04-Oct-2018). I had accepted an answer but there is a problem with it, so as of now the status of the question is unknown. Is consistent hyperplane as hard as general LP?
Edit 2 (06-Oct-2018). Status: solved!
Second version, hopefully correct.

I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce linear programming to the feasibility problem.

Let us first reduce the strict feasibility problem $\exists? x: Ax &lt; b$ to finding a linear separator. Towards this, notice that you can reduce to the special case $b=0$: just transform the constraints to 
$$
Ax + tb &lt; 0, \\
t &lt; 0 
$$
If $Ax &lt; b$ is feasible for some $x$, then $(x, -1)$ is feasible for the problem above. Conversely, if $(x, t)$ is feasible for the problem above, then $\tilde{x} = -x/t$ is feasible for $A\tilde{x} &lt; b$. 
This reduction just adds a row and a column to $A$, and a new variable $t$. 

Assume then that you are given the problem $Ax &lt; 0$. 
Create a data set which has one point labeled red for every row of $A$, and is equal to that row. It also contains the origin $0$, labeled blue. Any hyperplane $H$ separating the red-labeled points from the blue-labeled origin gives a solution to $Ax &lt; 0$: just take the normal of $H$ in the direction of the origin to be $x$. 

The final step is to reduce the feasibility problem $Ax \le b$ to the strict feasibility problem $Ax &lt; b$. We argue that given an oracle for the strict feasibility problem, we can solve the feasibility problem. Let $S$ be an inclusion-maximal set of constraints such that the system $\forall i \in S: (Ax)_i &lt; b_i$ is feasible: we can find $S$ in at most $m$ calls to the oracle (assuming $A$ is $m\times n$). If $S$ contains all constraints, we are done. Otherwise, it is not hard to see that, if $Ax \le b$ is feasible, then for any $i \not \in S$ the constraint $(Ax)_i \le b_i$ must be satisfied with equality for all feasible $x$. Use one (or more) of these constraints to eliminate one (or more) of the variables, and recurse on the remaining variables. 

This equivalence between finding a linear separator and linear programming is surely well-known, but I do not know what the right reference is. For example, I have seen something like the final reduction above attributed to Chvatal.