Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_1,\ldots,v_k$ so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the idle time, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al. (2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively.In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their algorithm ${\mathcal A}_2$ for unidirectional patrolling of a closed fence; (ii) we present a schedule with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.
7 April 2012 in The Electronic Journal of Combinatorics
Let $n \geq 4$ be even. It is shown that every set $S$ of $n$ points in the plane can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of $n$ straight-line edges such that the angle between any two consecutive edges is at most $2\pi/3$. For $n=4$ and $6$, this statement is tight. It is also shown that every even-element point set $S$ can be partitioned into at most two subsets, $S_1$ and $S_2$, each admitting a spanning tour with no angle larger than $\pi/2$. Fekete and Woeginger conjectured that for sufficiently large even $n$, every $n$-element set admits such a spanning tour. We confirm this conjecture for point sets in convex position. A much stronger result holds for large point sets randomly and uniformly selected from an open region bounded by finitely many rectifiable curves: for any $\epsilon>0$, these sets almost surely admit a spanning tour with no angle larger than $\epsilon$.
10 August 2010 in Discrete & Computational Geometry
We revisit some maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1995). Given a set of n points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching, (b) a Hamiltonian path, and (c) a spanning tree. We obtain some new results for (b) and (c), as well as for the Hamiltonian cycle problem. (i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio \(\frac{2}{\pi+1}\approx0.4829\). The previous best ratio, due to Alon et al., was \(\frac{1}{\pi }\approx0.3183\). The ratio of our algorithm is close to \(\frac{2}{\pi}\approx0.6366\) on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. For instance “random” point sets meet the condition with high probability. The algorithm runs in O(n7/3log n) time. (ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio 0.502 which runs in O(nlog n) time. The previous ratio, 1/2, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster algorithm and a very simple analysis. (iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to 2/π on a relatively broad class of instances: for point sets where the product 〈diameter×convex hull size〉 is much smaller than the maximum length matching. Again “random” point sets meet the condition with high probability. However, this algorithm does not come with a constant approximation guarantee for all instances. The algorithm runs in O(n7/3log n) time. No previous approximation results were known for this problem.