In the original art gallery problem, there is a non-convex area provided and one has to divide it into regions based on infinite visibility of guards. We assume an unlimited number of guards. However, suppose we only have n number of guards with limited visibility. Then how to divide the area in a balanced way meaning each guard gets roughly same size of area to guard. What kind of algos have been developed in this area till now?

  • 1
    $\begingroup$ If some grid cell is visible to two or more guards, who is it assigned to? $\endgroup$ – j_random_hacker Oct 6 '16 at 11:23
  • $\begingroup$ That is where i wish to use balancing. If guard X already has more grid cells to guard, then another guard Y should get the conflicting grid cell. If there is a tie, then either assign the conflicting grid cell to guard nearer in some sense or randomly assign. $\endgroup$ – user_1_1_1 Oct 6 '16 at 21:48
  • $\begingroup$ You can view this as covering grid points with $n$ (equal-size?) circles. The first issue is that the problem may have no solution, if $n$ (or the visibility radius) is too small to cover all points. $\endgroup$ – j_random_hacker Oct 7 '16 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.