
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Characterizing Link2 LRVisibility Polygons and Related Problems
Xuehou TAN Bo JIANG
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E102A
No.2
pp.423429 Publication Date: 2019/02/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E102.A.423
Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: computational geometry, visibility, nonredundant components, linkk 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 link2 visible if there exists the third point z ∈ P such that z is visible from both x and y. The polygon P is link2 LRvisible 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 link2 visible from some point of the other boundary of P from t to s and vice versa. We give a characterization of link2 LRvisibility polygons by generalizing the known result on LRvisibility polygons. A new idea is to extend the concepts of rayshootings and components to those under notion of link2 visibility. Then, we develop an O(n log n) time algorithm to determine whether a given polygon is link2 LRvisible. Using the characterization of link2 LRvisibility polygons, we further present an O(n log n) time algorithm for determining whether a polygonal region is searchable by a ksearcher, k ≥ 2. This improves upon the previous O(n^{2}) 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 ksearcher holds k flashlights and can see only along the rays of the flashlights emanating from his position.

