m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-11-26 17:06:03 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-11-26 17:06:03 +0100
commit6baa0cb5219290cbc9c77c71189b8aad1f69add1 (patch)
tree58396b2af5f122d1b0872cd88e4dd12067a02d14
parent0c4da4bc2cf21f895ad33dfbf624170c6a73e704 (diff)
Begin rewording LCA proof
-rw-r--r--mgr.tex44
1 files changed, 32 insertions, 12 deletions
diff --git a/mgr.tex b/mgr.tex
index b414db7..1bfba88 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -830,28 +830,48 @@ the minimal partition ready set containing $W$.
\subsection{Computing the LCA closure}\label{computing-closure}
-The LCA closure of a set of $m$ vertices $W$ can be computed in time $O(m \log
-m)$ after linear preprocessing of the tree $T$. In the preprocessing step, in
-addition to preprocessing for LCA queries, we will assign each vertex $v$ its
-in-order number, $\infixtable[v]$.
+\begin{lemma}
+ After linear preprocessing of a tree $T$, the LCA closure of a set of $m$
+ tree vertices $W \subseteq V(T)$ can be computed in time $O(m \log m)$, and
+ the size of the closure is linear in the size of $W$.
+\end{lemma}
+
+Proof: In the preprocessing step, we will preprocess the tree for LCA queries,
+and assign each vertex $v$ its in-order number, $\infixtable[v]$.
Now to compute the closure of $W$, we first sort the vertices in $W$ with
respect to their in-order numbers, so we end up with a list $v_1, \ldots, v_m$
of vertices such that $\infixtable[v_1] < \ldots < \infixtable[v_m]$.
-\begin{lemma}
- if $\infixtable[u] < \infixtable[v] < \infixtable[w]$, then $\mathlca(u, w)$
+\begin{observation}
+ If $\infixtable[u] < \infixtable[v] < \infixtable[w]$, then $\mathlca(u, w)$
is equal to either $\mathlca(u, v)$ or $\mathlca(v, w)$.
-\end{lemma}
+\end{observation}
This may be proved by a simple case analysis.
+\begin{observation}
+ Consider two tree vertices, $u, w \in V(T)$ with $\infixtable[u] <
+ \infixtable [w]$, and their least common ancestor
+ $v$. Then $\infixtable[u] \leq \infixtable[v] \leq \infixtable[w]$.
+\end{observation}
+
+Proof: If $v$ is equal to one of $u$ or $w$, the observation is obvious. For
+example, if $v = u$, we have that $\infixtable[u] = \infixtable[v] <
+\infixtable[w]$. If $v$ is a third vertex, then $u$ must be in its left subtree
+and $w$ must be in its right subtree. Thus an infix walk over $T$ will first
+visit $u$, then $v$, and then $w$.
+
Now, once $W$ has been sorted by in-order numbers, we can complete our
-computation in time $O(m)$. It is enough to walk through the list and issue LCA
-queries about successive pairs. By the lemma, the resulting set will indeed
-contain LCAs for each pair in the set. Note also that for each successive pair
-we will have added at most one new vertex to the closure, thus the size of the
-closure of $W$ is linear in $m$.
+computation in time $O(m)$. Consider the following set of vertices:
+
+\begin{equation*}
+ U := \{ v \;|\; v = LCA(v_i, v_{i+1}) \text{ for $1 \leq i \leq m - 1$} \}
+\end{equation*}
+
+$U$ is of size $O(m)$ and can be computed in time $O(m)$ by issuing LCA queries
+to successive pairs of the sorted $W$. We claim that $W' := W \cup U$ is the LCA
+closure of $W$.
\section{Computing root states of parts}