https://hal.inria.fr/hal-00795064Devillers, OlivierOlivierDevillersGEOMETRICA - Geometric computing - CRISAM - Inria Sophia Antipolis - Méditerranée - Inria - Institut National de Recherche en Informatique et en Automatique - Inria Saclay - Ile de France - Inria - Institut National de Recherche en Informatique et en AutomatiqueRamos, PedroPedroRamosDepartamento de Matematicas [Alcala de Henares] - UAH - Universidad de Alcalá - University of AlcaláComputing Roundness is Easy if the Set is Almost RoundHAL CCSD2002[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]Devillers, Olivier2013-02-27 10:59:212023-03-16 04:01:512013-02-27 10:59:21enJournal articles10.1142/S02181959020008401In this paper we address the problem of computing the thinnest annulus containing a set of points S ⊂ Rd. For d = 2, we show that the problem can be solved in O(n) expected time for a fairly general family of almost round sets, by using a slight modification of Sharir and Welzl's algorithm for solving LP-type problems. We also show that, for points in convex position, the problem can be solved in (O(n) deterministic time using linear programming. For d = 2 and d = 3, we propose a discrete local optimization approach. Despite the extreme simplicity and worst case O(n^(d+1)) complexity of the algorithm, we give empirical evidence that the algorithm performs very well (close to linear time) if the input is almost round. We also present some theoretical results that give a partial explanation of this behavior: although the number of local minima may be quadratic (already for d = 2), almost round configurations of points having more than one local minimum are very unlikely to be encountered in practice.