Re: Need idears to solve an algorithmic problem

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 11/14/04 

Date: Sat, 13 Nov 2004 20:00:01 -0500 (EST)

On Sat, 13 Nov 2004, Jesper Thygesen wrote:
>
> cri@tiac.net (Richard Harter) wrote
>> There is a standard trick that you can use. For each map determine
>> its minimum and maximum x and y coordinates. Sort on these values.
>> Then, given a point {x0,y0}, search for the maps that could possibly
>> contain the point. (If it is not clear how this works, ask.)
>
> I am not sure how to most effeciently sort such data, being in two
> dimensions. A little elaboration would be greatly appreciated :o)

   Richard doesn't mean any kind of "2D sort." Just make two lists,
one of X coordinates and one of Y coordinates, and sort them
independently. Then, to find out which boxes might contain a given
point (X0, Y0), I'd do the following (though Richard might have something
more clever in mind):

   Initialize two "live lists" of boxes, both initially empty; one of them
is for the X coordinates and one for the Y coordinates.
   Start at the low end of the X-list, and go upwards until you pass X0.
Each time you pass the minimum X-value of box Bi, add Bi to your "live
list X." Each time you pass the maximum X-value of box Bi, delete Bi from
your "live list X." Stop once you get to X0.
   Repeat the same process for Y0 and the Y coordinate list.
   Take the intersection of "live list X" and "live list Y." These are
the boxes that might contain (X0, Y0). Examine each of them using the
naive algorithm.

   Example: Let's suppose we have three boxes in our map.

     Box B1: (0,4) (2,5) (3,3) (1,2)
     Box B2: (2,2) (6,2) (6,0) (2,0)
     Box B3: (5,4) (8,4) (8,1) (5,1)

We take the minimum and maximum X and Y values for each box:

     x1,y1,X1,Y1: 0,2,3,5
     x2,y2,X2,Y2: 2,0,6,2
     x3,y3,X3,Y3: 5,1,8,4

Sort the X and Y values separately, keeping the labels attached:

     Xlist: x1=0, x2=2, X1=3, x3=5, X2=6, X3=8
     Ylist: y2=0, y3=1, y1=Y2=2, Y3=4, Y1=5

That was the setup phase. Now we're given a point to find. Let's
say we're given the point (4,3) (which isn't in any of the boxes, by
the way).

     Xlive := [], Ylive := []

Step through 'Xlist' until passing 4:

     Xlist[0] = 0; add B1 to Xlive := [B1]
     Xlist[1] = 2; add B2 to Xlive := [B1,B2]
     Xlist[2] = 3; delete B1 from Xlive := [B2]
     Xlist[3] = 5 > 4; stop

Step through 'Ylist' until passing 3:

     Ylist: y2=0, y3=1, y1=Y2=2, Y3=4, Y1=5
     Ylist[0] = 0; add B2 to Ylive := [B2]
     Ylist[1] = 1; add B3 to Ylive := [B2,B3]
     Ylist[2] = 2; add B1 to Ylive := [B1,B2,B3]
     Ylist[3] = 2; delete B2 from Ylive := [B1,B3]
     Ylist[4] = 4 > 3; stop

Now intersect the sets:

     Candidates := Xlive ^ Ylive = [B2]^[B1,B3] = []

The point isn't in any of the boxes.

HTH,
-Arthur

Relevant Pages

  • Re: Need idears to solve an algorithmic problem
    ... >> cri@tiac.net (Richard Harter) wrote ... >> I am not sure how to most effeciently sort such data, ... Oby precomputing a search formula.)The admissable boxes are then ... of the intersection of the two sets of admissables. ...
    (comp.programming)
  • OT: Birthday, London, Friday
    ... You can see how the two discoveries were sort of simultaneous. ... underground map, and one of the allegedly realist ones it replaced; ... was the motto of Michelin and is the nickname of the ... The building has three large stained glass panels depicting ...
    (rec.arts.mystery)
  • Re: i got trapped in Wales because
    ... I've never caught her holding the map upside ... To be honest, I've never actually used a 'carbide lamp', but the ones ... meant for vehicles that I've seen lacked any sort of 'lighter' of their ... Paraffin lamps almost always need a match or something. ...
    (uk.people.support.depression)
  • Re: Spoilered for talk of religion
    ... Beats following someone else's map if you ask me - if you do that, ... around me', get on with things, complete a task, that sort of thing. ... That sort of gamble is a `near 100% gamble' as far ...
    (uk.people.support.depression)
  • Re: Finding, sharing and starting jam sessions
    ... offer which sort of music, let alone whether I can join in or not. ... Additionally, each post lists ... folkjam.org with a private map and forum. ... the domestic jams on the site in anything less than a year. ...
    (rec.music.folk)