abstract
The problem of finding the smallest enclosing ellipsoid of an
$n$-point set $P$ in
\linebreakByHand
$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~\cite{w-sedbe-91a} 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.
Back to the publications page
