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 cost 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 about 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 true 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.

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

VC-Dimension of Visibility Polygons

The VC-dimension (named after Vapnik and Chernovenkis) is defined to be the maximal cardinality of objects that can be “shattered” by regions in a general domain D. Shattering of a set of objects S means that any subset of S is exactly covered by one region R of D. For a simple polygon P the objects are points in P, the regions are all possible visiblity polygons in P and the domain is P itself. Thus, we are searching for a maximal set S of points in an arbitrary P such that any subset of S is precisely covered by a visibilty polygon in P. There is an example by Pavel Valtr that shows that 6 point can be shattered, which means that there is a special polygon with 6 points inside and for any of the 2^6=64 subsets of the 6 points there is a point in P that precisely sees the corresponding subset. On the other hand there is a result that shows that no more than 14 points can be shattered in general. So there is still a gap between 6 and 14 for the precise cardinality of the VC-dimension. The VC-dimension has impact on the number of guards which are necessary to cover a given domain, this is a direct consequence from the \epsilon-Net Theorem. We have made some attempts and we were able to prove that the VC-dimension is exactly 5, if we change the visibility from L_2 to L_1 visibility. The key idea of the proof is that we do not need all subsets and that the boundary of the changing visibility regions are important. We would like to make use of these ideas for letting the interval [6,14] shrink.

• Guarding galleries where no point sees a small area, 1998
• A new upper bound for the VC-dimension of visibility regions, 2011
• The exact VC-Dimension for L_1 visibility in simple polygons, 2019

Geometric Fire Fighting in the plane

Let us assume that a fire expands in the plane from a given starting point with unit speed. On the other hand geometric fire figthers can build barriers everyhere in the plane with some speed t. For the fire figthers it is allowed that they separate the total speed among each other and it is also allowed to build the barriers everywhere without extra cost for jumping to the start. If a barrier is constructed and the fire hits the barrier, the barrier appears to be an obstacle that avoids the fire from free movement, so the barrier prevents the fire to expand arbitarily. The challenging question is, what is the minimim speed such that the fire fighters will be able to enclose and stop the fire. There is a simple argument that a speed of t=2+\epsilon is always sufficient by choosing two spiral paths along the boundary of the fire. Additionally, one can show that with speed t=1, it is impossible to enclose an expanding fire. An overall interesting question is, whether it makes sense to construct blocking barriers that are not connected to the outer boundary of the final enclosing construction. There is still this blind interval for t=(1,2].

• Dynamic blocking problems for a model of fire propagation, 2013
• On a Fire Fighter's Problem, 2019
• Geometric firefighting in the half-plane, 2021

Optimality of spiral search

Let us assume that starting from a position s we are searching for a line l in the plan without knowledge about the location of l. In comparison to the know shortest path to the line, which is just a segment s_l from s to l that is perpendicular to l, we are searching for a path that finally hits the line and whose path length is bounded by C times the length of s_l independently of the position of l. We are searching for the best strategic movement that guarantees the minimal C in the overall worst-case. It is an old open conjecture that a spiral path is an optimal strategy and the best spiral attains a factor C=13.811… We have some experience for the lower bound constructions for such strategies and would like to use them. A critical question is, whether it is allowed to search for strategies that behave in a monotone and periodic way. A first task then is, that among those strategies, a spiral is optimal.

• On the linear search problem, 1964
• Searching in the plane, 1993
• On the optimality of spiral search, 2010
• Optimal online escape path against a certificate, 2016
• On the approximation of shortest escape paths, 2021

Anchored Rectangle Problem

Given an axis-parallel unit square U and a set S of n points inside U, it is allowed to span an anchored axis parallel rectangle R_i for each point p_i of S inside U such that p_i is the lower left corner. For the overall anchored spanning all rectangles have to be disjoint which also means that no p_j lies inside a R_i. The conjecture is that for any point set S inside U, such that S at least contains the lower left corner of U, there exists a spanning, such that at least half of the interior of U can be covered. This conjecture is open for over 50 years. Our aim is to first find similar slightly extended versions such that a similar conjecture holds and that will lead us to an improvement to the best current known covering results. For the general problem, there is an example such that no more than half of the coverage of U can be attained. On the other hand there is a result that states that there are always solutions that cover at least roughly 10 percent of U. So there is still a huge gap that has to be closed.

• The anchored rectangle problem, Allan Freedman 1960
• Packing anchored rectangles, 2015
• Anchored Rectangle and Square Packings, 2016