bigintegers's blog

Covering a rectangle with dominoes
By bigintegers, history, 4 years ago, In English

As a part of a project, I am troubled with the following problem:

Given an l x w rectangle, where 1 <= l, w <= n as well as n polygon-shaped dominoes d1, d2, d3, ..., dn (each domino does not necessarily have just a length and width -- it is a polygon), I want to cover as much of the l x w rectangle as possible using the given dominoes.

The dominoes that are placed into the rectangle don't necessarily need to be small enough to fit inside of the rectangle, so we need to be able to recognize this and not use those dominoes in invalid places.

Now suppose I hypothetically have an O(n^k) algorithm that solves the following problem:

"Given the list of dominoes, the rectangle dimensions (l and w) and some value x, this algorithm returns true if there exists some way to cover at least x squares with the dominoes and the algorithm returns false otherwise."

Now using this algorithm, is it possible to find a tiling of the l x w rectangle that covers as many squares as possible (i.e. a maximal orientation) in polynomial time? I want to figure out if it is possible and how fast it would be.

You can find the maximal value of x in polynomial time. But then finding which dominoes to use and their orientation is difficult.

Some ideas (but I might be completely wrong):

  • Represent the squares as nodes in a graph?

  • Maybe something clever with DP?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

If you have that O(n^k) algorithm somehow, you can do binary search over x to cover as much of the rectangle as possible in time O(n^k log(l*w))

Edit: nvm, misunderstood the question

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't quite follow what you are saying. I need to figure out which dominoes to use and where they should be placed in polynomial time.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh, my bad. I completely misunderstood what you were asking for.

      I don't know how to figure where to put the dominoes, but you CAN determine which dominoes to use in polinomial time. Use binary search to determine the maximal value of x (let's call it x*). You can then try removing a domino from the list, and call your algorithm with the modified list and x*. If it returns false, this domino is required for an optimal solution, and you must return it to the list. If it returns true, then don't put it back. Do this for every domino in the list.

      When you finish, you'll have a list of dominoes such that an optimal solution exists that uses every (and only) dominoes in this list.

      → Reply