Computing a minimum-width square annulus in arbitrary orientation
Computing a minimum-width square annulus in arbitrary orientation
复制标题
计算任意方向的最小宽度方形环
DOI：
10.1016/j.tcs.2016.11.010
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Bae
中科院分区：
文献类型：
--
作者：
S. Bae
在这篇文章中，我们讨论了计算在任意方向上包围平面上给定的n个点的最小宽度平方环的问题。正方形环是两个同心正方形之间的区域。我们给出了一个O(n，3log，，n)时间算法，它在所有方向上都能找到这样的平方环。
In this paper, we address the problem of computing a minimum-width square annulus in arbitrary orientation that encloses a given set of n points in the plane. A square annulus is the region between two concentric squares. We present an O (n 3 log n)-time algorithm that finds such a square annulus over all orientations.