There are some geometric questions or conjectures that have attracted a lot of attention but up to now there is no final answer. The overall aim is to consider interesting related problems that might lead to a general solution of the problems.

Surveillance Route Problems

Traditional optimal watchman or exploration routes consider the problem of computing the shortest path that sees or visits all objects of a given environment along a shortest roundtrip. For a surveillance approach it is more important that the time period where a certain object is not under vision or control has to be short. Thus we are searching for example for consecutive round trips such that among all important objects the maximal time period where the object is not under vision or control has to be minimized. Obviously this is a min-max optimization problem but also other cost measures under the surveillanve aspect are relevant. Whereas for the Shortest Watchman Route problem there are many variants where the structure of the optimal round trip is known and where the optimal path can also be computed in polynomial time much less is known for this concept of optimal surveillance routes. For example the shortest watchman route (SWR) inside a simple polygon can be computed in O(n^3 \log n) time for a polygon with n egdes. A first prominent conjecture was, that the SWR is also the best min-max surveillance route (SSR) but there are special counterexamples which show that this is not the case in general. Some attempts have been made (also by ourself) regarding the hardness of surveillance route problems for discrete cases and under weights for the objects and also for special cases where the environment is restricted. Many almost simple questions are still open. For example how to compute the best surveillance single roundtrip in a simple polygon? There is a need for a geometric concept that expresses and incorporates the surveillance cost.

• Discrete Surveillance Tours in Polygonal Domains, CCCG 2017
• Inspecting a set of strips optimally, WADS 2009
• Touring a sequence of polygons, STOC 2003
• Shortest Watchman Routes, (different sources)