• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Computational Science and Its Applications - ICCSA 2003 Pt.3 May 18-21, 2003 Montreal, Canada >Connected Guards in Orthogonal Art Galleries
【24h】

Connected Guards in Orthogonal Art Galleries

机译：正交美术馆中的守卫

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper we consider a variation of the Art Gallery Problem for orthogonal polygons. A set of points G in a polygon P_n is a connected guard set for P_n provided that is a guard set and the visibility graph of the set of guards G in P_n is connected. The polygon P_n is orthogonal provided each interior angle is 90 ° or 270 °. First we use a coloring argument to prove that the minimum number of connected guards which are necessary to watch any orthogonal polygon with n sides is n/2 ― 2. This result was originally established by induction by Hernandez-Penalver. Then we prove a new result for art galleries with holes: we show that n/2 ― h connected guards are always sufficient to watch an orthogonal art gallery with n walls and h holes. This result is sharp when n = 4h + 4. We also construct galleries that require at least n/2 ― h ― 1 connected guards, for all n and h.
机译：在本文中，我们考虑了正交多边形的“画廊问题”的一种变体。多边形P_n中的一组点G是用于P_n的连接的保护组，只要该保护组是保护组，并且连接P_n中的保护组G的可见性图即可。如果每个内角为90°或270°，则多边形P_n是正交的。首先，我们使用一个着色论证来证明观察具有n个边的任何正交多边形所需的最小连接保护数为n / 2〜2。该结果最初是由Hernandez-Penalver归纳得出的。然后，我们证明了带孔画廊的新结果：我们证明，n / 2-h个相连的门卫总是足以观看带有n个壁和h个孔的正交画廊。当n = 4h + 4时，此结果非常明显。对于所有n和h，我们还构建了至少需要n / 2-h-1个相连的门卫的画廊。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号