Intersection queries in sets of disks
In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report all k disks intersecting a query line segment in time O(nβ+ε+k), where n is the number of disks, β=log2(1+√5)-1 ≈ 0.695, and ε is an arbitrarily small positive constant. If the segment is a full line, the query time becomes O(nβ+k). For intersecting disks we obtain an O(n log n) size data structure that can answer an intersection query in time O(n2/3 log2n+k). We also present a linear size data structure for ray shooting queries, whose query time is O(nβ). © 1992 BIT Foundations.
van Kreveld, M; Overmars, M; Agarwal, PK
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)