Before revision:  We also provide a discrete algorithm for constructing it in O(n^3  +n^2f(n)) time in the real-RAM model of computation, where f(n) is the runtime of a geometric primitive (which we identify ) that can be performed in the real-RAM model or can be approximated numerically, but cannot, in general, be performed exactly in an algebraic model of computation  .
After revision:  We also provide a discrete algorithm for constructing it in O(n^3 +n^2f(n)) time in the real-RAM model of computation, where f(n) is the runtime of a geometric primitive (which we identify ) that can be performed in the real-RAM model or can be approximated numerically, but cannot, in general, be performed exactly in an algebraic model of computation . We show, however, how to compute the geometric primitive exactly for polygonal convex distance functions .