Intersection queries in sets of disks

Published

Conference Paper

© Springer-Verlag Berlin Heidelberg 1990. In this paper we develop some new data structures for storing sets of disks such that different types of queries can be answered efficiently. In particular we study intersection queries with lines and line segments and shooting queries. In the case of non-intersecting disks we obtain structures that use linear storage and have a query time of O(nβ+ε + k) for intersection queries, where n is the number of disks, β = log2(l + √5) - 1 ≈ 0.695, ∊ is an arbitrarily small positive constant, and k is the number of disks reported. For sets of intersecting disks we obtain a structure that uses 0(n log n) storage and answers a query in time 0(n2/3 log2 n). For ray shooting we obtain a structure that uses linear storage and has O(nβ+ε) query time, for any ∊ > 0.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 1990

Published In

Volume / Issue

  • 447 LNCS /

Start / End Page

  • 393 - 403

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540528463

Digital Object Identifier (DOI)

  • 10.1007/3-540-52846-6_107

Citation Source

  • Scopus