Finding strongly connected components of circle cover graph in one-dimensional
Ching-Ho Huang, Nen‐Fu Huang, Wen-Tsuen Chen · 2003
Given a set C=(c/sub 1/, c/sub 2/, . . ., c/sub n/) of n circles in the plane, the circle cover graph is the digraph G(C)=(V, E) where a vertex upsilon /sub i/ in V stands for the center of circle c/sub i/, and a directed edgein E if and only if circle c/sub i/ covers the center of circle c/sub j/. The authors propose an O(n log n) algorithm with O(n) space to find all the strongly connected components of G(C) for the one-dimensional case. Based on this result, the time complexity of the algorithm proposed by N.F. Huang, C.H. Huang (Inf. Process. Lett., vol.40, p.13-20, October, 1991) to solve the repeaters allocation problem for one-dimensional case can be improved from O(n log n+e) to O(n log n); where e is the number of edges in G(C).>