# Smallest Enclosing Ellipses -

An Exact and Generic Implementation

###
Bernd Gärtner

Institut für Theoretische Informatik

ETH Zentrum, IFW

CH-8092 Zürich, Switzerland

email: gaertner@inf.ethz.ch

Sven Schönherr

Institut für Informatik

Freie Universität Berlin

Takustr. 9, D-14195 Berlin, Germany

email: sven@inf.fu-berlin.de

Report B 98-05

April 1998

We present a C++ implementation of an optimisation algorithm for
computing the smallest (w.r.t. area) enclosing ellipse of a finite
point set in the plane. We obtain an exact solution by using Welzl's
method together with the primitives as described in report B 97-03.
The algorithm is implemented as a semi-dynamic data structure, thus
allowing to insert points while maintaining the smallest enclosing
ellipse. Following the *generic programming* paradigm, we use
the template feature of C++ to provide generic code. The data
structure is parameterized with a traits class, that defines the
abstract interface between the optimisation algorithm and the
primitives it uses. The interface of the data structure is compliant
with the STL.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-98-05.ps.gz