this is for holding javascript data
Xavier Holt edited CST_Monopolar_Algorithm_d_leftarrow__.md
almost 8 years ago
Commit id: 4afde95bd0994eb1832bc61d0bb3fdc4ed521f10
deletions | additions
diff --git a/CST_Monopolar_Algorithm_d_leftarrow__.md b/CST_Monopolar_Algorithm_d_leftarrow__.md
index 78539eb..73ac8f2 100644
--- a/CST_Monopolar_Algorithm_d_leftarrow__.md
+++ b/CST_Monopolar_Algorithm_d_leftarrow__.md
...
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 one circle, and the sum of the radii is minimum. We
define \(L_r:=\max_{p \in P_i} |ip|; R_r:=\max_{p \in P_j} |jp|\) 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\}\).
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, is evident -- we're seeking minimum distance so
we have we're not going to
try go further than the last-covered point. Similarly, if we haven't covered a
bit harder. It turns out point we
can get away with checking far fewer candidate radii. can't have a radius smaller than this edge.
To see this, assume one circle is fixed As such, we could simply iterate through all possible pairs and
denote it `L`. Let see which gets us the
points covered by `L` be denoted \(P_L\). We don't need best diameter. This takes us to \(O(n^4)\) however, so we have to
consider any point \(\in P_L\) as try a
potential radius. We don't cover any additional points by doing so. 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.
...
* 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)\) \(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: i \(\in P\): O(n)
* \(P_s \leftarrow\) `P-{i}` sorted in increasing distance WRT `i`: \(O(n \log n)\)
* For all points j \(\in\) `P-{i}`: O(n)
* Remove `j` from \(P_s\): O(n)
...
* 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.