Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

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