From 6baa0cb5219290cbc9c77c71189b8aad1f69add1 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Fri, 26 Nov 2021 17:06:03 +0100
Subject: Begin rewording LCA proof

---
 mgr.tex | 44 ++++++++++++++++++++++++++++++++------------
 1 file changed, 32 insertions(+), 12 deletions(-)

(limited to 'mgr.tex')

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}
 
-- 
cgit v1.2.3