Computing roundness is easy if the set is almost round
Computing roundness is easy if the set is almost round
复制标题
如果集合几乎是圆形的，则计算圆度很容易
DOI：
10.1145/304893.304984
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
P. Ramos
中科院分区：
文献类型：
--
作者：
O. Devillers;P. Ramos
本文讨论了包含一组点的最薄环的计算问题，S，⊂，Rd。对于d=2，我们证明了对于一个相当一般的几乎圆集族，只要稍加修改Sharir和Welzl求解LP型问题的算法，这个问题就可以在O(N)期望时间内得到解决。我们还证明，对于凸点位置上的点，利用线性规划可以在(O(N))确定的时间内求解该问题。对于d=2和d=3，我们提出了一种离散局部优化方法。尽管该算法极其简单，最坏情况下的复杂度为O(nd+1)，但我们给出的经验证据表明，当输入几乎是圆形时，该算法的性能非常好(接近线性时间)。我们还给出了部分解释这一行为的理论结果：尽管局部极小值的数目可能是二次的(对于d=2已经是)，但在实践中不太可能遇到具有多个局部极小值的几乎圆形构型的点。
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(nd+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.