A Proportion of Visibility Polygon’s Surface to the Entire Polygon’s Surface: A Lower Bound of the Proportion Derived for General Polygons of Any Shape and Orthogonal Polygons
摘要
Assuming a bounded non-empty polygon and a point either inside it or on its boundary, the visibility polygon, also known as the visibility region, represents the area within the polygon that can be seen directly from the point without crossing the polygon’s edges. Since the polygon is bounded, the visibility polygon is also bounded, and its surface area relative to the entire polygon’s surface can theoretically be calculated. Numerous studies explore the applications of visibility polygons in fields such as robotics and computer graphics, often focusing on efficient algorithms to determine the visibility region for a given polygon. However, it is surprising that there is little research on estimating the proportion of the visibility polygon’s area to the entire polygon’s area or defining bounds for this proportion. It is clear that the upper bound of this surface proportion depends significantly on the choice of the point, whether inside or on the boundary. For special cases, such as convex polygons, the upper bound is consistently 1, regardless of where the point is placed within or on the polygon’s edges. Therefore, this paper focuses on determining a lower bound for the surface proportion of the visibility polygon within a given polygon. For an n-sided simple polygon, which has no holes or intersecting edges, we apply the well-known art gallery problem and demonstrate that there is always a point inside or on the boundary of the polygon ensuring that the proportion of the point-associated visibility polygon’s area to the total area of the polygon is at least \(\frac{1}{\left\lfloor n / 3 \right\rfloor }\) . Furthermore, we demonstrate that there exist n-sided polygons for which this proportion does not exceed \(\frac{1}{\left\lfloor n / 3 \right\rfloor }\) for any point within or on the boundary. Consequently, the lower bound of \(\frac{1}{\left\lfloor n / 3 \right\rfloor }\) for this proportion cannot be improved in general. While these findings apply to general simple polygons, including orthogonal polygons, we specifically investigate the lower bound for n-sided orthogonal polygons, where the bound tends to increase. By leveraging the orthogonal art gallery problem, we demonstrate that there is always a point within or on the boundary of an orthogonal polygon for which the visibility polygon’s area is at least \(\frac{1}{\left\lfloor n / 4 \right\rfloor }\) of the total area. Finally, we present a family of n-sided orthogonal polygons for which no point within or on the boundary achieves a visibility polygon proportion greater than \(\frac{1}{\left\lfloor n / 4 \right\rfloor }\) . Thus, for orthogonal polygons, the lower bound of \(\frac{1}{\left\lfloor n / 4 \right\rfloor }\) for the visibility polygon’s surface proportion is close to optimal and, in general, cannot be significantly improved.