Introduction to Priority Search Trees in Computational Geometry
This lecture outlines the structure and query process of Priority Search Trees (PST) in computational geometry. It covers heap-based point queries, range trees for windowing queries, handling query ranges in 1D and 2D spaces, and using heaps to efficiently handle query ranges. The content discusses how to integrate information about coordinates without associated structures in handling query ranges. The examples and explanations provide insights into efficient data structuring and usage in computational geometry.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Priority Search Trees Outline: I. Heap-based point queries II. Structure of a PST III. Query IV. Correctness and running time Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.
Windowing Queries with an Interval Tree ???? Range tree on left endpoints Range tree on right endpoints Complicated data structure due to the uses of range tree and fractional cascading for efficiency. High storage: ?(?log?) Improvement? Explore that the query range is unbounded on one side ( or over ?). Use a simpler data structure to cut down storage to ?(?). Priority search tree
I. Query Problem Point set: ? = ?1,?2, ,?? Query range: ( ,??] [??,?? ] Let us think small to start with the 1D case first. Range: ( ,??] Order the points ?1< ?2< < ??. ?? ??+1 ?2 ?1 ?? ?? Start at the leftmost point and walk toward right until ??+1> ??. Report ?1,?2, ,?? during the walk ?(1 + ?)
Moving on to 2D Query Among the points with ?-coordinates in ,??, select those whose ?-coordinates are in [??,?? ]. How to exploit ,?? being half-open? Property Every internal node stores the minimum value of the subtree rooted at the node. Use a min heap. 1 11 3 13 22 6 9 40 8 {1,3,11,6,9,13,22,8,40}
First Query Range Handled by a Heap Point set: ? = ?1,?2, ,?? Query range: ( ,??] Walk down the tree. At each node with stored point ? = (??,??) check if ?? ??. If yes, report ? and continue in both subtrees ? and ?. ? Otherwise (??>??), abort the subtree ?(?) rooted at ?. ? ? Every node ? = (??,??) ? in ?(?) satisfies ?? ??> ??
Example ( ,12] on the heap below. 1 1 11 11 3 3 13 22 6 6 9 9 40 37 8 8 24 Report 1, 3, 6, 8, 9, 11.
Both Query Ranges Handled by a Heap Point set: ? = ?1,?2, ,?? Query range: ( ,??] [??,?? ] A set can be represented by many heaps, each representing a way of partitioning the set. How to integrate the information about the ?-coordinate without using the associated structures? We can choose a heap that partitions the set according to the ?-coordinate. Split the remainder of the set into two subsets such that the points in one subset have their ?-coordinates less than those of the points in the other subset.
II. Priority Search Tree (PST) ?3 ?1 ?3 Rotated counterclockwise for visualization purpose ?1 ?5 ?4 ?5 ?7 ?4 ?6 ?7 ?2 ?6 ?4is at the root because it has the smallest ?-coordinate. Of the remaining 6 points, ?7has the median ?-coordinate. ?2 This median splits them into two groups: ?2, ?6, ?7 stored in the left (lower) subtree and ?1, ?3, ?5 stored in the right (upper) subtree. ?6and ?1are the roots of the two subtrees because they have the smallest ?-coordinates in their groups, and so on.
Formal Definition of the PST Assumption No two points have the same ?- or ?-coordinate. (Easily removable with lexicographic ordering) If |?| = 1, then the tree has one node. Otherwise, ???? ? with the smallest ?-coordinate. ????: median ?-coordinate of the remaining points. ??????= ? ? { ???? | ?? ????}. ??????= ? ? { ???? | ??> ????}. Create ? ????, ???? Points are not stored at leaves only. Every node stores a different point. ?????? ??????
Construction Time ?(?log?)if recursively (top-down) ????, ???? ?????? ?????? ? ? if the points are pre-sorted on ?-coordinate, and constructed bottom-up in the way of building a heap.
III. Query Query range: ( ,??] [??,?? ] ? 1) Search the PST with ?? and ?? comparing them with the ???? value at each node. by 1D range searching ?????? ? The two searches end at the nodes ? and ? , respectively. ? ,?? ??,? Selected subtrees for future searches based on ?-coordinates
Nodes on the Search Paths Check every node ? on every one of the three paths, ? ??????, ?????? ? and ?????? ? to see if ? ] ?(?) ( ,??] [??,?? ?????? ? ,?? ??,?
Search in the Selected Subtrees 2) Search every selected subtree based on ?-coordinate as in a one-dimensional array. ? ??(?) ??(?) ReportInSubtree(?,??) // incorrect in the text for omitting // the case of ? as a leaf 1. if ? ? ? ?? 2. then report ?(?) 3. if ? is not a leaf 4. then ReportInSubtree(??(?),??) 5. ReportInSubtree(??(?),??) min heap on ?-coordinate
IV. Correctness of ReportInSubtree() LemmaReportInSubtree(?,??) reports in ? 1 + ??time all the ??points in the subtree ? ? whose ?-coordinate is at most ??. Proof Consider a node ? in ? ? such that its stored point ?(?) satisfies ? ? Along the (upward) path ? ? the ?-coordinates of the stored points decrease. ? ??. ? ?? ? ? ?> > ? ? ?> > ? ? ? Recursive calls to ReportInSubtree are invoked at all the nodes on the downward path ? ?. recursive calls to ReportInSubtree() ? ? ?(?) is reported. The time ? 1 + ?? follows from ?(1) effort spent on each node .
Query Algorithm ]) QueryPrioSearchTree(?,( ,??] [??,?? // ? is the root of ? 1. search with ?? and ?? 2. let ?????? be the node where the two paths split. 3. for each node ? on the path ? ? or ?????? ? 4. do if ?(?) ( ,??] [??,?? 5. then report ?(?) 6. for each node ? on ?????? ? 7. do if the path goes left at ? 8. then ReportInSubtree(??(?), ??) 9. for each node ? on ?????? ? 10. do if the path goes right at ? 11. then ReportInSubtree(??(?), ??) in ?, ending at the nodes ? and ? ]
Example of Execution ?3 ReportInSubtree(?5,??) ?? ?3 ?3 ) ?1 (??,?? Returns ?4, ?7, ?1. ?1 ?1 ?5 ?5 ?5 ?4 ?7 (??,??) ?4 ?4 ?? ?6 ?7 ?7 ?2 ??????= ?4 ?6 ?6 ]) QueryPrioSearchTree(?,( ,??] [??,?? // ? is the root of ? 1. search with ?? and ?? 2. let ?????? be the node where the two paths split. 3. for each node ? on the path ? ? or ?????? ? 4. do if ?(?) ( ,??] [??,?? 5. then report ?(?) 6. for each node ? on ?????? ? 7. do if the path goes left at ? 8. then ReportInSubtree(??(?), ??) 9. for each node ? on ?????? ? 10. do if the path goes right at ? 11. then ReportInSubtree(??(?), ??) in ?, ending at the nodes ? and ? ?2 ] ReportInSubtree(?,??) if (? ? )? ?? then report ?(?) if ? is not a leaf then ReportInSubtree(??(?),??) ReportInSubtree(??(?),??) 1. 2. 3. 4. 5.
Running Time ]) QueryPrioSearchTree(?,( ,??] [??,?? // ? is the root of ? 1. search with ?? and ?? 2. let ?????? be the node where the two paths split. 3. for each node ? on the path ? ? or ?????? ? 4. do if ?(?) ( ,??] [??,?? 5. then report ?(?) 6. for each node ? on ?????? ? 7. do if the path goes left at ? 8. then ReportInSubtree(??(?), ??) 9. for each node ? on ?????? ? 10. do if the path goes right at ? 11. then ReportInSubtree(??(?), ??) in ?, ending at the nodes ? and ? ] ReportInSubtree(?,??) // ?(?) ? ? ? ?? 1. 2. 3. 4. 5. if then report ?(?) if ? is not a leaf then ReportInSubtree(??(?),??) ReportInSubtree(??(?),??) Time cost breaks down to two parts: number of nodes on the path ? ? or ?????? ? number of recursive calls to ReportInSubtree(). ?(log?) ?(?) ?(log? + ?) # reported points
Summary on PST Min heap over the ?-coordinate. Binary search tree over the ?-coordinate. Storage ?(?) Construction time ?(?log?) Query time ?(log? + ?)
