Tiling an orthogonal polygon with squares

Question

Given an orthogonal polygon (a polygon whose sides are parallel to the axes), I want to find the smallest set of interior-disjoint squares, whose union equals the polygon.

I found several references to slightly different problems, such as:

• Covering an orthogonal polygon with squares - similar to my problem, but the covering squares are allowed to overlap. This problem has a polynomial solution (Aupperle, Conn, Keil and O'Rourke, 1988; Bar-Yehuda and Ben-Hanoch, 1996).
• Tiling/decomposing/partitioning an orthogonal polygon to rectangles. This problem has a polynomial solution (Keil, 2000; Eppstein, 2009).
• Covering an orthogonal polygon with rectangles - this problem is known to be NP-complete (Culberson and Reckhow, 1988).

I am looking for an algorithm for minimal tiling with squares.

Answer 1

I will try to show this problem is NP-hard, by reduction from $\text{Planar-}3\text{-SAT}$.

---

Reduction from $\text{Planar-}3\text{-SAT}$

Some basic Gadgets

Gadgets are internal configurations of geometry that will allow us to construct gates for use in a circuit, to which we will reduce $\text{Planar-}3\text{-SAT}$.

4X3-gadget

This gadget has two valid minimal-square-partition-states:

               

^{LeftA 4X3-gadget.Middle and right:Two possible minimal-square-partition-states.}

5X4-gadget

This gadget, is exactly like a 4X3-gadget, just with larger dimensions.

               

^{LeftA 5X4-gadget.Middle and right:Two possible minimal-square-partition-states.}

endpoint-gadget

An endpoint-gadget is a 5X4-gadget. It is frequently used as an endpoint/pin of a gate. One of the two states of an endpoint can be valued as true, and the other false. An endpoint marks the two ends, one as $T$ and the other as $F$. The end that is covered by the large square is the value of the endpoint.

^{Left: Wireframe of endpoint-gadget. Center:True-valued endpoint. Right: False-valued endpoint.}

i-wire gadget

An i-wire gadget is short for implication wire.

Rules:

• An i-wire gadget consists of a odd-length rectangle of a length of more than $2$ and a width of $2$.
• An i-wire gadget can have $3$ minimal-square-partition-states, pushed from one side, the other, or neither; an i-wire in this third state shall be called locally unconstrainted.

Example:

^{Figure 7: An i-wire gadget of length $7$, and width $2$.}

Here is how it is used:

       

^{Figure 8,9, Left: wireframe i-wire across two endpoints. Right: Union.}

Now, if one endpoint is in the right state, it forces the other endpoint into a pushed-position. Example:

       

^{Left: Square partition diagram; left switch is down, "pushes" all the squares down the i-wire and finally, pushes the other switch (endpoint). Right: Square partition diagram; left endpoint is full, "pushes" all the squares down the i-wire, and forces the endpoint on left to be "up".}

This is essentially a logical implication. Consider "down" to be true, then we have $A \implies \neg B$. We can also do $A \implies B$ by simply flipping the endpoint on the right.

However, this leaves the unconstrainted case:

If we combine two i-wires, we can get a two-way implication, essentially a boolean (in)equality:

       

So, two i-wires can carry a full equality relationship, much like a circuit - in fact, it is a circuit. We will use these pairs to construct a usable wire.

Each i-wire gadget contributes $\frac{l-1}{2}+2$ partition-squares to the minimal-square-partition, save for the shared-corners with other gadgets.

i-wires can be oriented as needed.

wire

A wire consists a pair of i-wires that are connected to the same gates at each endpoint.

• The i-wires are colored red and green.
• The pair must be separated by $3$ spaces (convention).
• Each gate pin will have a green and red contact; a wire must correctly connect.
• Invariant rule: one i-wire be pushed in the opposite direction of the other i-wire, each gate assumes this, and makes certain of this (unless otherwise noted).
• Since each wire contains a two-way implication, it carries the values from gate to gate like a wire in a circuit.
• Every wire must be connected to a gate at both ends.. Failing this can ruin the assumptions of some gates that I describe, and the invariant rule above; however, gates that have endpoints across the leads are safe - you can connect stray wires to these endpoints without worrying about it ruining the gate.
• wires must be of odd-length, including the leads to any circuit it connects to; however I will describe an odd-skip-gate below that allows an even-lengthed wire to become odd-lengthed.

Pictures:

^{Above: A wire.}

       

^{Left and right: Two possible minimal-square-partition-states of a wire. Note that if the wire is only this length, it will not be able to shift off to the right or left, and will have to break one square into smaller pieces.}

wires can be oriented as needed.

bend-gate: Bending a wire

       

^{Left: Wire-frame view. Right: Union view.}

Note the use of the 4X3-gadget. It is used to fix the red lead to odd length.

Following are the two possible minimal-square-partition-states of the bend:

       

^{Left and right:Two possible minimal-square-square-partition-states of a bending wire.}

The gate can be oriented as needed. Obviously, this gate can be mirrored to work for the other direction.

Skewing a wire

It is easy to shift a wire over. Wireframe illustration:

named-value-gate

A named-value-gate is essentially an endpoint as a gate with one wire contact:

odd-skip-gate: Odd skipping a wire

Sometimes it is inconvenient to only have odd-length wires. For example:

As you can see, that little bit of extension is a bit annoying. Here is a corresponding solution, using the 4X3-gate:

So, turning this into a gate, we get the odd-skip-gate (in wireframe):

The gate can be oriented as needed.

twist-gate: Twisting a wire

Somtimes you get the red and black i-wires on the wrong sides for use with a gate. In this case, a twist-gate is provided, to twist the red and black i-wires to the opposite sides.

Wireframe illustration:

Convince yourself it works:

       

^{Start from $A$, follow the push-arrows, everything else should be forced and consistent.}

The gate can be oriented as needed.

split-gate: Splitting a wire

Splitting a wire, wireframe:

Convince yourself that it works:

^{Figure:Start from $A$, follow the push-arrows. Everything should be forced and consistent.}

^{Figure:Start from $A$, follow the push-arrows. Everything should be forced and consistent.}

Note: Every wire coming in and out of the splitter absolutely must connect to an endpoint somewhere, in order to maintain the invariant. Alternatively, you can add endpoints to each of the pairs of leads of the splitter.

The gate can be oriented as needed.

not-gate

The not gate takes a wire and outputs a wire that has the reverse implications. It is basically a twist-gate, except that it relabels the colorings of the wires. The not-gate looks like this:

And a view of the two possible states:

       

The gate can be oriented as needed.

clause-gate

For the clause-gate, we first introduce the clause-gadget:

^{Left to right: 1 clause-gadget. 2-4: $3$ different minimal-square-partition-states.}

This is what the gate looks like:

We can demonstrate the different states of this gate (explanation underneath all $3$ illustrations):

Explanation:

2. Start at the clause-gadget and follow the arrows.
3. Non-arrow-lines mean that it is part of a circuit, but it is not forced into a state by the gate.
4. The state of the clause-gadget forces one of the endpoints to be valued true.

As you can see, at least one of the inputs will have to be valued as true. This is exactly what a $3\text{-CNF}$ clause requires.

The gate can be oriented as needed.

Reduction

Let $\Phi(\mathbf x)$ be a $\text{Planar-}3\text{-SAT}$ formula, where

$$\Phi\left(\mathbf x\right)={\huge\wedge}_i^n C_i,\\ C=\left\{(x_j \vee x_k \vee x_l)\right\} $$

A visual aid (original source: Terrain Guarding is NP-Hard (PDF), reproduced in tikz):

Then:

1. For each variable $x_i\in\mathbf x$, place two named-variable-gates next to each-other, name one of them $x_i$ and the other $\neg x_i$.
2. Connect the gates to each-other with a not-gate, so that they logically negate each-other's values.
3. Place the variables' gates' polygons at their locations in the planar-embedding.
4. For each clause, place a clause-gate at the clause's location in the planar-embedding.
5. Using the gates described above, connect all the variables to their clauses.
6. Run a minimum-square-paritioning-algorithm on the resulting union of the all of gate's polygons (the entire circuit).
7. If the algorithm returns the sum of all the gate's minimal-square-partition-state sizes (subtracting for shared-corners) then it is satisfiable. If it is not satisfiable, it will force a constrained gadget to split into smaller squares, thus increasing the number of squares required to partition the circuit.

Why it works

• Each gadget has a minimal-square-partition-state size; that is, a minimal-square-partition of that gadget is a certain size.
• Some gadgets have several states with this size; each of these states are valid minimal-square-partitions.
• When gadgets are combined only in the corners, the sum of the minimal-square-partition-states of the gadgets is *still the minimUM-square-partition-state of the union of them; you can see this intuitively: joining at the corner does not give ample space for a square to expand/connect with a square from another gadget.
• While combining gadgets at the corner does not decrease the total minimum-square-partition size, it does relate and constrain the gadgets with each-other.
• With the gates shown above, you can constrain the states enough, so that if the logical formula is unsatisfiable, then one or more gadets will have to break into even smaller squares, and increase the minimum-square-partition size.

graph sources

• squaretilings1.tex (writelatex)
• squaretilings2.tex (writelatex)
• clausegate.tex (writelatex)

You can also see larger images by removing the "s", "m", "l", suffixes of the imgur urls. For example, You can see a larger image of this: https://i.sstatic.net/6CKlGs.jpg by going to https://i.sstatic.net/6CKlG.jpg. Notice the missing "s" before the .jpg.

Answer 2

An old paper I coauthored establishes that the covering problem is polynomial for a polygon without holes, and NP-complete with holes. We showed that a key underlying graph is chordal. Please note: the algorithm is polynomial in the number $N$ of unit squares in the polygon, $O(N^{3/2})$.

"Covering orthogonal polygons with squares." L. J. Aupperle and H. E. Conn and J. M. Keil and Joseph O'Rourke. Proc. 26th Allerton Conf. Commun. Control Comput., pp. 97-106, 1988. (link to download PDF scan)

However, the resulting covering may include squares that overlap. You are looking for a tiling, where squares are not permitted to overlap, so your problem is not quite the same.