Guarding Offices with Maximum Dispersion

We present results for the Dispersive AGP with vertex guards in orthogonal polygons, including general, polyominoes, and office-like polygons, under $r$-visibility and $L_1$-geodesics. Without loss of generality, we assume a minimum distance of $1$ between any pair of vertices.²²2This assumption serves purely to simplify the statements; alternatively, setting the minimum distance to $\zeta$ would generalize all results proportionally.

• $\mathrm{■}$

  We show that the ratio between the cardinality of a maximally dispersed guard set and the smallest possible guard set can be arbitrarily large, even in histograms.

• $\mathrm{■}$

  We present polynomial-time algorithms that compute worst-case optimal guard sets for office-like polygons. Specifically, the algorithms achieve dispersion distances of $3$ when vertices are restricted to integer coordinates, and $2$ otherwise. These bounds are tight, as demonstrated by corresponding lower-bound constructions.

• $\mathrm{■}$

  Deciding whether a given office-like polygon allows a guard set with a dispersion distance of $4$ is $\mathrm{𝖭𝖯}$-complete when vertices are restricted to integer coordinates; the same result holds for polyominoes (and with minor modifications even for thin polyominoes), thereby resolving an open question from [27] on $\mathrm{𝖭𝖯}$-hardness in that setting. If vertex coordinates are allowed to be rational, deciding whether a dispersion distance of at least $2+\epsilon$ can be achieved for any $\epsilon >0$ is already hard; see Theorems 5, 6, and 7.

• $\mathrm{■}$

  For independent hole-free office-like polygons, we provide a dynamic programming approach to compute guard sets with maximum dispersion in polynomial time; see Theorem 8.

• $\mathrm{■}$

  We evaluate practical tractability by utilizing SAT, CP, and MIP techniques. Our experiments show that instances with up to $1600$ vertices can be solved in under $15\mathrm{s}$.

Note that the assumption on the minimum distance between any pair of vertices is not needed in both the practical evaluation as well as the dynamic programming. However, we adopt this assumption throughout the paper to improve clarity and readability. Due to space restrictions, details for statements marked with ($\star$) can be found in the full version [16].

The Art Gallery Problem (AGP) has been a cornerstone of computational geometry, inspiring extensive research. For an overview, see the previously mentioned book by O’Rourke [26] or the surveys by Shermer [29] and Urrutia [31].

For a long time, it was known that the classic AGP is $\mathrm{𝖭𝖯}$-hard in several fundamental variants [23, 28]. Abrahamsen, Adamaszek, and Miltzow [1] were the first to show that, even in monotone polygons, “irrational guards are sometimes needed”. They subsequently established $\exists ℝ$-completeness [2]. Meijer and Miltzow [25] construct a polygon that can be guarded by two guards, both of which must have irrational coordinates. When considering $r$-visibility (where two points $u$ and $v$ see each other if and only if the rectangle described by $u$ and $v$ lies completely within the polygonal region) instead of the classic line visibility, the AGP remains $\mathrm{𝖭𝖯}$-hard for polygons with holes [21], whereas optimal guard sets can be computed in polynomial time for hole-free (orthogonal) polygons [32]. Recently, Cruz and Tomás [10] introduced a family of orthogonal polygons designed to mimic properties of real-world buildings. We will refer to these polygons as office-like polygons. These polygons consist of multiple rectangular rooms connected by rectangular corridors, with each corridor being narrower than both of its incident rooms. Using $r$-visibility, they obtained several results. They introduced a simple greedy algorithm that computes optimal guard placements using the minimum number of guards for simple office-like polygonal environments. They also proved that efficient algorithms exist for the subclass of $r$-independent office-like polygons (i.e., office-like polygons in which the extensions of all pairs of adjacent corridors with the same direction are either coincident or disjoint), utilizing matching and flow techniques. However, guarding general office-like polygons under $r$-visibility remains $\mathrm{𝖭𝖯}$-hard.

All of the aforementioned results focus on minimizing the number of guards required for coverage. However, some variants relax this constraint and shift the focus to alternative objectives or other factors. One such example is the Chromatic AGP [12, 13, 14, 20], with each guard being assigned a color. The goal is to minimize the number of colors used so that no two guards of the same color class have overlapping visibility regions while ensuring full coverage of the domain. In the Conflict-free Chromatic AGP [3, 4, 19], the aforementioned overlapping constraint is relaxed, requiring that every point in the domain must see at least one guard whose color is unique among all guards visible from that point.

Under the current definition of the dispersive variant, the cardinality of a guard set is not considered relevant either. Rieck and Scheffer [27] studied the Dispersive AGP for vertex guards in polyominoes, assuming $L_1$ geodesics and $r$-visibility. They proved that deciding whether a given thin polyomino allows a guard set with a dispersion distance of $5$ is $\mathrm{𝖭𝖯}$-complete. Additionally, they provided a linear-time algorithm that produces a worst-case optimal solution for simple polyominoes, ensuring a guard set with a dispersion distance of $3$. Fekete et al. [15] extended this to vertex guards in polygons. They demonstrated that determining whether a guard set with a dispersion distance of $2$ exists in polygons with holes is $\mathrm{𝖭𝖯}$-complete. Furthermore, they showed that a dispersion distance of $2$ is sometimes unavoidable even in hole-free polygons and proposed an algorithm to generate such sets.

Dispersion problems, which are closely related to packing problems, focus on arranging a set of objects to be as far apart as possible or selecting a subset whose elements are maximally separated. Such problems naturally arise in the context of the obnoxious facility location problem [7] and the problem of distant representatives [17]. Baur and Fekete [5] studied the problem of distributing a set of points within a polygonal domain to maximize dispersion. They established that this problem is $\mathrm{𝖭𝖯}$-hard and ruled out the possibility of a $\mathrm{𝖯𝖳𝖠𝖲}$ for geometric dispersion problems unless $𝖯$=$\mathrm{𝖭𝖯}$.

