Stabbing segments with rectilinear objects
Stabbing segments with rectilinear objects
复制标题
用直线物体刺穿线段
DOI：
10.1016/j.amc.2017.04.001
复制
发表时间：
2017
影响因子：
4
通讯作者：
Silveira Rodrigo I.
中科院分区：
文献类型：
--
作者：
Claverol Merce;Garijo Delia;Korman Matias;Seara Carlos;Silveira Rodrigo I.
给定平面中 n 条线段的集合 S，如果 R 恰好包含 S 的每段线段的一个端点，我们就说区域 R⊆ R 2 是 S 的刺入点。在本文中，我们提供了最佳或接近最优的算法来报告几种形状的刺入点的所有组合不同的刺入点。具体来说，我们考虑刺刺可以被描述为轴平行半平面的交集的情况（因此刺伤是半平面、条带、象限、三边矩形或矩形）。运行时间为 O (n)（对于半平面情况）、O (nlog n)（对于条带、象限和三边矩形）和 O (n 2 log n)（对于矩形）。
Given a set S of n line segments in the plane, we say that a region R⊆ R 2 is a stabber for S if R contains exactly one endpoint of each segment of S. In this paper we provide optimal or near-optimal algorithms for reporting all combinatorially different stabbers for several shapes of stabbers. Specifically, we consider the case in which the stabber can be described as the intersection of axis-parallel halfplanes (thus the stabbers are halfplanes, strips, quadrants, 3-sided rectangles, or rectangles). The running times are O (n)(for the halfplane case), O (nlog n)(for strips, quadrants, and 3-sided rectangles), and O (n 2 log n)(for rectangles).