Drainability and Fillability of Polyominoes in Diverse Models of Global Control

The targeted use of global control mechanisms, applied synchronously and uniformly¹¹1Due to this intrinsic connection, we use the qualifiers “uniform” and “global” synonymously when applied to models of motion. to small-particle matter (i.e., passive matter), is both of great practical relevance and highest (theoretical) complexity. A fundamental type of global control mechanism is that of uniform movement or translation, which finds application in a variety of manufacturing processes, such as filling polyhedra with a liquid for gravity casting [19, 20, 31] or the intact removal of cast objects from their molds [17, 18]. Global forces like electromagnetic fields and gravity play a key role in a range of further applications, such as amorphous computing and smart materials like smart paint [2], autonomous monitoring and repair systems as well as minimally invasive surgeries [11], medication [14], and biological robots [16].

Inspired by tilt games [1, 4, 24], theoretical research commonly uses discrete, grid-based models to study the manipulation of passive matter by global control signals. In this context, a distinction is made between single step and full tilt models [11, 23], i.e., the movement of all particles by either one step or by a maximum distance in a uniform direction.

One of the most challenging problems remains the question of filling geometric shapes using global control: Given a board, defined as a subset of the square grid as well as a number of “infill points” (sources), the question is whether, and if so how, the entire board can be filled by adding particles through the set of sources, with all particles moving in the same direction as determined by global control mechanisms. Crucially, the inherently discrete nature of particle models introduces new complications that have not appeared in the continuous frameworks in [19, 20], such as particles forming stacks by blocking each other instead of spreading like liquids.

Naturally, there exist boards that cannot be filled with a given number of sources. We investigate the (therefore immediately arising) question of minimal necessary changes to the board in order to achieve fillability. Even in simplified models, globally controlled particles and targeted changes to the board create dynamic systems that are extremely complex to analyze and control: The smallest manipulation of a board can lead to far-reaching and not locally restrictable changes in terms of fillability, see for example Figures 2(b) and 2(c).

Furthermore, it is unclear how the different models relate to each other in terms of the contrasting objectives of filling or draining. In this paper, we provide a generalized, comprehensive framework for the comparative study of tilt models and formally investigate what makes a given model more powerful than another, i.e., allows more polyominoes to be filled or drained. This includes the special case of single step and full tilt movement.

Particles move on a board, which we model as a finite subgraph of the square tiling’s dual graph, i.e., a board $B=(V,E)$ is a finite graph with $V\subset {\mathbb{Z}}^2$ and $E\subseteq \{\{u,v\}:u\in V,v\in V,{\Vert u-v\Vert }_1=1\}$. The boundary of a board is the axis-aligned polygon separating the tiles in $V$ from ${\mathbb{Z}}^2\setminus V$. Note that the boundary uniquely determines the corresponding board. We only illustrate the special case of vertex-induced boards, which are isomorphic to sets of polyominoes and as such have boundaries whose sides only intersect at corners, even though the results in this paper hold in general. A sub-board is a vertex-induced subgraph of a board; a maximally connected (sub-)board is called a region. We refer to the elements of $V$ as pixels. Every pixel is uniquely determined as the intersection of two segments, a horizontal row segment and a vertical column segment, which are maximally contiguous subsets of pixels of equal $y$-, or $x$-coordinate, respectively. A boundary pixel is a pixel adjacent to a side of the boundary; a corner pixel is a pixel adjacent to two perpendicular sides of the boundary. The set $\{\mathrm{\ell },r,u,d\}$ is shorthand for the directions $\mathrm{\ell }$eft, $r$ight, $u$p, and $d$own. For a pixel $p$ let $p^{\mathrm{\ell }}$, $p^r$, $p^u$, and $p^d$ denote the left and right boundary pixel in its row segment, and the top and bottom boundary pixel in its column segment, respectively; see Figure 2(a).

