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


A linear worst-case lower bound on the number of holes inside regions visible due to multiple diffuse reflections
Authors:Siddhartha Brahma  Sudebkumar Prasant Pal  Dilip Sarkar
Institution:(1) Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, 721302, India;(2) Department of Computer Science, University of Miami, Coral Gables, Miami, FL 33124, USA
Abstract:It is known that the region V(s) of a simple polygon P, directly visible (illuminable) from an internal point s, is simply connected. Aronov et al. 2] established that the region V1(s) of a simple polygon visible from an internal point s due to at most one diffuse reflection on the boundary of the polygon P, is also simply connected. In this paper we establish that the region V2(s), visible from s due to at most two diffuse reflections may be multiply connected; we demonstrate the construction of an n-sided simple polygon with a point s inside it so that the region of P visible from s after at most two diffuse reflections is multiply connected. We also show that V3(s), the region of P visible from s after at most three diffuse reflections, can have OHgr(n) holes.A part of this work was done when this author was visiting the University of Miami, Coral Gables, Florida, USA.
Keywords:52C45  68U05
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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