Pursuit-Evasion Voronoi Diagrams in ell_1

We are given m pursuers and one evader. Each pursuer and the evader has an associated starting point in the plane, a maximum speed, and a start time. We also have a set of line segment obstacles with a total of n endpoints. Our task is to find those points in the plane, called the evader´s region, that the evader can reach via evasive paths. A path is evasive if the evader can traverse the path from its starting point without encountering a pursuer along the way. The evader and the pursuers must obey their start time and speed constraints, and cannot go through obstacles. The partition of the plane into the evader´s region and the remaining pursuers´ region is called the pursuit-evasion Voronoi diagram. We study pursuit-evasion Voronoi diagrams for the lscr₁ metric. We show that the complexity of the diagram is O((n + m)²(mn + m)) and that it can be calculated in polynomial time.