Counting circular arc intersections

Published

Conference Paper

© 1991 ACM. In this paper we present efficient algorithms for counting intersections in a collection of circles or circular arcs. We present a randomized algorithm to count intersections in a collection of n circles whose expected running time is O(n3/2+ϵ), for any ∈ > 0. We also develop another randomized algorithm to count intersections in a set of n circular arcs whose expected running time is O(n5/3+∈), for any ∈ > 0. If all arcs have the same radius, the (expected) running time can be improved to O(n3/2+∈), for any ∈ > 0.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sharir, M

Published Date

  • June 1, 1991

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 10 - 20

International Standard Book Number 10 (ISBN-10)

  • 0897914260

Digital Object Identifier (DOI)

  • 10.1145/109648.109650

Citation Source

  • Scopus