This paper discusses the problem of covering and hitting a set of linesegments $cal L$ in ${mathbb R}^2$ by a pair of axis-parallel squares suchthat the side length of the larger of the two squares is minimized. We alsodiscuss the restricted version of covering, where each line segment in $cal L$is to be covered completely by at least one square. The proposed algorithm forthe covering problem reports the optimum result by executing only two passes ofreading the input data sequentially. The algorithm proposed for the hitting andrestricted covering problems produces optimum result in $O(n)$ time. All theproposed algorithms are in-place, and they use only $O(1)$ extra space. Thesolution of these problems also give a $sqrt{2}$ approximation for coveringand hitting those line segments $cal L$ by two congruent disks of minimumradius with same computational complexity.
展开▼
机译：本文讨论了覆盖和击中一组Linesegments $ Cal L $的问题$ { mathbb r} ^ 2 $ by一对轴并联正方形，这两个方格的侧面长度最小化。我们alsodiscuss覆盖的受限制版本，其中每条线路段在$ cal l $的情况下由至少一个平方根完全覆盖。所提出的算法在覆盖问题上，通过仅顺序地执行两个传递输入数据来报告最佳结果。为击中AndRestRicted覆盖问题提出的算法在$ O（n）$时间中产生最佳结果。所有的算法都是原位的，它们仅使用$ o（1）$额外的空间。这些问题的选择也给出了一个$ sqrt {2} $近似为覆盖物和击中那些线段$ cal l $ cal l $ cal l $ cal l $ cal l $的两个总是具有相同的计算复杂性的最小值圆盘。
展开▼
