Smallest Enclosing Ellipses - Fast and Exact

Bernd Gärtner
Institut für Theoretische Informatik
ETH Zürich
Haldeneggsteig 4, CH-8092 Zürich, Switzerland

Sven Schönherr
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin, Germany

Report B 97-03
May 1997

The problem of finding the smallest enclosing ellipsoid of an n-point set P in d-space is an instance of convex programming and can be solved by general methods in time O(n) if the dimension is fixed. The problem-specific parts of these methods are encapsulated in \emph{primitive operations} that deal with subproblems of constant size. We derive explicit formulae for the primitive operations of Welzl's randomized method in dimension d=2. Compared to previous ones, these formulae are simpler and faster to evaluate, and they only contain rational expressions, allowing for an exact solution.

Get the report here or by anonymous ftp: 
File:   pub/reports/