4. In the art gallery guarding problem we are given a straight line L that represents a long hallway in an art gallery.

[answerhappygod]

4 In The Art Gallery Guarding Problem We Are Given A Straight Line L That Represents A Long Hallway In An Art Gallery 1 (33.07 KiB) Viewed 32 times

4. In the art gallery guarding problem we are given a straight line L that represents a long hallway in an art gallery. We are also given a set X = {x₁,x₂,...,xn) of real numbers that specify the positions of paintings in this hallway. Suppose that a single guard can protect all the paintings within distance at most 1 of his position on both sides. Design a polynomial-time algorithm for finding a placement of guards that uses the minimum number of guards to protect all the paintings with positions in X. A guard can be placed at any real number position in the hallway. Analyze the running time and show the correctness of your algorithm.