Smallest Enclosing Circles -
An Exact and Generic Implementation

Bernd Gärtner
Institut für Theoretische Informatik
ETH Zentrum, IFW
CH-8092 Zürich

Sven Schönherr
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin, Germany

Report B 98-04
April 1998

We present a C++ implementation of an optimisation algorithm for computing the smallest (w.r.t. area) enclosing circle of a finite point set in the plane. The algorithm is implemented as a semi-dynamic data structure, thus allowing to insert points while maintaining the smallest enclosing circle. 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: 
File:   pub/reports/