Sweep-plane approach to bounding box intersection
Tomasz Koziara, Nenad Bičanić · 2005
This paper summarises an effort towards approximation of an optimal sweepplane approach to axis aligned bounding box intersection problem. In particular a spatial hash table and priority search tree are combined in order to obtain a data structure suitable for solving two-dimensional dynamic rectangle intersection problem. Some variants of this structure allow logarithmic update and query times, although all of them suffer from repeated reports of intersections. This constrains an efficient application of presented algorithms only to sparse box distributions, where penalty of additional algorithmic effort for suppressing repeated reports is minor.