Skip to Main content Skip to Navigation
Journal articles

Computing Roundness is Easy if the Set is Almost Round

Olivier Devillers 1 Pedro Ramos 2
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : In 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Wednesday, February 27, 2013 - 10:59:21 AM
Last modification on : Thursday, October 17, 2019 - 12:04:02 PM




Olivier Devillers, Pedro Ramos. Computing Roundness is Easy if the Set is Almost Round. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2002, 12 (3), pp.229-248. ⟨10.1142/S0218195902000840⟩. ⟨hal-00795064⟩



Les métriques sont temporairement indisponibles