Re: Two-dimensional pattern matching/compression


Herbert Glarner wrote:
At least it seems to be in NP, a nondeterministic Turing machine could
provide the smallest area *g*

I guess it would not be a really clever approach to build hash keys with
any possible match of the supermatrix, which input matrices would check
based on their own hashes: the supermatrix' hashes grow exponential as
input is added, and since storage isn't infinite...

Still open for any input.

--
http://herbert.wikispaces.com
Yes it is NP complete.
Proof is based at this NP-complete problem(I can't remember name,but
its rather easy prove NP by choosing tiles so collums represents tape
and each collum changes it as in step of TM)
You have set of tiles with form and you should decide if you can cover
given rectangle with them. ie with tiles
#1# #4#
2 3 3 2
#4# #1#
and rectangle 2*2 is solution
#1##4#
2 33 2
#4##1#
#4##1#
3 22 3
#1##4#
and we can easy use reduction to this problem. WLOG patern consist of
0,1,2,.(empty) We replace tiles by rectangle patterns which have at
all corners 2(so they can overlap only by edges) and at edges is
written number of aprop. tile in binary.Rest of edges are "." . In
middle is another number in binary to distinguish othervise same tiles
and othervise 0
Covered rectange is grid with 2 where you place tiles and 0 at unused
middle. We must choose tile long enought that placing one tile to
rectangle is better than all tiles outside and unused 0 will help with
this.

I would use some greedy algorithm like join two patterns which most
overlap and repeat until one pattern remains.
Hope that helps.

.

Relevant Pages

  • Re: Enigma 1491 - Tile trials
    ... Dick has a box of rectangular tiles. ... is a different size, the dimensions being ... all those that he has taken into a rectangle ... These "Enigmas" are usually solved before I see them, ...
    (rec.puzzles)
  • Re: Divide a rectangle (with cartesian coordinates) into equal
    ... into tiles in one of the configurations ... nearly square as possible, you just need to ... given an overall rectangle size ... number of squres along l = l/s ...
    (comp.soft-sys.matlab)
  • Re: Divide a rectangle (with cartesian coordinates) into equal
    ... into tiles in one of the configurations ... nearly square as possible, you just need to ... given an overall rectangle size ...
    (comp.soft-sys.matlab)
  • Re: Divide a rectangle (with cartesian coordinates) into equal
    ... into tiles in one of the configurations ... nearly square as possible, you just need to ... given an overall rectangle size ... number of squres along l = l/s ...
    (comp.soft-sys.matlab)
  • Natural Stone
    ... decoration. ... These tiles are available in different patterns and ... designs. ... various patterns to create spell-bounding designs.http:// ...
    (uk.people.parents)