Publication Details
Title: A New Algorithm for Counting Circular Arc Intersections
Author: M. Pellegrini
Group: ICSI Technical Reports
Date: February 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-010.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-010
Bibliographic Reference:
M. Pellegrini. A New Algorithm for Counting Circular Arc Intersections. ICSI Technical Report TR-92-010, February 1992
Author: M. Pellegrini
Group: ICSI Technical Reports
Date: February 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-010.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-010
Bibliographic Reference:
M. Pellegrini. A New Algorithm for Counting Circular Arc Intersections. ICSI Technical Report TR-92-010, February 1992