Characterizing Link-2 LR-Visibility Polygons and Related Problems

Xuehou TAN  Bo JIANG  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.2   pp.423-429
Publication Date: 2019/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.423
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
computational geometry,  visibility,  non-redundant components,  link-k visibility,  polygon search problem,  

Full Text: PDF(805KB)
>>Buy this Article


Summary: 
Two points x, y inside a simple polygon P are said to be mutually link-2 visible if there exists the third point zP such that z is visible from both x and y. The polygon P is link-2 LR-visible if there are two points s, t on the boundary of P such that every point on the clockwise boundary of P from s to t is link-2 visible from some point of the other boundary of P from t to s and vice versa. We give a characterization of link-2 LR-visibility polygons by generalizing the known result on LR-visibility polygons. A new idea is to extend the concepts of ray-shootings and components to those under notion of link-2 visibility. Then, we develop an O(n log n) time algorithm to determine whether a given polygon is link-2 LR-visible. Using the characterization of link-2 LR-visibility polygons, we further present an O(n log n) time algorithm for determining whether a polygonal region is searchable by a k-searcher, k ≥ 2. This improves upon the previous O(n2) time bound [9]. A polygonal region P is said to be searchable by a searcher if the searcher can detect (or see) an unpredictable intruder inside the region, no matter how fast the intruder moves. A k-searcher holds k flashlights and can see only along the rays of the flashlights emanating from his position.