Approximating Smallest Enclosing Disks
Frank Nielsen, Richard Nock · Canadian Conference on Computational Geometry · 2004
The smallest enclosing disk (SED for short) problem dates back to 1857 when J. J. Sylvester [7] first asked for the smallest disk enclosing points on the plane. Although ! #%$'&( *) -time algorithms were designed for the planar case in the early 1970s [4, 6], the problem complexity was only settled in 1984 with N. Megiddo’s first linear time algorithm [3] for solving linear programs in fixed dimension. Unfortunately, these algorithms exhibit a large constant hidden in the big-Oh notation and do not perform so well in practice. E. Welzl [8] developed a simple recursive + , *) randomized algorithm for point sets, called ”move-to-front” heuristic, that is often used by practitioners (see Section 6). Recently, Fischer et al. [2, 1] described a pivoting scheme resembling the simplex method for linear programming that, despite no theoretical time bounds (besides guaranteed termination), can tackle exactly problems in large dimensions for ball sets. Computing smallest enclosing disks are useful for metrology, machine learning and computer graphics problems. Fast constant approximation heuristics are popular in computer graphics [5]. Our paper aims at designing a fast deterministic (i.e., worst-case time bounded) approximation algorithm that is suitable for real-time demanding applications. Since they gain in speed as the precision requirement decreases, approximation algorithms are well suited for such purposes. Our simple implementation for point/disk sets is a mere 30-line C code which does not require to compute the basic primitive of the smallest disk enclosing three disks. In fact, surprisingly, we exhibit a robust approximation algorithm using only algebraic predicates of degree 2 using integer arithmetic. Moreover, as shown in Section 6, our floating-point implementation outperforms or fairly competes with traditional methods while guaranteeing worst-case termination time. Sony Computer Science Laboratories Inc. E-mail: [email protected] . Universite Antilles-Guyane, DSI GRIMAAG. E-mail: [email protected] /10 /32