Re: Covering rectangles in 2D
- From: quasi <quasi@xxxxxxxx>
- Date: Sun, 16 Mar 2008 22:43:49 -0500
On Mon, 17 Mar 2008 02:58:00 -0000, Tim Little
<tim@xxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
On 2008-03-16, Hector <encapuchado@xxxxxxxxx> wrote:
Suppose there is a big rectangle, 'A', and suppose that I put
several smaller rectangles over 'A'. The small rectangles can be
overlapped, but they are all inside 'A'. The question is, is it
possible to know whether 'A' is totally covered?
Sure: if nothing else, divide A up into a grid using the edges of the
rectangles as grid lines.
In general this would be O(N^2) in the number of rectangles, which is
a bit of a nuisance. I'm sure there are faster methods.
That's a nice method.
But I highly doubt that you can do better than O(N^2).
In fact, I don't even see how the method you suggest _is_ O(N^2).
Perhaps I misunderstand your intended method, but as I see it, it's
O(N^3).
On the other hand, the algorithm I proposed _is_ O(N^2), or at least
I'm fairly sure that it is, and moreover, I believe that my algorithm
is best possible as far as order of magnitude.
quasi
.
- Follow-Ups:
- Re: Covering rectangles in 2D
- From: Tim Little
- Re: Covering rectangles in 2D
- References:
- Covering rectangles in 2D
- From: Hector
- Re: Covering rectangles in 2D
- From: Tim Little
- Covering rectangles in 2D
- Prev by Date: Discrete Mathematics Problem (Tucker)
- Next by Date: Re: groups
- Previous by thread: Re: Covering rectangles in 2D
- Next by thread: Re: Covering rectangles in 2D
- Index(es):
Relevant Pages
|
