Multidimensional/Spatial Structures
17Multidimensional Spatial Data Structures Hanan Samet
Introduction•Point Data•Bucketing Methods•Region Data•Rectangle Data•Line Data and Boundaries of Regions•Research Issues and Summary•Acknowledgment•References
18Planar Straight Line Graphs Siu-Wing Cheng
Introduction•Features of PSLGs•Operations on PSLGs•Winged-Edge•Halfedge•Quadedge•Further Remarks•Glossary•Acknowledgments•References
19Interval, Segment, Range, and Priority Search Trees D. T. Lee and Hung-I Yu
Introduction•Interval Trees•Segment Trees•Range Trees•Priority Search Trees•Acknowledgments•References
20Quadtrees and Octrees Srinivas Aluru
Introduction•Quadtrees for Point Data•Spatial Queries with Region Quadtrees•Image Processing Applications•Scientific Computing Applications•Acknowledgments•References
21Binary Space Partitioning Trees Bruce F. Naylor
Introduction•BSP Trees as a Multi-Dimensional Search Structure•Visibility Orderings•BSP Tree as a Hierarchy of Regions•Bibliography
22R-Trees Scott Leutenegger and Mario A. Lopez
Introduction•Basic Concepts•Improving Performance•Advanced Operations•Analytical Models•Acknowledgment•References
23Managing Spatiotemporal Data Sumeet Dua and S. S. Iyengar
Introduction and Background•Overlapping Linear Quadtree•3D R-Tree•2+3 R-Tree•HR-Trees•MV3R-Tree•Indexing Structures for Continuously Moving Objects•References
24Kinetic Data Structures Leonidas Guibas
Introduction•Motion in Computational Geometry•Motion Models•Kinetic Data Structures•A KDS Application Survey•Querying Moving Objects•Sources and Related Materials•References
25Online Dictionary Structures Teofilo F. Gonzalez
Introduction•Trie Implementations•Binary Search Tree Implementations•Balanced BST Implementation•Additional Operations•Discussion•References
Introduction•The Cutting Construction•Applications•Acknowledgments•References
27Approximate Geometric Query Structures Christian A. Duncan and Michael T. Goodrich
Introduction•General Terminology•Approximate Queries•Quasi-BAR Bounds•BBD Trees•BAR Trees•Maximum-Spread k-d Trees•Acknowledgments•References
28Geometric and Spatial Data Structures in External Memory Jeffrey Scott Vitter
Introduction•EM Algorithms for Batched Geometric Problems•EM Tree Data Structures•Spatial Data Structures and Range Search•Related Problems•Dynamic and Kinetic Data Structures•Conclusion•Acknowledgments•References