Re: Covering rectangles in 2D

On Tue, 18 Mar 2008 03:18:04 -0000, Tim Little
<tim@xxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

On 2008-03-17, quasi <quasi@xxxxxxxx> wrote:
I'm not sure what this means. If you are visiting every cell formed by
the grid lines, that O(N^2), right there

Yes, that's where the O(N^2) comes from.


Does passing a grid line means you are sweeping down a column, or
does it mean you have finished sweeping across the row above and are
proceeding to the next row?

Either/both. It just means crossing from one cell of the grid to a
neighbouring cell.


Also, a grid line is not, in general, an edge of a rectangle, so I
don't know what you mean by "check whether it was a real edge".

Each of the (unevenly spaced) grid lines is generated by a rectangle
that has a side aligned along that X or Y coordinate. In general
there are up to 4 of these, 2 vertical and 2 horizontal.

Each transition from one grid cell to a neighbouring one crosses a
grid line, hence is associated with a rectangle (or list of
rectangles, but we can treat this much like a sequence of grid lines
with 0 separation).

So all we need do is check that rectangle to see whether the
transition enters or leaves that rectangle.


If it was real, increment or decrement the count of currently
overlapping rectangles.

I don't follow.

As we sweep through the grid, we keep a count of how many rectangles
are covering the cell we're looking at. Passing a grid line can
change that count by -1, 0, or +1. Checking which is an O(1)
operation.

You might be right -- maybe it's O(N*log N), but I'm not convinced.

Nor am I. O(N log N) might be a bit ambitious, but perhaps O(N^1.5)
is achievable.

I don't really understand your algorithm, but from what I can follow,
I don't think you achieved O(N^2). There are O(N^2) cells, right? And
it appears your method visits all of them, one at a time. Of course
that's at least O(N^2) right there, but when you visit a cell,
checking whether or not that cell is occupied is not O(1). Checking a
cell is at most O(N), so for the full grid, O(N^3) is the worst case.
With some pre-sorting of the rectangles, perhaps you can get less than
O(N^3), but I don't see O(N^2), not from what you described.

quasi
.

Relevant Pages

  • Re: Covering rectangles in 2D
    ... since it seems you only care about grid lines that can be ... crossing from a cell to an adjoining cell, ... chose for each rectangle to define a grid line, ...
    (sci.math)
  • Re: Covering rectangles in 2D
    ... insure uniqueness. ... In other words, if 2 cells share a grid line, you ... crossing from a cell to an adjoining cell, ... chose for each rectangle to define a grid line, ...
    (sci.math)
  • Re: Covering rectangles in 2D
    ... Sort the x and y bounds of each rectangle, ... associated with exactly two grid lines. ... crossing from a cell to an adjoining cell, ... Increment, decrement, or leave C unchanged accordingly. ...
    (sci.math)
  • Re: Grid and Array Association
    ... When all the calculations are completed, you want to put the total ... count for each date in the cell just below that date. ... Loop through GridArray assigning the date found at the top of the grid ... called dResult. ...
    (microsoft.public.vb.general.discussion)
  • Re: Grid and Array Association
    ... When all the calculations are completed, you want to put the total ... count for each date in the cell just below that date. ... Loop through GridArray assigning the date found at the top of the grid ... called dResult. ...
    (microsoft.public.vb.general.discussion)