Before revision:  By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. In the mid-1970's, a result by Dudley showed that O(1/\varepsilon^{(d-1)/2}) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices .
After revision:  By combinatorial complexity we mean the total number of faces of all dimensions . Classical constructions by Dudley and Bronshteyn/Ivanov show that O(1/\varepsilon^{(d-1)/2}) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices .