The dispersive art gallery problem (Q6092310)

This fascinating paper studies an interesting question in computational geometry coined ``The dispersive art gallery problem.'' The problem roughly put is to answer the following question: How many guards are necessary to guard an art gallery? This question was first posed by Victor Klee in 1973 and opened a flourishing field of research in computational geometry. The paper under review contains a survey of results since then. In the context of a precise mathematical question, the question is the following: Let us be given a fixed simple polygon \(P\) and integer \(k\). How to decide whether there is a guard set of cardinality \(k\) such that every point \(p\in P\) is seen by at least one guard, where a point is seen by a guard if and only if the connecting line segment is inside the polygon. In this paper, the authors study the vertex guard variant of this problem for the class of polyominoes. Amongst the many things they discover are the following. They provide a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most 3. They describe an algorithm that computes guard sets for simple polyominoes that match this upper bound. They show that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least 5 in a given polyomino is NP-complete. They also compute a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes. The paper is well written with a good set of references.