Art gallery theorems for guarded guards

We prove two art gallery theorems in which the guards must guard one another in addition to the gallery. A set of points (the guards) in a simple closed polygon (the art gallery) is a guarded guard set provided (i) every point in the polygon is visible to some point in and (ii) every point in is visible to some other point in We prove that a polygon with n sides always has a guarded guard set of cardinality (3n−1)/7 and that this bound is sharp (n5); our result corrects an erroneous formula in the literature. We also use a coloring argument to give an entirely new proof that the corresponding sharp function for orthogonal polygons is n/3 for n6; this result was originally established by induction by Hernández-Peñalver.     

Art gallery problem with guards whose range of vision is 180

It is shown that in any polygonal art gallery of n sides it is possible to place n/3 point guards whose range of vision is 180° so that every interior point of the gallery can be seen by at least one of them. The guards can be stationed at any point of the art gallery. This settles an open problem posed by J. Urrutia.     

Art Galleries with Interior Walls

Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Each interior wall has an arbi- trarily placed, arbitrarily small doorway. We show that the minimum number of guards that suffice to guard all art galleries with n vertices and m interior walls is , If we restrict ourselves to galleries with convex rooms of size at least r , the answer improves to The proofs lead to linear time guard placement algorithms in most cases. Received September 1, 1997, and in revised form May 27, 1998.     

Orthogonal art galleries with interior walls

Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Suppose that all walls (interior as well as exterior) are horizontal or vertical and each interior wall has an arbitrarily placed, arbitrarily small doorway. We show that the minimum number of guards that suffice to guard all such art galleries with n vertices and m interior walls is min{⌊(n+2m)/4⌋,⌊(n+3⌊n/2⌋+m-2)/8⌋}.     

Perfect Graphs and Guarding Rectilinear Art Galleries

In this paper we introduce a new method based on perfect graphs that can be used to prove bounds on the number of guards necessary to guard a rectilinear art gallery in terms of the number of vertices, area and perimeter, respectively. Using this method, we prove that a polyomino with perimeter $l\ge 6$ can be guarded by at most $\lfloor \tfrac{l}{6}\rfloor $ guards. Moreover, we give a new proof for the rectilinear art gallery theorem, stating that any rectilinear art gallery with $n$ vertices can be guarded by at most $\lfloor \frac{n}{4}\rfloor $ guards. Finally, we give a new proof that at most $\lfloor \tfrac{m+1}{3}\rfloor $ guards are necessary to guard an $m$ -polyomino, even if the polyomino contains holes.     

Art galleries with guards of uniform range of vision

We are given an art gallery represented by a simple polygon with n sides and an angle (0°,360°]. How many guards of range of vision are required to monitor every point of the polygon in the worst case? After recent results on upper bounds of this problem, we prove new lower bounds for all 0°<<180°. Several lower bounds meet the best known upper bounds, and we expect our lower bounds to be best possible.

Surprisingly, it turns out that n/3 180°-guards are always enough to monitor a polygon of n sides, but if we wish to use (180−)°-guards for any >0, then possibly 2n/3−1 guards are necessary.     

An efficient algorithm for guard placement in polygons with holes

In this paper we consider the problem of placing guards to supervise an art gallery with holes. No gallery withn vertices andh holes requires more than [(n+h)/3] guards. For some galleries this number of guards is necessary. We present an algorithm which places the [(n+h)/3] guards inO(n ²) time. Work by the first author was done at Rutgers University and was supported in part by a DIMACS research assistantship. The second author was supported in part by National Science Foundation Grants CCR-88-03549 and CCR-91-04732.     

A Characterization of Homothetic Simplices

For any k we construct a simply connected compact set (art gallery) in R ³ whose every point sees a positive fraction (in fact, more than 5/9) of the gallery, but the whole gallery cannot be guarded by k guards. This disproves a conjecture of Kavraki et al. Received May 2, 1997, and in revised form February 5, 1998.     

Normal art galleries: Wall in – all in

