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.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2002, 12 (3), pp.229-248. 〈10.1142/S0218195902000840〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00795064
Contributeur : Olivier Devillers <>
Soumis le : mercredi 27 février 2013 - 10:59:21
Dernière modification le : samedi 27 janvier 2018 - 01:31:39

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

315