wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> covering problem
        
(Message started by: BNC on Jan 19^th, 2007, 2:32pm)

Title: covering problem
Post by BNC on Jan 19^th, 2007, 2:32pm

A friend of mine told me he think he came up with an algorithm for solving the covering problem. He asked for my help in demonstrating / proving it.

Is it a well-known problem? Is it NP or P? Are there any / many algorithms to solve it?

Thanks!

Note: The covering problem (or at least the variant I'm dealing with) is: given an area composed of squares (the area may be any shape, connected), and a cell, also composed of squares, what is the minimal number of cells needed to cover the whole area>

Title: Re: covering problem
Post by THUDandBLUNDER on Jan 19^th, 2007, 6:44pm

Sounds like the Set Cover (http://en.wikipedia.org/wiki/Set_cover_problem) problem.

Title: Re: covering problem
Post by BNC on Jan 19^th, 2007, 10:14pm

But is it identical?

A simple example of the covering problem I was presented with may be this:
Take a chess board, with N (N>=0) of its squares removed, but in such a way that it's still connected (one area).
Now, take a simple shape -- say a domino like 1X2 element, or a cross-like element (a center piece, and its immediate neighbors to the E, W, S, N).
How many elements are required to cover the whole area?
elements may overlap, and they may "cover" squares outside of the area. They may not be turned, though.