I have coordinate points (x,y) say I have 10 000 points . now when a new point is given as test query say (p,q). I have to check with every point in coordinate points.if x coordinate of text query that is P Y from online searches I came to know that Rmq- range min/max query datastructure can help me but I am not sure how to do it..can some one help me how may i do this ..any references or code help in c++ will be of great help .thank you
1
votes
Can you clarify what you're asking? What do you want to do with the test point? Are you trying to find the closest point to it? Are you trying to check whether the point exists in the data set?
- templatetypedef
I am trying to find if the point exits in the dataset
- Nichole Grace
more precisely I tried to get suffix array ranges of input text .that is if a string when checked with suffix array .. then it gives range which encloses all its suffixes . Now i managed to get suffix range of text with respect to the suffix array of input text . Now Im trying to see if the suffix range of input text is prefix of the test string. to test this I may have to use rmq or some good datastructure to check this case for time efficiency
- Nichole Grace
I'm not sure I see what your (x, y) points are in this case. Can you elaborate on this?
- templatetypedef
I am trying to check if the test string is prefix of input or input string is prefix of test string
- Nichole Grace
1 Answers
3
votes
If your goal is to check whether the point exists in the data set, then there are a number of really useful data structures you could use to hold the data, each of which supports very efficient lookups.
For starters, if all you need to know is whether or not the point exists, you could always store all the points in a standard hash table or balanced binary search tree. This would offer O(1) or O(log n) lookup time, respectively. Plus these structures tend to be available in most programming languages.
If, on the other hand, you're planning on doing fancier operations on the data, such as searching for the k points in the data set nearest some test point, or trying to find all of the points in some bounding area, you might want to consider using a kd-tree or a quadtree. These variants on the standard binary search offer fast lookups (O(log n) time). The kd-tree also supports very fast k-nearest-neighbor searches and searches inside of bounding volumes. Moreover, the kd-tree is surprisingly easy to implement if you have any experience implementing a standard binary search tree.
Hope this helps!
