Maximize area of light with 4 light sources on a diagram of a room

Question

Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized.

Here is a simple example diagram so the problem can be better understood:

The solution I thought was to find the spot with most light and from there find the second one and so on. But something makes me think that it may exist a configuration which is better that doesn't need to be the best from the beginning, kinda feels like a special case of the knapsack problem, if so I'd think of implementing a greedy algorithm or using genetic algorithms to give an approximation of the best places.

The problem could be viewed as a particular case of "the Art gallery problem" but instead of finding the least amount of guards, you have 4 guards and you have to put them in certain places so they can observe the most area of the gallery possible.

I'd be grateful if at least someone points me in the right direction so I can do a better research, thank you very much!

Answer 1

This is an optimization problem, where a function $f: \Bbb R^8 \rightarrow \Bbb R$ is defined as an area of the visibility polygon, corresponding to four points, situated inside a polygon with holes. So, your research should go in two directions:

1. Global optimization - a branch of numerical analysis, that deals with various iterative algorithms, able to find an argument of the optimized function, giving its minimum or maximum value over all the function domain. Sometimes the global optimization problem is solved as a sequence of local optimizations (with random starting points), however in general case there are no guarantee that the optimal solution will be found by this method. Please see this paper, where authors apply the Gradient descent method to maximize the area of the region, visible to the observer in a simple polygon (without holes).

2. Visibility polygon for a point $p$ in the plane configuration with possible boundary and obstacles is the polygonal region $V(p)$ of all points of the plane visible from the p. You'll need to compute visibility polygons many times for different points, so it makes sense to pre-process the original polygon (together with its holes) to make this computation faster. Please see this paper, where authors do exactly that - their approach needs $O(n^3log(n))$ pre-processing time, and it allows to compute the visibility polygon with $k$ vertices in $O((1+min(h,k))log(n)+k)$ time, where $h$ is the number of holes. The visibility polygon for four points will be a union of four visibility polygons (and this union can have holes) - so you'll need to compute this union. Please see Boolean operation on polygons as a starting point for your research as well.

Optimization problems on real numbers are intrinsically inexact and their solutions are approximations - the question is how close your solution should be to the optimal one. The gradient descent method might be enough in your case, where the bounding polygon is simply a rectangle, and holes also have simple shape.