• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International computing and combinatorics conference >Optimal Covering and Hitting of Line Segments by Two Axis-Parallel Squares
【24h】

Optimal Covering and Hitting of Line Segments by Two Axis-Parallel Squares

机译：两个轴平行正方形的最优线段覆盖和击中

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper discusses the problem of covering and hitting a set of line segments L in R~2 by a pair of axis-parallel squares such that the side length of the larger of the two squares is minimized. We also discuss the restricted version of covering, where each line segment in L is to be covered completely by at least one square. The proposed algorithm for the covering problem reports the optimum result by executing only two passes of reading the input data sequentially. The algorithm proposed for the hitting and restricted covering problems produces optimum result in O(n log n) time. All the proposed algorithms are in-place, and they use only O(1) extra space. The solution of these problems also give a √2 approximation for covering and hitting those line segments L by two congruent disks of minimum radius with same computational complexity.
机译：本文讨论了用一对平行轴覆盖并敲击R〜2中的一组线段L的问题，以使两个正方形中较大的一个的边长最小。我们还将讨论覆盖的限制版本，其中L中的每个线段均应至少被一个正方形完全覆盖。所提出的覆盖问题算法通过仅顺序执行两次读取输入数据的过程来报告最佳结果。提出的针对命中和受限覆盖问题的算法可在O（n log n）时间内产生最佳结果。所有提出的算法都是就地的，并且它们仅使用O（1）额外的空间。这些问题的解决方案还给出了一个√2近似值，以用相同的计算复杂度用两个最小半径的全等圆盘覆盖并击中这些线段L。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号