geometric-search

**Problem ** Discuss Interval Search Tree Idea behind Interval Search Tree Lets discuss the 1D Interval search. By 1D I mean in 1 dimension i.e. having interval along 1 axis only. So, suppose along x axis we have collection of intervals - [1,2], [1,3] and so on. Here Interval Tree or Interval Search tree is helpful as it holds set of (overlapping) intervals Insert the interval Search delete Main functionality - Interval intersection query - given the interval (lo, hi) find all intervals in data structure which intersect with given interval. [Read More]

All these data structures are used for solving different problems: Segment tree stores intervals, and optimized for “which of these intervals contains a given point” queries. Interval tree stores intervals as well, but optimized for “which of these intervals overlap with a given interval” queries. It can also be used for point queries - similar to segment tree. Range tree stores points, and optimized for “which points fall within a given interval” queries. [Read More]

Input - 2 Rectangles with x and y coordinates. Output - boolean value which states if they overlap or not This is a one of the classic problems in graphics programming and game development. So, let’s see how we can solve it. Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. [Read More]