Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 12 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 12 Prof. Erik Demaine
Computational geometry Algorithms for solving geometric problems in 2D and higher Fundamental objects: o point line segment Ine Basic structures point set polygon c 2001 by erik D. Demaine Introduction to Agorithms Day 21 L12.2
© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.2 Computational geometry Algorithms for solving “geometric problems” in 2D and higher. Fundamental objects: point line segment line Basic structures: point set polygon
Computational geometry Algorithms for solving geometric problems in 2D and higher Fundamental objects: o point line segment Ine Basic structures triangulation convex hull c 2001 by erik D. Demaine Introduction to Agorithms Day 21 L12.3
© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.3 Computational geometry Algorithms for solving “geometric problems” in 2D and higher. Fundamental objects: point line segment line Basic structures: triangulation convex hull
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
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