Intersection queries in sets of disks

Published

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • van Kreveld, M; Overmars, M; Agarwal, PK

Published Date

  • June 1, 1992

Published In

Volume / Issue

  • 32 / 2

Start / End Page

  • 268 - 279

Electronic International Standard Serial Number (EISSN)

  • 1572-9125

International Standard Serial Number (ISSN)

  • 0006-3835

Digital Object Identifier (DOI)

  • 10.1007/BF01994881

Citation Source

  • Scopus