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.
Tiling an orthogonal polygon with squares
algorithms;computational geometry;tiling
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 GadgetsGadgets 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-gadgetThis gadget has two valid minimal-square-partition-states:              LeftA 4X3-gadget.Middle and right:Two possible minimal-square-partition-states.5X4-gadgetThis gadget, is exactly like a 4X3-gadget, just with larger dimensions.              LeftA 5X4-gadget.Middle and right:Two possible minimal-square-partition-states.endpoint-gadgetAn 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 gadgetAn 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.wireA 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 wireIt is easy to shift a wire over. Wireframe illustration:named-value-gateA named-value-gate is essentially an endpoint as a gate with one wire contact:odd-skip-gate: Odd skipping a wireSometimes 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 wireSomtimes 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 wireSplitting 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-gateThe 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-gateFor 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:Start at the clause-gadget and follow the arrows.Non-arrow-lines mean that it is part of a circuit, but it is not forced into a state by the gate.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.ReductionLet $\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: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$.Connect the gates to each-other with a not-gate, so that they logically negate each-other's values.Place the variables' gates' polygons at their locations in the planar-embedding.For each clause, place a clause-gate at the clause's location in the planar-embedding.Using the gates described above, connect all the variables to their clauses.Run a minimum-square-paritioning-algorithm on the resulting union of the all of gate's polygons (the entire circuit).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 worksEach 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 sourcessquaretilings1.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: http://i.stack.imgur.com/6CKlGs.jpg by going to http://i.stack.imgur.com/6CKlG.jpg. Notice the missing s before the .jpg.