Computational Geometry: Theory and Applications
Computational Geometry: Theory and Applications
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Sang Won Bae;Chunseok Lee;Hee-Kap Ahn;Sunghee Choi;Kyung-Yong Chwa b
中科院分区：
文献类型：
--
作者：
Sang Won Bae;Chunseok Lee;Hee-Kap Ahn;Sunghee Choi;Kyung-Yong Chwa b
研究计算两个非凸包围形状最小面积的问题； L 形和直线凸包。给定平面上的一组 n 点，我们找到一个包含这些点的 L 形状或该点集的直线凸包，在所有方向上具有最小面积。我们证明，在旋转坐标系时，固定方向的最小包围形状最多会组合变化 O ( n ) 次。基于此，我们提出了有效的算法，可以在所有方向上以最小面积计算两种形状。该算法提供了一种在旋转坐标系时维护极值点集或楼梯的有效方法，并在 O ( n 2 ) 时间和 O ( n ) 空间中计算最小封闭形状。我们还表明，如果我们使用更多的空间，维护楼梯的时间复杂度可以得到改善。
We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull . Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O ( n ) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O ( n 2 ) time and O ( n ) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.