This paper studies a variant of the Art Gallery problem in which the ``walls" can be replaced by \emph{reflecting edges}, which allows the guards to see further and thereby see a larger portion of the gallery. Given a simple polygon $\cal P$, first, we consider one guard as a point viewer, and we intend to use reflection to add a certain amount of area to the visibility polygon of the guard. We study visibility with specular and diffuse reflections where the specular type of reflection is the mirror-like reflection, and in the diffuse type of reflection, the angle between the incident and reflected ray may assume all possible values between $0$ and $\pi$. Lee and Aggarwal already proved that several versions of the general Art Gallery problem are $NP$-hard. We show that several cases of adding an area to the visible area of a given point guard are $NP$-hard, too. Second, we assume all edges are reflectors, and we intend to decrease the minimum number of guards required to cover the whole gallery. Chao Xu proved that even considering $r$ specular reflections, one may need $\lfloor \frac{n}{3} \rfloor$ guards to cover the polygon. Let $r$ be the maximum number of reflections of a guard's visibility ray. In this work, we prove that considering $r$ \emph{diffuse} reflections, the minimum number of \emph{vertex or boundary} guards required to cover a given simple polygon $\cal P$ decreases to { $\bf \lceil \frac{\alpha}{1+ \lfloor \frac{r}{8} \rfloor} \rceil$}, where $\alpha$ indicates the minimum number of guards required to cover the polygon without reflection. We also generalize the $\mathcal{O}(\log n)$-approximation ratio algorithm of the vertex guarding problem to work in the presence of reflection.


翻译:本文研究了艺术馆问题的一种变体,在此变体中,“墙壁”可以由“反射边”代替,这使得守卫能够看得更远,从而看到更多的画廊部分。给定一个简单的多边形 $\cal P$,首先,我们考虑一个警卫作为一个点的观察者,并试图使用反射来增加警卫的可见性边界的一定面积。我们研究了具有镜面反射和漫反射性质的可见性,其中镜面反射类型为镜面反射,而在漫反射类型中,入射光线和反射光线之间的角度可能取 $0$ 到 $\pi$ 之间的所有可能值。Lee 和 Aggarwal 已经证明了一般艺术馆问题的几个版本是 $NP$-难的。我们证明添加到给定点警卫的可见面积的几种情况也是 $NP$-难的。其次,我们假设所有边都是反射器,并且我们打算减少所需的守卫最小数量以覆盖整个画廊。Chao Xu 证明了即使考虑 $r$ 个镜面反射,也可能需要 $\lfloor \frac{n}{3} \rfloor$ 个守卫来覆盖多边形。令 $r$ 为警卫的可见性光线的最大反射次数。在这项工作中,我们证明了,在考虑 $r$ 个漫反射反射的情况下,覆盖给定简单多边形 $\cal P$ 所需的最小顶点或边界守卫数量减少到 {$\bf \lceil \frac{\alpha}{1+ \lfloor \frac{r}{8} \rfloor} \rceil$},其中 $\alpha$ 表示不使用反射所需的最小守卫数量。同时,我们还将顶点守卫问题的 $\mathcal{O}(\log n)$ 近似比算法推广到存在反射的情况。

0
下载
关闭预览

相关内容

专知会员服务
25+阅读 · 2021年4月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
还在修改博士论文?这份《博士论文写作技巧》为你指南
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Code Smell 重构你的日常代码-圈复杂度高多层嵌套
阿里技术
1+阅读 · 2022年11月11日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月20日
Arxiv
0+阅读 · 2023年5月20日
VIP会员
相关VIP内容
相关资讯
Code Smell 重构你的日常代码-圈复杂度高多层嵌套
阿里技术
1+阅读 · 2022年11月11日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
相关基金
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员