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