current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 2 down vote favorite
1

I am given a huge list of objects with attributes x and y. We are required to search for all objects lying between a given upper and lower bound of both the attributes.

I was wondering if there is an efficient algorithm to implement this.

Thanks!

share|improve this question
    
Regarding "required": note that if this is a homework question, please tag it as homework, thank you! –  ninjagecko Jul 11 '11 at 4:39
    
Hi, it is just one of my personal projects, and not a homework. So, I think I will leave it as it is. Thanks. –  Shubham.Shukla Jul 11 '11 at 7:44

2 Answers 2

up vote 1 down vote accepted

A quadtree or a spatial index (a space-filling curve, for example a hilbert curve).

share|improve this answer
    
Thanks, I will look into this. –  Shubham.Shukla Jul 11 '11 at 7:45
up vote 2 down vote

There are standard algorithms for this. See http://en.wikipedia.org/wiki/R-tree for one.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.