Computing Roundness is Easy if the Set is Almost Round - Archive ouverte HAL Access content directly
Journal Articles International Journal of Computational Geometry and Applications Year : 2002

Computing Roundness is Easy if the Set is Almost Round

(1) , (2)
1
2

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.
Not file

Dates and versions

hal-00795064 , version 1 (27-02-2013)

Identifiers

Cite

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

Collections

INRIA INRIA2
172 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More