Art Gallery Theorem with Holes

[JasonJo]

Hey guys, my professor recently posed the problem of finding a simple Fisk like proof for the Art Gallery Theorem with holes:

it says that's to guard a polygon with n vertices and h holes, we will always need at most floor[(n+h)/3] where floor represents the floor function.

now i saw some proofs, some used induction, others used the fact that we can split one of the hole vertices into 2 vertices and build channels, eliminating the hole and creating h vertices, so we would be left with a polygon with n+h vertices, and then we just apply the regular Art Gallery Theorem.

however, I am trying to prove this theorem without using any perturbations.

i'm just wondering if any of you guys have tried to solve this or have encountered a similar type problem in your studies, whatever studies it may be.

 

[mighty2000]

Hello! Thank you for bringing up this interesting problem. As a fellow scientist, I have also encountered the Art Gallery Theorem in my studies. In fact, I have been working on a similar problem recently and have some insights to share with you.

Firstly, I agree with your professor's statement that we will always need at most floor[(n+h)/3] guards to guard a polygon with n vertices and h holes. This is a well-known result in the field of computational geometry and has been proven using various techniques, including the ones you mentioned (induction and perturbations).

However, I understand your desire to prove this theorem without using any perturbations. In fact, I believe that there is a simpler and more intuitive proof that does not involve any perturbations. The key idea is to use the concept of visibility polygons.

A visibility polygon is a polygon that represents the area that can be seen from a single point inside a polygon. By placing guards at strategic points inside the polygon, we can ensure that every point in the polygon is covered by at least one guard's visibility polygon.

Now, let's consider a polygon with n vertices and h holes. We can divide this polygon into smaller polygons by connecting the holes to the outer boundary. This creates n+h smaller polygons, each of which can be guarded by at most floor[(n+h)/3] guards using the regular Art Gallery Theorem.

Next, we place guards at the center of each of these smaller polygons. This ensures that every point in the original polygon is covered by at least one guard's visibility polygon. Therefore, we only need floor[(n+h)/3] guards to guard the entire polygon with n vertices and h holes.

I hope this explanation helps you in your quest to prove the Art Gallery Theorem without using perturbations. I believe that this approach provides a simpler and more intuitive proof. Good luck with your studies!