Counting circular arc intersections
Publication
, Conference
Agarwal, PK; Sharir, M
Published in: Proceedings of the Annual Symposium on Computational Geometry
June 1, 1991
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.
Published In
Proceedings of the Annual Symposium on Computational Geometry
DOI
ISBN
0897914260
Publication Date
June 1, 1991
Start / End Page
10 / 20
Citation
APA
Chicago
ICMJE
MLA
NLM
Agarwal, P. K., & Sharir, M. (1991). Counting circular arc intersections. In Proceedings of the Annual Symposium on Computational Geometry (pp. 10–20). https://doi.org/10.1145/109648.109650
Agarwal, P. K., and M. Sharir. “Counting circular arc intersections.” In Proceedings of the Annual Symposium on Computational Geometry, 10–20, 1991. https://doi.org/10.1145/109648.109650.
Agarwal PK, Sharir M. Counting circular arc intersections. In: Proceedings of the Annual Symposium on Computational Geometry. 1991. p. 10–20.
Agarwal, P. K., and M. Sharir. “Counting circular arc intersections.” Proceedings of the Annual Symposium on Computational Geometry, 1991, pp. 10–20. Scopus, doi:10.1145/109648.109650.
Agarwal PK, Sharir M. Counting circular arc intersections. Proceedings of the Annual Symposium on Computational Geometry. 1991. p. 10–20.
Published In
Proceedings of the Annual Symposium on Computational Geometry
DOI
ISBN
0897914260
Publication Date
June 1, 1991
Start / End Page
10 / 20