Intersection queries for curved objects


Conference Paper

© 1991 ACM. The following class of query problems is studied: Given a set of n arcs (disks, circles, circular arcs, Jordan arcs) in the plane, preprocess it into a data structure, such that for a query line (or segment) ℓ, one can quickly (i) report all arcs intersecting ℓ, or (ii) count the number of arcs intersecting ℓ. We also study the ray shooting problem for disjoint Jordan arcs and for circular arcs. Most of the data structures presented here use linear or near to linear space and have query time near to O(√n+K) or O(n2/3 + K), where K is the size of the output. The query time of some of our algorithms can be improved by allowing more space.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • June 1, 1991

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 41 - 50

International Standard Book Number 10 (ISBN-10)

  • 0897914260

Digital Object Identifier (DOI)

  • 10.1145/109648.109653

Citation Source

  • Scopus