3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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:


   Abstract
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) (PDF download):
            Fig2.2

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Mar 20, 2013 at 0:30
  • $\begingroup$ @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. $\endgroup$ Mar 20, 2013 at 0:57
  • $\begingroup$ 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 $\endgroup$ Mar 20, 2013 at 1:28
  • $\begingroup$ If we're allowed four crossings, thin rectangles arranged in a square grid pattern gives the $\Omega(n^2)$ lower bound, right? $\endgroup$ Mar 20, 2013 at 2:04
  • $\begingroup$ @Michael: Yes! :-) $\endgroup$ Mar 20, 2013 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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