A New Algorithm for Counting Circular Arc Intersections

TitleA New Algorithm for Counting Circular Arc Intersections
Publication TypeTechnical Report
Year of Publication1992
AuthorsPellegrini, M.
Other Numbers715

We discuss the following problem: given a collection $Gamma$ of $n$ circular arcs in the plane, count all intersections between arcs of $Gamma$. We present an algorithm whose expected running time is $O(n^{3/2+eps})$, for every $eps >0$. If the arcs have all the same radius the expected time bound is $O(n^{4/3+eps})$, for every $eps>0$. Both results improve on the time bounds of previously known asymptotically fastest algorithms. The technique we use is quite general and it is applicable to other counting problems.

Bibliographic Notes

ICSI Technical Report TR-92-010

Abbreviated Authors

M. Pellegrini

ICSI Publication Type

Technical Report