An Efficient Algorithm for Finding the Visibility Polygon for a Polygonal Region with Holes
Summary :
We are given a polygonal region P with holes and one point q is specified in the region. The problem is how fast we can find the portion of the boundary of P that is visible from q. For this problem an efficient algorithm is presented which runs in time O(n log h) in the worst case and in time O(n+h log h) if every hole is a convex polygon, where n is the total number of vertices of P and h is the number of holes.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E68-E No.9 pp.557-559
- Publication Date
- 1985/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Data Processing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Tetsuo ASANO, "An Efficient Algorithm for Finding the Visibility Polygon for a Polygonal Region with Holes" in IEICE TRANSACTIONS on transactions,
vol. E68-E, no. 9, pp. 557-559, September 1985, doi: .
Abstract: We are given a polygonal region P with holes and one point q is specified in the region. The problem is how fast we can find the portion of the boundary of P that is visible from q. For this problem an efficient algorithm is presented which runs in time O(n log h) in the worst case and in time O(n+h log h) if every hole is a convex polygon, where n is the total number of vertices of P and h is the number of holes.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e68-e_9_557/_p
Copy
@ARTICLE{e68-e_9_557,
author={Tetsuo ASANO, },
journal={IEICE TRANSACTIONS on transactions},
title={An Efficient Algorithm for Finding the Visibility Polygon for a Polygonal Region with Holes},
year={1985},
volume={E68-E},
number={9},
pages={557-559},
abstract={We are given a polygonal region P with holes and one point q is specified in the region. The problem is how fast we can find the portion of the boundary of P that is visible from q. For this problem an efficient algorithm is presented which runs in time O(n log h) in the worst case and in time O(n+h log h) if every hole is a convex polygon, where n is the total number of vertices of P and h is the number of holes.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - An Efficient Algorithm for Finding the Visibility Polygon for a Polygonal Region with Holes
T2 - IEICE TRANSACTIONS on transactions
SP - 557
EP - 559
AU - Tetsuo ASANO
PY - 1985
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E68-E
IS - 9
JA - IEICE TRANSACTIONS on transactions
Y1 - September 1985
AB - We are given a polygonal region P with holes and one point q is specified in the region. The problem is how fast we can find the portion of the boundary of P that is visible from q. For this problem an efficient algorithm is presented which runs in time O(n log h) in the worst case and in time O(n+h log h) if every hole is a convex polygon, where n is the total number of vertices of P and h is the number of holes.
ER -
English
