Exact primitives for smallest enclosing ellipses

The problem of finding the unique closed ellipsoid of smallest volume enclosing an n-point set P in d-space (known as the Lowner-John ellipsoid of P (John, 1948) is an instance of convex programming and can be solved by general methods in time O(n) if the dimension is fixed O Welzl, 1991; Matousek et al., 1992; Dyer, 1992; Adler and Shamir, 1993). The problem-specific parts of these methods are encapsulated in primitive operations that deal with subproblems of constant size. We derive explicit formulae for the primitive operations of Welzl's randomized method (Welzl, 1991) in dimension d = 2. Compared to previous ones (Silverman and Titterington, 1980; Post, 1982; Schonherr, 1994), these formulae are simpler and faster to evaluate, and they only contain rational expressions, allowing for an exact solution. (C) 1998 Elsevier Science B.V. All rights reserved.