Konferensartikel

We propose an exact minimum bounding sphere algorithm for large point sets in low dimensions. It aims to reduce the number of required passes by retrieving a well-balanced set of outliers in each linear search through the input. The behaviour of the algorithm is mainly studied in the important three-dimensional case. The experimental evidence indicates that the convergence rate is superior compared to previous exact methods, which effectively results in up to three times as fast execution times. Furthermore, the run times are not far behind simple 2-pass constant approximation heuristics.

Bounding spheres; computational geometry; geometric algorithms