Tag range search

Rectangle Intersection

Given $N$ rectangles, find all the intersections. This algorithm is very similar to the 1-D line intersection search. The difference...

Posted by Beetle B. on Sun 12 October 2014

1-D Interval Intersection

Suppose we have $N$ 1-D intervals of the form $(a,b)$ where \(a

Posted by Beetle B. on Sat 11 October 2014

2-D Range Search, Points in a Box Search and K-D Trees

This is like the 1-D range search, but where the keys can now have two coordinates. It’s finding the number of points in a rectangle...

Posted by Beetle B. on Fri 10 October 2014

1-D Range Search and Line Intersection Search

Sample problems we want to solve: What are all the keys between two keys? (Relevant to databases) How many keys exist between two keys?...

Posted by Beetle B. on Fri 10 October 2014