On the number of guard edges of a polygon |
| |
Authors: | Jung-Heum Park Sung Yong Shin Kyung-Yong Chwa Tony C Woo |
| |
Institution: | (1) Department of Computer Science, Korea Advanced Institute of Science and Technology, Kusong-dong 373-1, Yusong-ku, 305-701 Taejon, Republic of Korea;(2) Department of Industrial and Operations Engineering, University of Michigan, 48109 Ann Arbor, MI, USA |
| |
Abstract: | This paper establishes tight bounds on the number of edges of a polygon from which every point in the polygon is visible;
we call them guard edges. For a nonstarshaped polygon, there can be at most three guard edges. For a polygon with holes, there
may be at most six; three on the outer boundary and three on one of the holes. The results give new insights into the structure
of visibility in polygons and shed light on developing an efficient algorithm for finding all guard edges of a polygon with
or without holes.
This work was partially supported by the Korea Science and Engineering Foundation (Project No. 91-01-01). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|