Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results
Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results
复制标题
使用滑动相机守卫正交艺术画廊：算法和硬度结果
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Mehrabi
中科院分区：
文献类型：
--
作者：
Stephane Durocher;S. Mehrabi
设 P 为正交多边形。考虑一个滑动相机，它沿着正交线段 s ⊆ P 作为其轨迹来回移动。如果存在点 q ∈ s，使得 pq 是完全包含在 P 中的垂直于 s 的线段，则相机可以看到点 p ∈ P。在最小基数滑动相机问题中，目标是找到一组最小基数的滑动相机来保护 P（即，P 中的每个点都可以被 S 中的某个滑动相机看到），而在最小长度滑动相机问题中，目标是找到这样一个集合 S，以便最小化S 中摄像机的移动轨迹。
Let P be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment s ⊆ P as its trajectory. The camera can see a point p ∈ P if there exists a point q ∈ s such that pq is a line segment normal to s that is completely contained in P. In the minimum-cardinality sliding cameras problem, the objective is to find a set S of sliding cameras of minimum cardinality to guard P (i.e., every point in P can be seen by some sliding camera in S) while in the minimum-length sliding cameras problem the goal is to find such a set S so as to minimize the total length of trajectories along which the cameras in S travel.