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:

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

  • mmm I can imagine this being NP-hard. I'll try to formulate something. – Realz Slaw Nov 3 '13 at 10:55
  • 1
    The minimization version with holes allowed is NP-Hard, but for simply-connected orthogonal polygons (i.e. without holes) it has a polynomial algorithm. However, if in your problem the sizes are integer and you really mean a minimal cover and not a minimum cover, then in this case a polynomial algorithm is possible. – Parham Nov 4 '13 at 1:11
  • Mmm, I need a proof that a the minimum squares will be rationally positioned and have rational sizes; or even more, that if the input is integer-sized and integer-positioned, then the minimum squares will be as well (to reduce it to SAT). Intuitively, I conjecture that this is true, do you have any ideas to prove it? – Realz Slaw Nov 4 '13 at 15:59
  • @MahmoudAlimohamadi: can you provide the titles/authors of the paper(s) where the problem of tiling rectilinear polygons (with or without holes) with squares is studied (and solved). – Vor Nov 5 '13 at 10:06
  • 2
    btw, I assumed you meant minimum instead of minimal. – Realz Slaw Nov 7 '13 at 19:36
up vote 14 down vote accepted
+100

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:

enter image description here         enter image description here         enter image description here

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.

enter image description here         enter image description here         enter image description here

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.

enter image description here

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:

enter image description here

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

Here is how it is used:

enter image description here         enter image description here

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:

enter image description here         enter image description here

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:

enter image description here

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

enter image description here         enter image description here

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:

enter image description here

Above: A wire.

enter image description here        enter image description here

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

enter image description here       enter image description here

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:

enter image description here         enter image description here

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:

enter image description here

named-value-gate

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

enter image description here

odd-skip-gate: Odd skipping a wire

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

enter image description here

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

enter image description here

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

enter image description here

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:

enter image description here

Convince yourself it works:

enter image description here         enter image description here

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:

enter image description here

Convince yourself that it works:

enter image description here

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

enter image description here

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:

enter image description here

And a view of the two possible states:

enter image description here         enter image description here

The gate can be oriented as needed.

clause-gate

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

enter image description here

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:

  1. Start at the clause-gadget and follow the arrows.
  2. Non-arrow-lines mean that it is part of a circuit, but it is not forced into a state by the gate.
  3. 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):

enter image description here

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

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.

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.

  • lol I was half-way through a formulation :(. Very interesting though! Welcome to cs.SE. – Realz Slaw Nov 4 '13 at 4:31
  • 2
    If I understand correctly, this paper allows the squares to overlap (i.e. it is a covering problem). I am interested in the case where the squares are not allowed to overlap (i.e. it is a partitioning / tiling problem). – Erel Segal-Halevi Nov 4 '13 at 8:01
  • @ErelSegalHalevi: Oh, I am sorry, I didn't read your question carefully. – Joseph O'Rourke Nov 4 '13 at 10:37
  • 2
    Oh then I shall continue :D – Realz Slaw Nov 4 '13 at 14:01

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.