Orthogonal range searching Input: n points in d dimensions Query: Axis-aligned box (in 2D, a rectangle) Report on the points inside the box Goal: Preprocess points into a data structure to support fast queries Primary goal: Static data structure In id. we will also obtain a ynamic data structure supporting insert and delete c 2001 by erik D. Demaine Introduction to Agorithms Day 21 L12.5© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.5 Orthogonal range searching Input: n points in d dimensions Query: Axis-aligned box (in 2D, a rectangle) • Report on the points inside the box Goal: Preprocess points into a data structure to support fast queries • Primary goal: Static data structure • In 1D, we will also obtain a dynamic data structure supporting insert and delete