Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

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