An efficient certifying algorithm is proposed that, given a set of n points in \(\mathbb {R}^d\) with binary labels, either returns a hyperplane separating the points, or identifies \(d+2\) of the labeled points that cannot be separated by any hyperplane. The existence of such \(d+2\) points in the inseparable case is known to be guaranteed by Kirchberger’s theorem in combinatorial geometry; we show how to compute these points efficiently. We then propose a dimension-free and constructive extension of Kirchberger’s theorem, where for any \(\varepsilon >0\) one finds either a separating hyperplane, or \(O(1/\varepsilon ^2)\) of the labeled points that cannot be separated with normalized margin \(\varepsilon \) by any hyperplane. Our algorithms are based on solving one primal-dual pair of linear programs with d primal and n dual variables, and at most \(n-d\) linear equation systems with O(d) equations and O(d) unknowns.