首页> 外文期刊>Algorithmica >Stabbing Circles for Sets of Segments in the Plane
【24h】

Stabbing Circles for Sets of Segments in the Plane

机译:平面中各段线段的刺圆

获取原文
获取原文并翻译 | 示例

摘要

Stabbing a set S of n segments in the plane by a line is a well-known problem. In this paper we consider the variation where the stabbing object is a circle instead of a line. We show that the problem is tightly connected to two cluster Voronoi diagrams, in particular, the Hausdorff and the farthest-color Voronoi diagram. Based on these diagrams, we provide a method to compute a representation of all the combinatorially different stabbing circles for S, and the stabbing circles with maximum and minimum radius. We give conditions under which our method is fast. These conditions are satisfied if the segments in S are parallel, resulting in a time and O(n) space algorithm. We also observe that the stabbing circle problem for S can be solved in worst-case optimal time and space by reducing the problem to computing the stabbing planes for a set of segments in 3D. Finally we show that the problem of computing the stabbing circle of minimum radius for a set of n parallel segments of equal length has an lower bound.
机译:用一条线刺入平面中的n个段的集合S是一个众所周知的问题。在本文中,我们考虑了刺伤对象是圆形而不是直线的变化形式。我们表明问题与两个簇Voronoi图紧密相关,特别是Hausdorff图和最远颜色的Voronoi图。基于这些图,我们提供了一种方法来计算S的所有组合不同的刺圆以及具有最大和最小半径的刺圆的表示。我们给出了我们的方法快速的条​​件。如果S中的段平行,则满足这些条件,从而产生时间和O(n)空间算法。我们还观察到,通过在3D中为一组线段计算刺伤平面的问题,可以在最坏情况下的最佳时间和空间解决S的刺伤圆问题。最后,我们证明了为一组等长的n个平行段计算最小半径的刺圆的问题具有一个下界。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号