Given a set S of regions with piece-wise linear boundary and a positive angle α < 90°, we consider the problem of computing the locations and orientations of the minimum number of α-floodlights positioned at points in S which suffice to illuminate the entire x-axis. We show that the problem can be solved in O(n log n) time and O(n) space, where n is the number of vertices of the set S.

We revisit the problem of pursuit-evasion in a grid introduced by Sugihara and Suzuki [SIAM J. Discrete Math., 2 (1989), pp. 126–143] in the line-of-sight vision model. Consider an arbitrary evader Z with the maximum speed of 1 who moves (in a continuous way) on the streets and avenues of an $n\times n$ grid $G_n$. The cunning evader is to be captured by a group of pursuers, possibly only one. The maximum speed of the pursuers is $s\geq1$; s is a constant for each pursuit-evasion problem considered, but several values for s are studied. We prove several new results (no such algorithms were available for capture using one, two, or three pursuers having a constant maximum speed limit): (i) A randomized algorithm through which one pursuer A with a maximum speed of $s\geq3$ can capture an arbitrary evader Z in $G_n$ in expected polynomial time. For instance, the expected capture time is $O(n^{1+\log_{6/5}16})=O(n^{16.21})$ for $s=3$, $O(n^{1+\log12})=O(n^{4.59})$ for $s=4$, $O(n^{1+\log60/13})=O(n^{3.21})$ for $s=6$, and it approaches $O(n^3)$ with the further increase of s. (ii) A randomized algorithm for capturing an arbitrary evader in $O(n^3)$ expected time using two pursuers who can move slightly faster than the evader ($s=1+\varepsilon$ for any $\varepsilon>0$). (iii) Randomized algorithms for capturing a certain “passive” evader using either a single pursuer who can move slightly faster than the evader ($s=1+\varepsilon$ for any $\varepsilon>0$) or two pursuers having the same maximum speed as the evader ($s=1$). (iv) A deterministic algorithm for capturing an arbitrary evader in $O(n^2)$ time, using three pursuers having the same maximum speed as the evader ($s=1$).

Consider the following survival problem:Given a set of k trajectories (paths) with maximum unit speed in a boundedregion over a (long) time interval [0,T], find another trajectory (if itexists) subject to the same maximum unit speed limit, that avoids (that is, stays at a safe distance of)each of the other trajectories over the entire time interval. We call this variant the continuous model of the survival problem. The discrete model of this problem is: Given the trajectories (paths) of k point robots in a graph over a (long)time interval 0,1,2,...,T, find a trajectory (path) for anotherrobot, that avoids each of the other k at any time instance in thegiven time interval. We introduce the notions of survival number of a region,and that of a graph, respectively, as the maximum number oftrajectories which can be avoided in the region (resp. graph). We give the first estimates on the survival number of the n x n grid Gn, and also devise an efficient algorithm for the corresponding safepath planning problem in arbitrary graphs. We then show that our estimates on the survival number of Gn%on the number of paths that can be avoided in Gn can be extended for the survival number of a bounded (square) region.In the final part of our paper, we consider other related offlinequestions, such as the maximum number of men problem and the spy problem.