Given any polygon $𝒫$, a subset $𝒢\subset 𝒫$ of points is called a guard set for $𝒫$ if every point $p\in 𝒫$ is visible by at least one point $g\in 𝒢$. We restrict ourselves to vertex guards, i.e., guards are only placed on vertices of the domain. We adopt the r-visibility model, where two points $p$ and $q$ are said to see each other if the axis-aligned rectangle defined by $p$ and $q$ is entirely contained within $𝒫$. The visibility region $\text{<em class="ltx\_emph ltx\_font\_italic">Vis</em>}(p)\subseteq 𝒫$ of a point $p$ is the set of all points that are visible from $p$. The size of a guard set is its number of guards. We measure the distance $\delta (p,q)$ between two points $p,q\in 𝒫$ as $L_1$-geodesics. With this, the dispersion distance $\mathrm{\ell }$ of a guard set $𝒢$ is the minimum geodesic $L_1$-distance between any pair of guards; we say that a guard set realizes a dispersion distance of $\mathrm{\ell }$, or is $\mathrm{\ell }$-realizing.

In this paper, we consider office-like polygons as well as polyominoes. Polyominoes are orthogonal polygons formed by joining unit squares edge to edge. An office-like polygon $𝒫=(ℛ,𝒞)$ is a connected orthogonal polygon made up from a collection of rectangular rooms $ℛ$ that are linked by a collection of rectangular corridors $𝒞$. A corridor connects two rooms if a side of the corridor is strictly contained in an edge of both rooms, i.e., the corridor is narrower than the rooms, and none of the vertices of a room coincides with a vertex of a corridor. An example of an office-like polygon with several rooms and corridors, as well as a set of guards is depicted in Figures 1 and 3(b). Each corridor connects exactly two rooms. A corridor is horizontal if it links rooms to its left and right; otherwise, it is vertical. Two corridors $C_1$ and $C_2$ are independent if no guard placed on a vertex of $C_1$ also guards $C_2$. If every pair of corridors is independent, then the polygon is independent.

Fekete et al. [15] showed that optimal solutions for the Dispersive AGP when considering arbitrary simple polygonal domains may contain many guards, even if the domain can be covered by a small number of guards. In particular, they obtained a family of polygons in which the ratio between the sizes of the respective guard sets is unbounded. We strengthen this by observing that this is true even for histograms, as visualized in Figure 2.

In the case of office-like polygons, it appears that the situation may differ. However, we can construct a family of these polygons for which this ratio asymptotically approaches $2$; the construction is given in the full version [16].

We establish the following worst-case bound.

As a first observation, it is easy to construct instances in which every guard set has a dispersion distance of at most $3$; an example is visualized in Figure 3(a). In this polygon, at least one guard is required in each of the three unit-square corridors, but then at least one pair of guards must be in distance $3$ of one another. Notably, this polygon can serve as some kind of building block, as it can be extended arbitrarily along the black arrows.

We now outline the high-level idea of a polynomial-time algorithm that computes guard sets with a dispersion distance of $3$, thereby ensuring optimal solutions in the worst-case. Our approach consists of three phases. In each phase, we place a set of guards, guaranteeing that no guard is positioned less than $3$ units away from any previously placed guard.

Phase (1):

Place guards on vertices of corridors connecting two rooms vertically to ensure that these corridors are properly guarded.

Phase (2):

Place guards similarly on the vertices of corridors connecting rooms horizontally.

Phase (3):

Place guards in any remaining rooms that are not yet covered.

An example illustrating the guard placements made by our algorithm is shown in Figure 3(b). Red guards are placed during the first phase, blue guards during the second phase, and green guards during the final phase.

In each phase, our approach ensures that every new guard is placed at least 3 units away from all previously placed guards. Essentially, in the first two phases, we place guards either on the left side of vertical corridors or on the bottom side of horizontal corridors. Moreover, it is easy to see that in every room that is not covered by the first two phases, there is at least one vertex that is in distance at least $3$ to a guard placed in an incident corridor.

We now investigate worst-case optimal solutions in case that vertices of the polygon are not restricted to integer coordinates. The primary challenge in achieving large dispersion distances arises in corridors that are independent but have a minimal horizontal or vertical separation. We refer to such arrangements of corridors as densely packed; an example is depicted in Figure 4(a).

Our main theorem for these polygons is the following.

We begin with observing that arrangements of densely packed corridors enforce small dispersion distances.

Consider the polygon shown in Figure 4(a). All corridors (depicted in dark gray) are unit squares, the rooms (represented as horizontal bars in light gray) have a height of $1$, and the red rectangles have a width of for any $\epsilon \in (0,1)$.

We now give the idea that any guard set contains a guard in corridor $C$ only if its dispersion distance is smaller than $2+\epsilon$. Clearly, every guard set must contain such a guard, as otherwise the corridor is not guarded. Every guard set with a dispersion distance of at least $2+\epsilon$ that contains a guard at the bottom-left (top-left) vertex of $C$ must contain all guards depicted in green (blue). However, this leads to a contradiction, as no guard can be placed with sufficient distance in $C_1$ (or $C_2$), i.e., there is no $2+\epsilon$-realizing guard set. Incoming arcs indicate that a previously placed guard enforces a guard position (because no other option in the respective corridor is possible). Due to symmetry, a guard set with adequate dispersion distance cannot contain a guard at either the bottom-right or top-right vertex of $C$. Moreover, this instance can easily be extended along the black arrows, to obtain office-like polygons with an arbitrary number of vertices.

We now prove that a dispersion distance of $2$ is always realizable.