A configuration $C\subseteq V$ is a subset of the pixels. We call a pixel $p\in C$ occupied and a pixel $p\in V\setminus C$ free. A move $m:2^V\to 2^V$ is a mapping between configurations; a model is a set of moves. Given a model $M$ and two configurations, $C$ and $D$, we say $D$ is reachable from $C$ in one move, or $C{\to }_{M}D$, if $D=m(C)$ for some $m\in M$. $D$ is reachable from $C$, or $C{\to }_M^{\ast }D$, if there is a sequence of moves $m_1,m_2,\mathrm{\dots },m_k\in M$ such that $D=m_k\circ \mathrm{\cdots }\circ m_2\circ m_1(C)$, i.e., ${\to }_M^{\ast }$ is the reflexive, transitive closure of ${\to }_M$. We omit braces for singletons and write, e.g., $u{\to }_{M}v$ instead of $\{u\}{\to }_M\{v\}$. A pixel $p$ is occupiable from a configuration $C$ if there is a configuration $D$ reachable from $C$ that contains $p$.

The full tilt model, $\mathrm{FT}=\{u_{\mathrm{\infty }},d_{\mathrm{\infty }},{\mathrm{\ell }}_{\mathrm{\infty }},r_{\mathrm{\infty }}\}$, has one move for every direction, which sees particles move maximally in that direction until they hit the boundary or are blocked by another particle. The move ${\mathrm{\ell }}_{\mathrm{\infty }}$, for example, transforms a configuration $C$ in such a way that exactly the $|R\cap C|$ leftmost pixels of every row segment $R$ are occupied in ${\mathrm{\ell }}_{\mathrm{\infty }}(C)$.

A sink is a move associated with a pixel $s\in V$ defined as $C\mapsto C\setminus \{s\}$. A configuration $C$ is minimal with respect to a set of sinks $S\subseteq V$ if there is no configuration $D$ such that $C{\to }_{\mathrm{FT}\cup S}^{\ast }D$ and . If $V{\to }_{\mathrm{FT}\cup S}^{\ast }\mathrm{\varnothing }$, then the board is drainable to $S$. Figure 3 illustrates particles moved to and removed at a sink.

Further notation is introduced as needed in individual sections. Table 1 provides a reference of frequently used symbols.

In this section, we examine an algorithmic approach to deciding drainability in the full tilt model, starting with the following theorem. This is a special case of a property that holds in more general classes of models, which is why we postpone the proof until Theorem 20 in Section 5.

The characterization in Theorem 1 suggests an approach to deciding drainability. Consider what we call the full tilt graph $G_F(B)=(V_F,E_F)$ of a board $B=(V,E)$. $V_F=V$ contains all pixels of $B$ and $E_F=\{(p,q)\in V^2:p\ne q,q\in \{p^{\mathrm{\ell }},p^r,p^u,p^d\}\}$ connects $p$ to $q$ if a particle at $p$ can reach $q$ in a single move. Deciding drainability is equivalent to testing if there is a path in $G_F$ from every pixel to a sink. However, this is unnecessarily inefficient. In particular, we do not need to check every pixel and require only the boundary as input.

We now describe an algorithm that, given the boundary of a board $B=(V,E)$ and a set $S\subseteq V$ of potential sinks, finds a minimum-cardinality subset $S^{\prime }\subseteq S$ such that $B$ is drainable to $S^{\prime }$ – or reports that no such set exists. As a consequence, we can decide whether a board is drainable to a set $S$ by supplying $S$ to the algorithm and observing if it returns a subset or reports failure. The general approach is the same as the one used by the authors of [6]. However, due to the rectilinear nature of board boundaries, and our restriction to tilting in only four directions, our algorithm requires less time.

By Corollary 2, the only pixels relevant for drainability are those reachable from corner pixels. This allows us to restrict our algorithm to the small tilt graph, $G_S(B)=(V_S,E_S)$, of $B$. Let $V^{\prime }\subseteq V$ be the set of corner pixels of $B$. Then $V_S$ is the closure of $V^{\prime }$ under ${\to }_{\mathrm{FT}}^{\ast }$, and $G_S$ is the subgraph of $G_F$ induced by $V_S$; see Figure 4(a). For a boundary with $n$ corners, $|V_S|\in 𝒪(n)$ as there are at most two additional pixels for every reflex corner of the boundary, and $|E_S|\in 𝒪(n)$ as at most three other pixels are reachable from every boundary pixel in a single move.

Although not every board is drainable, slight changes may render a board drainable, see Figures 2(b) and 2(c). Given a board and a set $S$ of sinks, we want to determine a maximum-size sub-board drainable to $S$. In other words, we want to place a minimum number of obstacles such that the remaining board is drainable. We refer to this as the Maximum Tilt Draining Problem.

