Multiple point visibility and related problems

Abstract

If a point p is visible from m distinct points, the point p is said to be m-visible. For a simple polygonal shape art gallery P, it is shown that the minimum number of guards required for P to be m-visible is either 2(m−1)+1 or 3(m−1)+1 if P is a star-shaped polygon with the property that P is visible from only a boundary point. For any simple polygon with n vertices, it is also shown that the [n/3] × m guards are occasionally necessary and always sufficient. The algorithms to locate the determined guards on the given gallery (or polygon) are also presented.

Keywords:

• Computational geometry
• Art gallery problem
• Multiple point visibility

C.R.Categories:

• F.2.2
• I.3.5