1
$\begingroup$

I have an image consisting of discrete pixels, and which contains a smaller, rectangular 'target'-region. This target rectangle needs to be tiled with tiles of arbitrary shape. The shape and size of a tile depends on the position at which I put it down. I know how the tile shape changes as a function of position, and this dependence is smooth, for a vague and intuitive definition of smooth. E.g. it could be that a tile is approximately a triangle (or a pyramid), whose area increases the further to the left I go in the image.

I want to tile my target rectangle with as few tiles as possible, and with as little tiles as possible sticking out of the rectangle at the end. I believe that also implies that I want to minimize the overlap between tiles within the target rectangle.

I'm not too familiar with optimization and was hoping for pointers for how to do this? I'm particularly interested in knowing if this is an easy problem or not, and if not, is the problem equivalent to any other problems in the literature?

I believe the problem could be recast in terms of graph-theory instead of a set of pixels, and certainly one could use a target region that is not rectangular.

Furthermore, as I've stated the problem, it is a continuous problem, in that I can put a tile down at any position. I'm perhaps even more interested in solving the discrete version, where I can only put a tile down at a pre-selected number of grid points. The latter would be sufficient for my needs, and a local minimum solution rather than a global one would also be fine.

I'm particularly wondering if the discrete version might be an NP-complete problem, for a suitable cost-function (which I have only very loosely defined above).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.