Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

upobir's blog

By upobir, history, 4 years ago, In English

Consider $$$n$$$ 2d disks, suppose I want to find out the shape of their common area. This shape would be made up of some arcs of the disks. How many arcs can there be at most? My intuition says it should be $$$O(n)$$$, but I can't prove it, any help would be apreciated.

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
4 years ago, # |
Rev. 3   Vote: I like it +51 Vote: I do not like it

I believe your intuition is correct. In fact, I think the maximum number is exactly $$$2n-2$$$ for $$$n > 1$$$. Here is a basic argument:

Suppose $$$n > 2$$$ and consider the disk $$$D$$$ which has the largest radius among any in the set. If none of its arc segments are on the boundary of the intersection, we can simply consider the remaining $$$n-1$$$ disks. Otherwise, I claim that the part of its boundary $$$\partial D$$$ which belongs to the intersection consists of exactly one contiguous segment. To see this intuitively, note that the curvature at any point on the boundary of the intersection must be at least as high as that of the boundary of $$$D$$$. (To see this rigorously, prove that any disk which contains two points $$$x$$$ and $$$y$$$ in $$$\partial D$$$ and has radius no larger than that of $$$D$$$ contains the entire (at most 180 degree) arc between them.) As a result, removing $$$D$$$ from the set and considering the intersection of the remaining $$$n-1$$$ disks will directly remove at most 1 arc, and merge at most 1 pair of previously distinct arcs, decreasing the total number of arcs by at most 2.

Since there are at most 2 arcs when $$$n = 2$$$, my earlier bound of $$$2n-2$$$ for $$$n > 1$$$ follows from this by induction. (To actually achieve this bound, consider cutting off $$$n-1$$$ "corners" of a single small circle with very large circles.)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The proof seems sound to me, thanks!