abstract
The problem of finding the unique closed ellipsoid of smallest
volume enclosing an $n$-point set $P$ in $d$-space (known as the
\emph{L\"owner-John ellipsoid} of $P$ \cite{j-episc-48}) is an instance of
convex programming and can be solved by general methods in time $O(n)$ if the
dimension is fixed~\cite{w-sedbe-91a,msw-sblp-92,d-ccpac-92,as-rssal-93}. 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~\cite{st-mce-80,p-cmse-82,s-bkep-94}, these formulae
are simpler and faster to evaluate, and they only contain rational
expressions, allowing for an exact solution.
Back to the publications page
