ROUGH DRAFT authorea.com/113550
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • A6

    Intersecting Circles

    Algorithm and Runtime

    Form a pointset of all circle centers. Use a WSPD to find the closest pair of centers \(O(n\log n)\). Return disjoint if the distance between these points is > 1, non-disjoint else.

    Correctedness

    Disjoint circles

    \(\iff\) all pairwise circle centers are > 1 dist apart (unit circles, r=1)

    \(\iff\) the closest pair of points is > 1 dist apart \(\square\).

    CST

    Monopolar

    Algorithm

    • \(d\leftarrow \infty; u\leftarrow\) None
    • For all p in P: O(n)
      • Find the two points i,j furthest from p: \(O(n)\)
      • If \(|p,i| + |p,j|\) < \(d \): \(O(1)\)
        • d \(\leftarrow |p,i| + |p,j|\)
        • u \(\leftarrow p\)
    • Return unipolar MST formed from u.

    Runtime: \(O(n^2)\).

    Correctedness

    We consider all possible poles. The MST and diameter are unique given a pole. Clearly when we return the minimum over all of these trees we find the overall minimum diameter MST.

    Dipolar

    We want to do a process similar to above with all pair of points. In order to do so, we need an efficient way of calculating the diameter of a MST given poles \(i,j\), which we refer to as \(T_{ij}\).

    Let \(P_i, P_j\) be the points connected to \(i,j\) respectively in \(T_{ij}\). The diameter of the MST \(d(T_{ij}) = \max_{p \in P_i} |ip| + \max_{p \in P_j} |jp| + |ij|\). We can view our task as essentially centering a circle at each pole such that all points are covered by a circle, and the sum of the radii is minimum. We denote our two radii \(L_r, R_r\) for the circle centered at \(i,j\) respectively.

    Our radii are always going to be defined by an edge between our pole and points \(\in P-\{i,j\}\). This is evident -- we're seeking minimum distance so we're not going to go further than the last-covered point. Similarly, if we haven't covered a point we can't have a radius smaller than this edge.

    As such, we could simply iterate through all possible pairs and see which gets us the best diameter. This takes us to \(O(n^4)\) however, so we have to try a bit harder. It turns out we can get away with checking far fewer candidate radii.

    To see this, assume one circle is fixed and denote it L. Let the points covered by L be denoted \(P_L\). We don't need to consider any point \(\in P_L\) as a potential radius. Among all other candidates, we only need to find the point that is closest to j while covering everything else. This point is simply the furthest non-\(P_L\) point from j.

    We can exploit this structure by making our L as big as possible, and then shrinking it point by point. We start with our L radius being the point furthest from i, and then bringing it back point by point. Whenever we stop covering a point with L, we make sure that it is covered by R -- i.

    Subroutine: diameter(i,j,P)

    Input: i, j, P. i and j are poles. P is a list of our pointset-{i,j} sorted in decreasing order WRT distance to i.

    • Remove the first element from P and denote it x
    • \(L_r\leftarrow |i, x|\), \(R_r\leftarrow 0\).
    • \(L_p \leftarrow x\)
    • d \(\leftarrow L_r + R_r\)
    • For \(p \in P\): O(n)
      • \(R_r \leftarrow \max \{R_r, |j, L_p|\}\)
      • \(L_r \leftarrow |i,p|\); \(L_p \leftarrow p\)
      • d \(\leftarrow \min \{d, R_r + L_r\}\)
    • Return d + |i,j|

    Correctedness (of the sub-routine) follows from above -- we consider all radii which could potentially be diameter-defining, and simply return the minimum of all of these. Runtime is \(O(n)\).

    Main Algorithm

    We note that a poor implementation from this point can still result in \(O(n^3\log n\) runtime if we sort too frequently. As such, we sort after choosing each i -- not after choosing a pair i,j. That is:

    • a,b=None; d=\(\infty\)
    • For all points i \(\in P\): O(n)
      • \(P_s \leftarrow\) P-{i} sorted by decreasing distance t i: \(O(n \log n)\)
      • For all points j \(\in\) P-{i}: O(n)
        • Remove j from \(P_s\): O(n)
        • If di = diameter\((i,j,P_s)\) < d: O(n)
          • d = di; a=i; b=j
        • Add j to \(P_s\): O(n)
    • Return the dipolar MST formed by poles a and b. We can find which points to connect to which poles by following the same process as the diam subroutine.

    Runtime of \(O(n \left( n\log n + n \left( n\right) \right)) = O(n^3) \)

    Correctedness

    Correctedness is an immediate property of our arguments above. For all possible pair-of-points, we consider all potential radius-definiing points. By finding the minimum over all of these combinations we are guaranteed to solve our problem.

    WSPD Approximation

    For our approximation scheme we perform a process similar to the above. The difference is we use a WSPD to consider only a linear number of potential poles.

    WSPD and Diameter

    We assume the optimal spanning tree for our pointset is dipolar. We justify this assumption by noting that after this process is complete, we can use the \(O(n^2)\) algorithm given above to find the optimal unipolar tree and simply return the smaller of the two. This does not impact our overall runtime.

    Our strategy is to iterate over all pairs in the decomp. We'll choose a point randomly from each tuple as our two potential poles. We aim to demonstrate that this strategy results in a reasonable diameter tree in the worst case.

    Let our two optimal poles be denoted i and j. In our WSPD, there is exactly one pair A,B such that \(i\in A, j\in B\) or vice-versa. Let i' and j' be the points we randomly choose when iterating over the pair A,B.

    Approximation Bound

    Again we let \(P_i, P_j\) be the points connected to i and j resp. in the optimal tree. We examine the properties of a tree formed by connecting everything in \(P_i\) to i' instead (similarly for \(P_j\), j').

    We justify this strategy by noting that we're going to use our diameter sub-routine. This calculates the optimal diameter with i',j' poles. As such, any particular point-pole connection strategy we choose for analysis will never result in a better diameter than our system.

    If we set the radius of the i'-circle to be \(|i,i'| + L_r\) where \(L_r\) was the i-optimal radius we cover all points. This follows from the triangle inequality. For all points \(p\in P_i\), \(|i',p| \leq |i',i| + |i,p| \leq |i',i| + L_r\). We set the j'-radius similarly.

    It follows that our diameter is given by the following: \(\text{diam}(i',j')=\left(|i,i'| + L_r \right) + \left(|j,j'| + R_r \right) + |i',j'|\).

    We substitute in our WSPD bounds of \(|i,i'| \leq \frac{2}{s}|i,j|\) (resp. \(|j,j'| \leq \dots\) ) and \(|i',j'| \leq (1 + \frac{4}{s}) |i,j|\).