We study the problem of multiple anchored watchman routes, where we are given m starting points for watchmen, and aim to find routes for all watchmen such that all points in a polygon are visible from at least one route. We consider the problem in Minbar polygons,2 which are staircase polygons for which the floor of the staircase solely consists of one horizontal and one vertical edge, and in generalized Minbar polygons, which relaxes the definition of Minbar polygons, allowing for non-rectilinear edges. For Minbar polygons, we exhibit polynomial time algorithms to compute optimal solutions for both the min-max and the min-sum criteria. The min-max algorithm takes O(mlog⁡m+nlog⁡n) time, using O(m+n) storage, and the min-sum algorithm takes O(n2log⁡m+mlog⁡m) time, also using O(m+n) storage. For generalized Minbar polygons, we prove NP-hardness for the min-sum and min-max criteria, and present approximation algorithms for both criteria: an O(log⁡(m+n))-approximation taking O(m4n2) time for the min-sum criterion, and a (π+3)-approximation taking O(m3n2) time for the min-max criterion. Minbar polygons and the non-rectilinear generalization of them may seem to be very restricted polygon classes but they form an adjacent pair where the multiple anchored watchman routes problem has a polynomial time solution in one class but is NP-hard in the slightly more generalized class. It is this property that motivates our study of these restricted polygon classes.

We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2×2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3×3 block of cells) for all k∈N.

We show an asymptotic 2/3-competitive strategy for the bin covering problem using O(b + log n) bits of advice, where b is the number of bits used to encode a rational value and n is the length of the input sequence.

We consider a variant of the 2-watchmen problem that ensures that every point in a polygon P is seen from more than one direction: we search for routes W1, W2, such that for each p ∈ P there exist w1 ∈ W1, w2 ∈ W2 that see p and such that p ∈ w1w2 ⊂ P. We show that finding the two routes that are optimal with respect to the min-max criterion is NP-hard in simple polygons and present a 2-approximation algorithm for this case; moreover, we provide a polynomial-time algorithm for computing the two optimal routes with respect to the min-sum criterion in convex polygons. Finally, we discuss a generalized version of the problem with more than two watchmen.

We consider the watchman route problem for multiple watchmen in staircase polygons, which are rectilinear x- and y-monotone polygons. For two watchmen, we propose an optimal algorithm that takes quadratic time, improving on the cubic time of the trivial solution. For m ≥ 3 watchmen, we explain where our approach fails.

The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times O ( n 8 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>8)$$\end{document} and O ( n 4 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>4)$$\end{document} respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in O ( n 2 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>2)$$\end{document} time, i.e., when two starting points of the two tours are given as input.

We study the ART GALLERY Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from PLANAR MONOTONE 3SAT, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2 x 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3 x 3 block of cells) for all k is an element of N.

The online bin covering problem is: given an input sequence of items find a placement of the items in the maximum number of bins such that the sum of the items' sizes in each bin is at least 1. Boyar et al. [3] present a strategy that with O(log log n) bits of advice, where n is the length of the input sequence, achieves a competitive ratio of 8/15 approximate to 0.5333 ... . We show that with a strengthened analysis and some minor improvements, the same strategy achieves the significantly improved competitive ratio of 135/242 approximate to 0.5578 ... , still using O(log log n) bits of advice.

We study the problem of determining the complexity of the lower envelope of a collection of n geometric objects. For collections of rays; unit length line segments; and collections of unit squares to which we apply at most two transformations from translation, rotation, and scaling, we prove a complexity of Θ(n). If all three transformations are applied to unit squares, then we show the complexity becomes Θ(nα(n)), where α(n) is the slowly growing inverse of Ackermann’s function.

A k-transmitter g in a polygon P, with n vertices, k-sees a point p ∈ P if the line segment gp intersects P’s boundary at most k times. In the k-Transmitter Watchman Route Problem we aim to minimize the length of a k-transmitter watchman route along which every point in the polygon—or a discrete set of points in the interior of the polygon—is k-seen. We show that the k-Transmitter Watchman Route Problem for a discrete set of points is NP-hard for histograms, uni-monotone polygons, and star-shaped polygons given a fixed starting point. For histograms and uni-monotone polygons it is also NP-hard without a fixed starting point. Moreover, none of these versions can be approximated to within a factor c · log n, for any constant c > 0.