The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Deux points x, y à l'intérieur d'un simple polygone P sont dits mutuellement lien-2 visible s'il existe le troisième point z ∈ P tel que z est visible des deux x et y. Le polygone P is lien-2 LR-visible s'il y a deux points s, t à la frontière de P de telle sorte que chaque point sur la limite dans le sens des aiguilles d'une montre de P du s à t le lien-2 est-il visible depuis un certain point de l'autre limite de P du t à s et vice versa. Nous donnons une caractérisation du lien-2 LR-polygones de visibilité en généralisant le résultat connu sur LR-polygones de visibilité. Une nouvelle idée est d'étendre les concepts de tirs de rayons et de composants à ceux de la notion de visibilité lien-2. Ensuite, nous développons un O(n enregistrer n) algorithme temporel pour déterminer si un polygone donné est lien-2 LR-visible. Utilisation de la caractérisation du lien-2 LR-polygones de visibilité, nous présentons en outre un O(n enregistrer n) algorithme temporel pour déterminer si une région polygonale peut être recherchée par un k-chercheur, k ≥ 2. Ceci améliore le précédent O(n2) limité dans le temps [9]. Une région polygonale P est dit être interrogeable par un chercheur si le chercheur peut détecter (ou voir) un imprévisible intrus à l’intérieur de la région, quelle que soit la vitesse à laquelle l’intrus se déplace. UN k-chercheur détient k lampes de poche et ne peut voir que le long des rayons des lampes de poche émanant de sa position.
Xuehou TAN
Tokai University
Bo JIANG
Dalian Maritime University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Xuehou TAN, Bo JIANG, "Characterizing Link-2 LR-Visibility Polygons and Related Problems" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 2, pp. 423-429, February 2019, doi: 10.1587/transfun.E102.A.423.
Abstract: Two points x, y inside a simple polygon P are said to be mutually link-2 visible if there exists the third point z ∈ P 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.423/_p
Copier
@ARTICLE{e102-a_2_423,
author={Xuehou TAN, Bo JIANG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Characterizing Link-2 LR-Visibility Polygons and Related Problems},
year={2019},
volume={E102-A},
number={2},
pages={423-429},
abstract={Two points x, y inside a simple polygon P are said to be mutually link-2 visible if there exists the third point z ∈ P 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.},
keywords={},
doi={10.1587/transfun.E102.A.423},
ISSN={1745-1337},
month={February},}
Copier
TY - JOUR
TI - Characterizing Link-2 LR-Visibility Polygons and Related Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 423
EP - 429
AU - Xuehou TAN
AU - Bo JIANG
PY - 2019
DO - 10.1587/transfun.E102.A.423
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2019
AB - Two points x, y inside a simple polygon P are said to be mutually link-2 visible if there exists the third point z ∈ P 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.
ER -