首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Illumination in the presence of opaque line segments in the plane
Authors:Csaba D Tth
Institution:

Institut für Theoretische Informatik, ETH Zürich, CH-8092 Zürich, Switzerland

Abstract:What is the minimal number of light sources which is always sufficient to illuminate the plane in the presence of n disjoint opaque line segments? For ngreater-or-equal, slanted5, O'Rourke proved that left floor2n/3right floor light sources are always sufficient and sometimes necessary, if light sources can be placed on the line segments and thus they can illuminate both sides of a segment.

We prove that left floor2(n+1)/3right floor light sources are always sufficient and sometimes necessary, if light sources cannot be placed on the line segments. An O(nlogn) time algorithm is presented which allocates at most left floor2(n+1)/3right floor light sources collectively illuminating the plane.

Keywords:Art gallery  Planar graph  Matching
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号