麻省理工学院：《算法导论》（英文版） Lecture 12 Prof erik demaine

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

ID range searching In ld. the query is an interval First solution using ideas we know Interval trees Represent each point x by the interval [x,x Obtain a dynamic structure that can list k answers in a query in O(k Ig n) time c 2001 by erik D. Demaine Introduction to Ago orns Day 21 L12.6

© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.6 1D range searching In 1D, the query is an interval: First solution using ideas we know: • Interval trees • Represent each point x by the interval [x, x]. • Obtain a dynamic structure that can list k answers in a query in O(k lg n) time

ID range searching In ld. the query is an interval Second solution using ideas we know Sort the points and store them in an array Solve query by binary search on endpoints Obtain a static structure that can list k answers in a query in O(k + Ig n)time Goal: obtain a dynamic structure that can list k answers in a query in O(k+lg n)time c 2001 by erik D. Demaine Introduction to Agorithms Day 21 L12.7

© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.7 1D range searching In 1D, the query is an interval: Second solution using ideas we know: • Sort the points and store them in an array • Solve query by binary search on endpoints. • Obtain a static structure that can list k answers in a query in O(k + lg n) time. Goal: Obtain a dynamic structure that can list k answers in a query in O(k + lg n) time

ID range searching In ld. the query is an interval New solution that extends to higher dimensions Balanced binary search tree New organization principle Store points in the leaves of the tree Internal nodes store copies of the leaves to satisfy binary search property Node x stores in key the maximum key of any leaf in the left subtree ofx c 2001 by erik D. Demaine Introduction to Algorithms Day 21 L12. 8

© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.8 1D range searching In 1D, the query is an interval: New solution that extends to higher dimensions: • Balanced binary search tree • New organization principle: Store points in the leaves of the tree. • Internal nodes store copies of the leaves to satisfy binary search property: • Node x stores in key[x] the maximum key of any leaf in the left subtree of x

Example of a lD range tree 43 681214 261354142 5961 c 2001 by erik D. Demaine Introduction to Algorithms Day 21 L12.9

© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.9 Example of a 1D range tree 11 66 88 1212 1414 1717 2626 3535 4141 4242 4343 5959 6161

Example of a lD range tree 42 14 35 43 2)17(26)(41)43(59 681214 261354142 5961 c 2001 by erik D. Demaine Introduction to Algorithms Dav2112.10

© 2001 by Erik D. Demaine Introduction to Algorithms Day 21 L12.10 Example of a 1D range tree 11 1212 66 88 1212 1414 1717 2626 3535 4141 4242 4343 5959 6161 66 2626 4141 5959 11 1414 3535 4343 88 4242 1717 xx ≤ x > x