Illuminate: provably good algorithms for guarding problems

In the project “Illuminate: provably good algorithms for guarding problems” we study visibility based problems--specifically those, where several stationary or mobile guards need to monitor each point of a domain.

These problems play a larger role in an increasing number of applications (e.g., surveillance, illumination and domain covering, and also in manufacturing) and are known to be computationally hard to solve in general. Hence, finding efficient ways to approximate them is important.

We consider restricted polygonal domains with the goal to obtain efficient optimal solutions or better approximate solutions than those known for simple polygons.Also we will study k-transmitters: modems that can connect to “see” another device that is obstructed by at most k walls.

If all points of an environment need to frequently connect to a k-transmitter, we want to find the shortest tour for the transmitter that allows for these connections.We focus on the design and analysis of algorithms and study the problems´ computational complexity; their basic geometric properties, structures and worst-case combinatorial bounds provide insights on the construction of solutions.

The research in the 4-year project is driven by the applicant Professor B. J. Nilsson,  Docent. C . Schmidt, and a PhD student. Research progress is disseminated through participation at international conferences and publication in journals.