|
|||||
|
|
A linear-time algorithm for constructing a circular visibility diagram |
|
| Authors: | Shuo-Yan Chou T. C. Woo |
| Affiliation: | (1) Department of Industrial Management, National Taiwan Institute of Technology, 43 Keelung Road, Section 4, Taipei, Taiwan;(2) Department of Industrial and Operations Engineering, University of Michigan, 48109-2117 Ann Arbor, MI, USA |
| Abstract: | To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of circular arcs by their centers results in a planar partition called the circular visibility diagram. AnO(n) algorithm is given for constructing the circular visibility diagram for a simple polygon withn vertices. |
| Keywords: | Computational geometry Circular visibility Planar partition Trapezoidal decomposition Point visibility Simple polygon Amortized |
| 本文献已被 SpringerLink 等数据库收录！ | |