We now step away from the full tilt model and consider arbitrary models. For a model $M$ we define the model $M^{\ast }$ to contain all compositions of moves from $M$, i.e., $m\in M^{\ast }$ if there are $m_1,m_2,\mathrm{\dots },m_k\in M$ such that $m=m_k\circ \mathrm{\cdots }\circ m_2\circ m_1$, for any $k\ge 0$. We generalize the concepts of minimality and drainability in the obvious way. A move $m$ is monotone if $C\subseteq D$ implies $m(C)\subseteq m(D)$; it is volume-preserving if $|m(C)|=|C|$ for all $C$. Note that the moves associated with sinks are monotone but obviously not volume-preserving. Models are called monotone or volume-preserving if all of their moves have the respective property.

The most well-studied model, apart from the full tilt model, is the single step model, $\mathrm{S1}=\{u_1,d_1,{\mathrm{\ell }}_1,r_1\}$, which has particles move to an adjacent pixel in one of the four directions, unless they are blocked by the boundary or another particle. Formally, call a pixel left-blocked in a configuration $C$ if it and every pixel left of it in its row segment are occupied in $C$. Then $p\in {\mathrm{\ell }}_1(C)$ if and only if $p$ is left-blocked in $C$ or $p+{(1,0)}^{\mathrm{T}}\in C$. The other moves are defined analogously with respect to the other directions. Additionally, we introduce an extension to the full tilt and single step models that allows movement to be restricted to a subset of the segments parallel to the direction of movement. Let $M\in \{\mathrm{FT},\mathrm{S1}\}$. Then the interval extension $M_{\mathrm{I}}$ has moves $m^{[i,j]}\in M\times {\mathbb{Z}}^2$ that apply the move $m\in M$ to those segments whose $y$-coordinate (in the case of row segments and horizontal moves) or $x$-coordinate (for column segments and vertical moves) lies in the interval $[i,j]$, and leave all other segments of the affected type unchanged. See the bottom half of Figure 12 for exemplary moves in ${\mathrm{FT}}_{\mathrm{I}}$. We start with an easily verified observation.

In this paper, we have analyzed ways to make a board fillable or drainable using particles moving as instructed by several models of global control signals. We have shown that placing a minimum number of obstacles to achieve fillability is $\mathrm{𝖭𝖯}$-hard in all considered models. However, a constant-factor approximation is possible for scaled boards. The most apparent open question concerns the complexity of the obstacle placement problem for scaled boards. Is it still $\mathrm{𝖭𝖯}$-hard or can we do better than the approximation and solve it optimally?

The next step in our future work is to investigate how to actually fill a board, once we know it is fillable. An immediate approach would be to maintain a configuration in memory and successively move bubbles to a source until the board is full. However, this may require an amount of memory that is not polynomial in the size of an appropriate encoding of the boundary. Can we efficiently compute (short) filling sequences? Of particular interest is the worst case analysis of the length of filling sequences.

It would be interesting to better understand the geometric properties of fillable regions. In the related problem of assembly there is a hierarchy of constructable shapes [8]. These shapes derive from the external movement of particles, whereas ours derive from internal movement. Are these classifications related?

Our goal so far was to completely fill a region. Applications may impose restricted areas, i.e., positions that may never be occupied by particles, while requiring other areas to be filled. How can this constraint be handled?

Although we introduced duality of models as a tool to connect fillability to drainability, it leads to interesting new questions. Maximality in a model is strongly related to the occupancy problem in the dual model. However, occupiability in the dual model has a natural interpretation in the original model, leading to what we dub the vacancy problem: Given a configuration $C$ and a pixel $p\in C$, is there a configuration $D$ reachable from $C$ that does not contain $p$? This problem is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete in the full tilt model because so is the occupancy problem and $\mathrm{FT}$ is dual to itself. To the best of our knowledge, this natural problem has not been examined in the single step model.

A promising approach to prove the conjecture is to follow the ideas Caballero et al. [22] used to prove the relocation problem hard for the single step model. They built on the techniques of [8] and used an observation that can be seen as a precursor to our notion of duality, implying that the same methods are likely applicable in this case.