The paper develops some new data structures for storing sets of disks such thatdifferent types of queries can be answered efficiently. In particular it studies intersection queries with lines and line segments and shooting queries. In the case of non-intersecting disks, it obtains structures that use linear storage and have a query time of O(n to the (Beta + Epsilon power + k) for intersection queries, where n is the number of disks, Beta = log(sub 2)(1 + square root of 5) - 1 is approximately equal to 0.695, Epsilon is an arbitrarily small positive constant, and k is the number of disks reported. For sets of intersecting disks it obtains a structure that uses O(n log n) storage and answers a query in time O(n to the (2/3) power log squared n). For ray shooting it obtains a structure that uses linear storage and has O(n to the (Beta + Epsilon) power) query time, for any Epsilon > 0.
展开▼
