Intersection queries in curved objects


Journal Article

A number of problems of the following type are studied: Given a set of n arcs (disks, circles, circular arcs, Jordan arcs) in the plane, preprocess it into a data structure, so that for a query line (or segment) one can quickly (i) report all arcs intersecting it, or (ii) count the number of arcs intersecting it. We also study the ray-shooting problem among disjoint Jordan arcs and circular arcs. Most of the data structures presented here use close to linear space and have query time close to O(√n + K) or O(n2/3 + K), where K is the size of the output. © 1993 Academic Press, Inc.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Van kreveld, M; Overmars, M

Published Date

  • January 1, 1993

Published In

Volume / Issue

  • 15 / 2

Start / End Page

  • 229 - 266

International Standard Serial Number (ISSN)

  • 0196-6774

Digital Object Identifier (DOI)

  • 10.1006/jagm.1993.1040

Citation Source

  • Scopus