We introduce the notion of a normal gallery, a gallery in which any configuration of guards that visually covers the walls necessarily covers the entire gallery. We show that any star gallery is normal and any gallery with at most two reflex corners is normal. A polynomial time algorithm is provided deciding if, for a given gallery and a finite set of positions within the gallery, there exists a configuration of guards in some of these positions that visually covers the walls, but not the entire gallery.     

An addition to art galleries with interior walls

Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Each interior wall has an arbitrarily placed, arbitrarily small doorway. It is shown in [5] that the minimum number of guards that suffice to guard all art galleries with n vertices and m interior walls is \min{ \lfloor (2n-3)/3\rfloor, \lfloor (2m+n)/3\rfloor, \lfloor (2n+m-2)/4\rfloor} . The proofs for the first two bounds lead to linear-time guard placement algorithms, while this is not known for the third case. We present an alternative short proof for the third upper bound \lfloor(2n+m-2)/4\rfloor that also leads to a linear-time guard placement algorithm. Received March 2, 2000, and in revised form April 28, 2000. Online publication October 10, 2000.     

On guarding the vertices of rectilinear domains

We prove that guarding the vertices of a rectilinear polygon P, whether by guards lying at vertices of P, or by guards lying on the boundary of P, or by guards lying anywhere in P, is NP-hard. For the first two proofs (i.e., vertex guards and boundary guards), we construct a reduction from minimum piercing of 2-intervals. The third proof is somewhat simpler; it is obtained by adapting a known reduction from minimum line cover.

We also consider the problem of guarding the vertices of a 1.5D rectilinear terrain. We establish an interesting connection between this problem and the problem of computing a minimum clique cover in chordal graphs. This connection yields a 2-approximation algorithm for the guarding problem.     

Geodesic and contour optimization using conformal mapping

The art gallery problem (AGP) is one of the classical problems in computational geometry. It asks for the minimum number of guards required to achieve visibility coverage of a given polygon. The AGP is well-known to be NP-hard even in restricted cases. In this paper, we consider the AGP with fading (AGPF): A polygonal region is to be illuminated with light sources such that every point is illuminated with at least a global threshold, light intensity decreases over distance, and we seek to minimize the total energy consumption. Choosing fading exponents of zero, one, and two are equivalent to the AGP, laser scanner applications, and natural light, respectively. We present complexity results as well as a negative solvability result. Still, we propose two practical algorithms for AGPF with fixed light positions (e.g. vertex guards) independent of the fading exponent, which we demonstrate to work well in practice. One is based on a discrete approximation, the other on non-linear programming by means of simplex-partitioning strategies. The former approach yields a fully polynomial-time approximation scheme for the AGPF with fixed light positions. The latter approach obtains better results in our experimental evaluation.     

The Art Gallery Theorem for Polyominoes

We explore the art gallery problem for the special case that the domain (gallery) P is an m-polyomino, a polyform whose cells are m unit squares. We study the combinatorics of guarding polyominoes in terms of the parameter m, in contrast with the traditional parameter n, the number of vertices of P. In particular, we show that $\lfloor\frac{m+1}{3} \rfloor$ point guards are always sufficient and sometimes necessary to cover an m-polyomino, possibly with holes. When $m \leq\frac{3n}{4} - 4$ , the sufficiency condition yields a strictly lower guard number than $\lfloor\frac{n}{4}\rfloor$ , given by the art gallery theorem for orthogonal polygons.     

Watched guards in art galleries

The art gallery problem asks how many guards are sufficient to see every point of the interior of a polygon. A set of guards is called watched if each guard itself is seen by at least one of its colleagues. In 1994, Hernández-Pe?alver wrote that watched guards always suffice to guard any polygon with n vertices. However in 2001, Michael and Pinciu, and independently Żyliński, presented a class of polygons that required more than watched guards – which disproved the Hernández-Pe?alver’s result – and they established a new tight bound for watched guards: . Combinatorial bounds for watched guards in orthogonal polygons were independently given by Hernández-Pe?alver , and by Michael and Pinciu, who proved the -bound to be tight. In this paper, tight bounds for polygons of miscellaneous shapes are presented: watched guards for monotone and spiral polygons, and vertex watched guards for star-shaped polygons.     

Discrete sensor placement problems in distribution networks

