Re: Covering rectangles in 2D
- From: quasi <quasi@xxxxxxxx>
- Date: Fri, 21 Mar 2008 22:38:01 -0500
On Sat, 22 Mar 2008 02:23:43 -0000, Tim Little
<tim@xxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
On 2008-03-22, quasi <quasi@xxxxxxxx> wrote:
when you visit a cell, checking whether or not that cell is occupied
is not O(1).
It is O(1). I'm not checking from scratch whether a cell is occupied.
I'm checking the *difference* between coverage of it and the
preceding, neighbouring cell.
Define "preceding, neigboring cell". Presumably there is some kind of
pre-sort which determines which cell preceeds which?
Because every grid line (and hence boundary between grid cells) is
generated by a known rectangle, that is the only rectangle I need to
examine.
But as far as I can see, you need to check every cell in a row (or
column), not just the one that generated the grid lines for that row
(or column).
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
- Re: Covering rectangles in 2D
- From: quasi
- Re: Covering rectangles in 2D
- From: Tim Little
- Re: Covering rectangles in 2D
- From: quasi
- Re: Covering rectangles in 2D
- From: Tim Little
- Re: Covering rectangles in 2D
- From: quasi
- Re: Covering rectangles in 2D
- From: Tim Little
- Covering rectangles in 2D
- Prev by Date: Re: the shortest and longest Good Fridays
- Next by Date: Re: math -- boolean combinations of rectangles
- Previous by thread: Re: Covering rectangles in 2D
- Next by thread: Re: Covering rectangles in 2D
- Index(es):
Relevant Pages
|
