Could the original question be missing something, like the specification of the rectangle being a longer operation, such as O(log n)?
A dominance relationship structure (storage: O(n^2)) has, after you use inclusion/exclusion to specify the rectangle, a query time of O(1). Could that be what he is looking for? On Jun 27, 2:05 pm, Luke Schafer <[EMAIL PROTECTED]> wrote: > Sorry, I'd like some clarification: > > What do you mean exactly by O(1) time? If the rectangle is not known > to the set prior to the query, I don't see how, given the > multidimensional nature of the data, this could be achieved. Would you > count two separate O(1) lookups as O(1)? Or how about two O(1) and an > intersection (that's the simplest solution)? The best other solution I > could come up with is O(n^(1/2) +k) on a kd-tree (also, O(n log n) [i > think] using divide and conquer). Is there a finite maximum magnitude > of each axis? Is this an axis-parallel rectangle we’re searching on? > > Sorry, it's been a very long time since I've done much work with > optimizing algorithms, I don't remember much. That's not to say I was > even that great in the first place :). I'd like to know the solution > to this as well, if someone comes up with it. > > Thanks. > > On Jun 14, 12:17 am, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote: > > > I guess playing a bit with the slopes of the sides of the rectangle and the > > slopes of the lines formed by the rectangle vertices and the individual n > > points will gie the answer. Not thought about the complexity though. > > > On Fri, Jun 13, 2008 at 7:39 PM, Raghavendra Sharma < > > > [EMAIL PROTECTED]> wrote: > > > Hi, > > > > There are n points in a plane (p1,p2.... pn). Design a O(N2) data > > > structure > > > so as to answer the querry > > > "How many points are there in this rectangle" in O(1) time > > > > The rectangle will be specified by the lower left point and upper right > > > point. > > > > Thanks, > > > Raghavendra > > > -- > > Ciao, > > Ajinkya --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