We consider the problem of placing sensors in a network to detect and identify thesource of any contamination. We consider two variants of this problem:

(1) sensor-constrained: we are allowed a fixed number of sensors and want to minimize contaminationdetection time; and

(2) time-constrained: we must detect contamination within a given time limit and want to minimize the number of sensors required.

Our main results are as follows. First, we give a necessary and sufficient condition for source identification.Second, we show that the sensor and time constrained versions of the problem are polynomially equivalent. Finally, we show that the sensor-constrained version of the problem is polynomially equivalent to the asymmetric k-center problem and that the time-constrained version of the problem is polynomially equivalent to the dominating set problem.     

New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

Effective inseparability in a topological setting

Effective inseparability of pairs of sets is an important notion in logic and computer science. We study the effective inseparability of sets which appear as index sets of subsets of an effectively given topological T₀-space and discuss its consequences. It is shown that for two disjoint subsets X and Y of the space one can effectively find a witness that the index set of X cannot be separated from the index set of Y by a recursively enumerable set, if X intersects the topological closure of an effectively enumerable subset of Y. As a consequence of a more general parametric inseparability result a theorem of Rice-Shapiro type is obtained. Moreover, under some additional requirements it follows that nonopen subsets have productive index sets. This implies a generalized Rice theorem: Connected spaces have only trivial completely recursive subsets. As application some decision problems in computable analysis and domain theory are studied. It follows that the complement of the halting problem can be reduced to the problem to decide of a number whether it is a computable irrational. The same is true for the problems to decide whether two numbers are equal, whether one is not greater than the other, and whether a number is equal to a given number. In the case of an effectively given continuous complete partial order the complexity of the last problem depends on whether the given element is the smallest element, in which case the complement of the halting problem is reducible to it, whether it is a base element and maximal, then the decision problem is recursively isomorphic to the halting problem, or whether it is none of these. In this case, both the halting problem and its complement are reducible to the problem. The same is true in nontrivial cases for the problems whether an element belongs to the basis, whether two elements of the partial order are equal, or whether one approximates the other. In general, for any nonempty proper subset of the partial order either the halting problem or its complement can be reduced to the membership problem of the subset.     

Optimal multiple interval assignments in frequency assignment and traffic phasing

In this paper, we consider the optimal assignments of unions of intervals to the vertices of the compatibility graph G, which arises in connection with frequency assignment and traffic phasing problems. It is shown that the optimal multiple interval phasing numbers θ_J≥rx(G) and θ^J≥r_xN(G), are optimal solutions to linear programming problems whose variables correspond to maximal cliques of G. Efficient algorithms are given for determining the first number, θ_J≥rx(G), when G is a chordal graph or a transitively orientable graph.     

A note on the eternal dominating set problem

We consider the “all guards move” model for the eternal dominating set problem. A set of guards form a dominating set on a graph and at the beginning of each round, a vertex not in the dominating set is attacked. To defend against the attack, the guards move (each guard either passes or moves to a neighboring vertex) to form a dominating set that includes the attacked vertex. The minimum number of guards required to defend against any sequence of attacks is the “eternal domination number” of the graph. In 2005, it was conjectured [Goddard et al. (J. Combin. Math. Combin. Comput. 52:169–180, 2005)] there would be no advantage to allow multiple guards to occupy the same vertex during a round. We show this is, in fact, false. We also describe algorithms to determine the eternal domination number for both models for eternal domination and examine the related combinatorial game, which makes use of the reduced canonical form of games.     

Matrix realizations of littlewood—richardson sequences

In this paper we consider the problem of characterizing the invariant factors of three matrices AB, and C, such that AB — C Our matrices have entries over a principal ideal domain or over a local domain. In Section 2 we show that this problem is localizablc

The above problem lias a well-known solution in terms of Littlewood-Richardson sequences. We introduce the concept of a matrix realization of a Littlewood-Richardson sequence. The main result is an explicit construction of a sequence of matrices which realizes a previously given Littlewood Richardson sequence. Our methods offer a matrix theoretical proof of a well-known result of T, Klein on extensions of p-modules.