Minimum-width rectangular annulus
Minimum-width rectangular annulus
复制标题
最小宽度矩形环
DOI：
10.1016/j.tcs.2012.02.041
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Sandip Das
中科院分区：
文献类型：
--
作者：
Joydeep Mukherjee;Priya Ranjan Sinha Mahapatra;Arindam Karmakar;Sandip Das
在本文中，我们确定了一个最小宽度的矩形环，它包围平面上给定的 n 个点集。我们针对这个问题提出了 O(n 2 log n) 时间和 O(n) 空间算法。据我们所知，这是第一个针对任意方向的矩形环的次立方算法。
In this paper, we identify a minimum width rectangular annulus that encloses a given set of n points in a plane. We propose an O (n 2 log n) time and O (n) space algorithm for this problem. To the best of our knowledge this is the first sub-cubic algorithm for a rectangular annulus for arbitrary orientation.