You can try the Lasserre moment relaxations of polynomial optimization problems, see the survey of Monique Laurent:
http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf
The code for your example in YALMIP (a MATLAB package) is:
clear b c m r
sdpvar b c m r
x = [1 2; 3 5; 9 7; 6 8; 7 6.5; 3 5.8; 10 19; 4 6]
constraints = set(b>=0) + set(r^2<=1+m^2) + set(m>=0)
for i = 1 : size(x,1)
constraints = constraints + set(0 <= x(i,2)-x(i,1)*m-c <= b*r)
end
relaxdeg=4
[info,sol,mom,cert]=solvemoment(constraints,b,[],relaxdeg)
sol{1}
This gives the following (at least numerically) optimal solution:
b = 4.7548
c = -9.9939
m = 1.8874
r = 2.1350
For this to work you need an SDP solver like SeDuMi. Implementations of the Lasserre moment approach other than YALMIP are SOSTools, GloptiPoly and SparsePOP. I have also some slides which might be helpful:
http://www.math.uni-konstanz.de/~schweigh/presentations/polopt-kirchberg.pdf