Orthogonal range searching Input: n points in d dimensions E. g. representing a database of n records each with d numeric fields Query: Axis-aligned box (in 2D, a rectangle Report on the points inside the box Are there any points? How many are there? List the points c 2001 by erik D. Demaine Introduction to Algorithms Day 21 L12. 4© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.4 Orthogonal range searching Input: n points in d dimensions • E.g., representing a database of n records each with d numeric fields Query: Axis-aligned box (in 2D, a rectangle) • Report on the points inside the box: • Are there any points? • How many are there? • List the points