Tiling an orthogonal polygon with squares

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.

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

StackExchange Computer Science Q#16661, answer score: 16