abstract
We present a solver for quadratic programming problems, which is tuned for
applications in computational geometry. The solver implements a
generalization of the simplex method to quadratic programs. Unlike existing
solvers, it is efficient if the problem is dense and has few variables or
few constraints. The range of applications covers well-known problems like
\emph{smallest enclosing ball}, or \emph{polytope distance}, but also linear
programming problems like \emph{smallest enclosing annulus}. We provide an
exact implementation with only little overhead compared to pure
floating-point code. Moreover, unlike all methods for these problems that
were suggested (and implemented) before in computational geometry, the
runtime in practice is not exponential in the dimension of the problem,
which for example allows to compute smallest enclosing balls in dimensions
up to 300 (beyond that, the exact arithmetic becomes the limiting factor).
The solver follows the generic programming paradigm, and it will become part
of the European computational geometry algorithms library \cgal.
Back to the publications page