Data structure to pre-process given set of N points and given a query parallel strip output all points lie within the strip

Question

I was asked to design an algorithm that pre-process the given set of N points such the given a query parallel strip that output all points lie within the strip.

I tried to design the algorithm but I am only able to solve the query separately.

I do not know which data-structure to use and pre-process the Given N points such the i can answer the queries easily.

I just need an idea about how to do it, and what complexity it will have.

Answer 1

The usual way of solving such problems is to use a bounding volume hierarchy.

Think of packing the points in boxes, and those boxes in larger boxes, etc... If one of your larger boxes is entirely outside the strip, then you don't need to check it. However, if it's inside the strip, then you'll have to take a look at what's inside. If what's inside has a box that isn't in the strip, you don't have to check the contents of that box, either. The key, of course, is packaging the boxes such that you can usually skip checking a lot of the sub-boxes and points.

(Note that not all BVHs use boxes -- some use spheres, some use simplices, some use a somewhat weirder partitioning, but most use boxes.)

R-trees are popular for 2D applications in large databases. You can also use a space partitioning structure (which are more or less just a specialization of BVHs), and you might do so because there's a lot of libraries out there for K-d trees (a type of space partitioning) already.

No matter what structure you end up, the top-level algorithm will remain the same:

# This algorithm could be implemented with a stack or recursively
# instead of maintaining a potentially very long list of nodes.
nodes = { top_level_node }
loop while there are nodes left to process
    set node = first element of nodes
    remove node from nodes
    if node does not intersect strip continue loop
    if node directly contains points that are within the strip add them to the output
    if node directly contains subnodes that intersect the strip add them to nodes
end loop

Depending on the structure you use, for a fixed number of dimensions you can expect the general behavior to be O(o log n) where n is the number of points total and o is the number of points within a strip. Note that this somewhat naive algorithm uses O(o) memory, but it could use O(log n) instead if a stack or recursion is used.

The Box2D physics engine has a decent 2D BVH implementation that is pretty easy to utilize. (License looks very permissive.) At one point Box2D's BVH was based on Bullet's (and may be still). The Bullet physics engine has a 3D BVH implementation that I've converted to 2D before and it has a zlib (very permissive) license. The problem with realtime physics engines is that they're typically not interested in getting an optimal tree -- they're interested in getting it "as good as possible" within few milliseconds because they don't have time for optimal. However, they may be good enough for your purposes.

Rosettacode even has a K-d tree entry -- but your mileage may vary as I'd expect these entries to be less tested than a well-used library (such as FLANN which I believe includes a K-d tree.)