MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a process which in each step creates a new unit circle and I am interested in maintaining the boundary of the resulting arrangement in linear time. Is there anything known about computing this boundary?

I am a bit amazed that I can not find any literature related to this topic, since it is well known that although the unit circle arrangement has quadratic complexity, its boundary is linear.

share|cite|improve this question
up vote 2 down vote accepted

The paper that proved the linear $(6n-12)$ complexity of the boundary of the union of $n$ Jordan curves that intersect pairwise at most twice,

K. Kedem, R. Livne, J. Pach, and M. Sharir, "On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles," Discrete Comput. Geom., 1 (1986), 59–71. (Springer link)

also showed that one can construct this boundary in $O(n \log^2 n)$ time. See Section 4, "Efficient Calculation of $K$," 66ff. The algorithm is divide-and-conquer, and employs a plane-sweep idea of Ottmann, Widmeyer, and Wood.

Note that the result neither requires unit radius nor even circles, but only Jordan curves that intersect pairwise at most twice, which of course includes circles (and so unit circles).

Here is the first two sentences of the abstract of the above paper:

And here is a figure illustrating the proof for disks in the later survey paper, "State of the Union (of Geometric Objects)," by Agarwal, Pach, Sharir (Proc. Joint Summer Research Conference on Discrete and Computational Geometry--Twenty Years later, Contemp. Math, AMS, Providence, RI, 154):

share|cite|improve this answer
Can you make clear the intersection condition? In particular, I am concerned with a unit circle intersecting the union boundary in many points. If the theory needs only that union members taken pairwise have small number of intersection points, then I am less worried, but your wording does not make this clear to me. Further, I wonder how the algorithm is affected if 2 points is replaced by 4 or even 3. Gerhard "Ask Me About System Design" Paseman, 2013.03.19 – Gerhard Paseman Mar 20 '13 at 0:30
@Gerhard: (1) I included now the beginning of the abstract in the hope that makes the intersection condition more clear. (2) If each pair of curves can intersect at most four times, already there are examples whose boundary contains $\Omega(n^2)$ curve intersection points. – Joseph O'Rourke Mar 20 '13 at 0:57
Thanks, Joseph. The abstract helped very much. While I am intrigued by the omega n^2 comment and would like some insight, I am also willing to accept it and move on. Gerhard "Ask Me About System Design" Paseman, 2013.03.19 – Gerhard Paseman Mar 20 '13 at 1:28
If we're allowed four crossings, thin rectangles arranged in a square grid pattern gives the $\Omega(n^2)$ lower bound, right? – Michael Biro Mar 20 '13 at 2:04
@Michael: Yes! :-) – Joseph O'Rourke Mar 20 '13 at 9:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.