# Distinguished Representations of $\mathrm{GL}_{n}(\mathbb{F}_{q})$

Guy Kapon

(Date: October 2021)

###### Abstract.

Let $\mathrm{G}=\mathrm{Gl}_{n}(K)$, and $\mathrm{H}=\mathrm{G}^{\sigma}$ for
$\sigma$ an involution of the form $g\rightarrow aga^{-1}$, It is known that
for $K=\mathbb{Q}_{q}$ any irreducible representation of $\mathrm{G}$ with an
$\mathrm{H}$ invariant functional, is self dual, we prove an analogous result
for $\mathbb{F}_{q}$.

###### Contents

  1. 1 Introduction
    1. 1.1 Ideas of The Proofs
    2. 1.2 Structure of The Paper
    3. 1.3 Acknowledgments
  2. 2 Preliminaries
    1. 2.1 Notations
  3. 3 The Cuspidal Case
  4. 4 The General Case
    1. 4.1 The Geometric Lemma
    2. 4.2 A distinguished Restriction
    3. 4.3 PSH-algebras
    4. 4.4 Primary Representations
    5. 4.5 End of Proof

##  1\. Introduction

Relative representation theory is concerned with understanding representations
of the form $C^{\infty}(G/H)$ or some other suitably chosen space of
functions, In particular an interesting question is which irreducible
representations sit inside $C^{\infty}(G/H)$.

This representation will be the induction from $H$ to $G$ of the trivial
representation taken in the appropriate sense, and therefore we will have
$\mathrm{Hom}_{G}(\pi,C^{\infty}(G/H))=\mathrm{Hom}_{H}(\pi|_{H},1_{H})$. In
other words the number of times $\pi$ appears in $C^{\infty}(G/H)$ is the
dimension of $H$ invariant functionals, in the case where this is non-zero
$\pi$ is called $H$-distinguished.

An important family of $H$ are the ones that form symmetric pairs, If $G$ is
an algebraic group, and $\theta$ an involution, we denote $H=G^{\theta}$ the
fixed points of $\theta$, and we call the pair $(G,H)$ a symmetric pair (and
$G/H$ a symmetric space).

In [Pra15] Prasad made a conjecture, which was later generalized by Erez
Lapid, for a necessary condition for a representation to be distinguished in
the case of symmetric pairs.

######  Conjecture 1.0.1.

(Lapid-Prasad) Let $G$ be a connected reductive algebraic group defined over a
local non-archemidiean field $F$, $\theta:G\rightarrow G$ an involution
defined over $F$, $\mathrm{H}=G^{\theta}$. Let $\pi$ be a smooth irreducible
representation of $G(F)$. If $\pi$ is $\mathrm{H}-$distinguished then the
L-packet111We will not define L-packets as we do not need them here, for an
expository note see [Art01] of $\pi$ is invariant to the functor
$\tau\rightarrow\tilde{\tau}^{\theta}$, where $\tilde{\tau}$ is the
contragredient representation, and $\tau^{\theta}$ is the twist by $\theta$.

This is also conjectured for the archimedean case, we only need to take the
correct category of representations.

Several cases of this were proved:

  * •

For the pair
$(\mathrm{GL}_{a+b}(\mathbb{Q}_{p}),\mathrm{GL}_{a}(\mathbb{Q}_{p})\times\mathrm{GL}_{b}(\mathbb{Q}_{p}))$
this was proven in [JR96].

  * •

In [FLO12] the case where $G=\mathrm{GL}_{n}(E)$ for $E/F$ a quadratic
extension, and $\mathrm{H}$ is a subgroup of unitary transformations was
proved.

  * •

The case of real Galois symmetric pairs was proved in [Gla17]

Another natural setting where this conjecture can be stated is over finite
fields, In this paper, we will prove this conjecture for the Jaquet-Rallis
case over finite fields (of characteristic different than 2).

######  Main Theorem.

Let $q$ be an odd prime power, denote
$\mathrm{G}=\mathrm{GL}_{n}(\mathbb{F}_{q})$ and let
$A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ be a matrix such that $A^{2}=I$. Define
$\mathrm{H}=\\{X\in\mathrm{G}|AXA^{-1}=X\\}$. Assume we are given an
irreducible representation $\pi$ of $\mathrm{G}$ s.t $\pi^{\mathrm{H}}\neq 0$,
then $\pi^{*}\cong\pi$

###  1.1. Ideas of The Proofs

We start by using the result for $\mathbb{Q}_{q}$, from an irreducible
cuspidal representation of $\mathrm{GL}_{n}(\mathbb{F}_{q})$ we can get an
irreducible cuspidal of $\mathrm{GL}_{n}(\mathbb{Q}_{p})$, if we started with
a distinguished one we will end up with a distinguished one, which is,
therefore, self-dual, and since the process is injective the original
representation is also self-dual.

The next step is to try and see what happens during parabolic induction, using
Mackey theory and some standard manipulations we get that if a parabolic
induction is distinguished then some Jacques restriction of it is also
distinguished (with respect to a different involution).

We then use the theory of Zelevinsky to break the induction process to two
steps, irreducibles that lie in the parabolic induction of a parabolic $\rho$
with itself $n$ times are called $\rho$-primary, and any representation is the
parabolic induction of primary representations over different cuspidals.

We then prove the case of primary representations, and then using it we
complete the proof for general representations.

###  1.2. Structure of The Paper

In §2 we review the notions we will use for $\mathrm{Gl}_{n}$, and it’s
subgroups, this will mostly be used in §4.

In §3 we prove the case of cuspidal representations using [JR96].

In §4 we prove the general case, starting by doing the ”induction step”, then
reviewing the Zelevinsky PSH-algebra theory, and then using it to complete the
proof.

###  1.3. Acknowledgments

I would like to thank Avraham Aizenbud, for suggesting this problem, helping
us along the way, and teaching me mathematics.

I was partially supported by ISF 249/17 and BSF 2018201 grants.

##  2\. Preliminaries

###  2.1. Notations

Throughout the paper we fix an odd prime power $q$, In this section, we mainly
explain the notions we use for subgroups and operations on
$\mathrm{GL}_{n}(\mathbb{F}_{q})$, when there is no confusion we will use
$G_{n}$ for $\mathrm{GL}_{n}(\mathbb{F}_{q})$.

######  Notion 2.1.1.

We use $[n]$ for the set $\\{0,1,...,n-1\\}$, when working with $\rm{Gl}_{n}$
we consider those as the indexes of the matrix.

######  Definition 2.1.2.

For an ordered partition of $[n]$ with sets $T=\\{T_{0},T_{1},\cdots
T_{m-1}\\}$ we denote by $P(T),U(T),L(T)$ the corresponding standard
parabolic, its unipotent subgroup, and it’s levy quotient (which we consider
inside $G_{n}$). We denote by $f_{T}:[n]\rightarrow[m]$ the function that
sends $T_{i}$ to $i$.

When there is no confusion we drop the $T$ from the notation.

The groups can be written directly:

$P(T)=\\{A\in G_{n}|\forall_{i,j}:f_{T}(i)>f_{T}(j)\Rightarrow A_{i,j}=0\\}$
$U(T)=\\{I+A\in G_{n}|\forall_{i,j}:f_{T}(i)\geq f_{T}(j)\Rightarrow
A_{i,j}=0\\}$ $L(T)=\\{A\in G_{n}|\forall_{i,j}:f_{T}(i)\neq
f_{T}(j)\Rightarrow A_{i,j}=0\\}$

We abuse notation and denote by $T_{i}$ also the space generated by the
coordinates of $T_{i}$.

######  Notion 2.1.3.

For $i\in[m]$ we denote $n_{i}=|T_{i}|$, we denote by
$L_{i}=\mathrm{GL}_{n_{i}}(\mathbb{F}_{q})$ where we think of it as the i’th
factor in the levy group.

Throughout the paper we will usually have some involution $\sigma$ fixed, our
involutions are always conjugation maps, so we define:

######  Definition 2.1.4.

for $A\in G_{n}$, $\sigma_{A}:G_{n}\rightarrow G_{n}$ is the conjugation by
$A$, $\sigma_{A}(X)=A\cdot X\cdot A^{-1}$. $H_{A}$ is the subgroup fixed by
$\sigma_{A}$, i.e the centraliser of $A$.

We will have most of the time that $A$ normalizes the standard torus, in that
case, $A$ is a permutation of the indices up to an element of the torus, and
we denote that permutation $\tau_{A}$.

From a representation of $L$ we can construct a representation of $G_{n}$ by
parabolic induction. Since $L$ is a product of groups we consider the
parabolic induction as a multiplication of representations and denote it in a
way that reflects this.

######  Definition 2.1.5.

If $\pi_{i}\in rep(L_{i})=rep(G_{n_{i}})$ are representations, we denote
$x=\boxtimes_{i\in[m]}\pi_{i}$ is the outer tensor product of them, which is a
representation of $L$. We then consider it as representation of $P$ using the
canonical map $P\rightarrow L$. With this notions we define:

$\prod_{i\in[m]}\pi_{i}=Ind_{P}^{G_{n}}x$

In the other direction, we have the Jacquet functor.

######  Definition 2.1.6.

Let $\pi$ be a representation of $G_{n}$, we denote by $\mathcal{J}_{T}(\pi)$
the Jacquet restriction, which is defined by restricting to $P$ and then
taking $U$ co-invariants, this is a representation of $L$.

##  3\. The Cuspidal Case

For our base case we use the result for $\mathbb{Q}_{q}$:

######  Theorem 3.0.1 ([JR96, Theroem 1.1]).

Let $G_{n}=\mathrm{GL}_{n}(K)$ where $K$ is a local non-Archimedean field of
characteristic 0. let p,q be positive integers with $p+q=n$ and let $H_{p,n}$
be the subgroup of $G_{n}$ which is $G_{p}\times G_{q}$. if $\pi$ is an
admissible irreducible representation of $G_{n}$, then:

$\mathrm{dim}(\left<{\pi|_{H_{p,q}}},{1_{H_{p,q}}}\right>)\leq 1$

And if there is equality then $\pi$ is isomorphic to its contragredient
representation.

For us only the case of equality is relevant

The second thing we use is:

######  Lemma 3.0.2.

There is an injective map between irreducible cuspidal representations of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$ and irreducible cuspidal representations of
$\mathrm{GL}_{n}(\mathbb{Q}_{q})$.

This map takes a representation of $\mathrm{GL}_{n}(\mathbb{F}_{q})$,
considers it as a representation of $\mathrm{GL}_{n}(\mathbb{Z}_{q})$, extends
it trivially on the center of $\mathrm{GL}_{n}(\mathbb{Q}_{q})$ and then
inducts it to the whole group. This lemma is part of the theory around Moy-
Prassad filtration and follows from [Fin19, Proposition 6.6], for completeness
we give proof for the irreducibility and the injectivity (the cuspidality is
unimportant for us).

###### Proof.

Let $\pi$ be a cuspidal irreducible representation of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$, let $\tilde{\pi}$ be it’s extension to
$K=\mathrm{GL}_{n}(\mathbb{Z}_{q})\cdot
Z(\mathrm{GL}_{n}(\mathbb{Q}_{q}))\cong\mathrm{GL}_{n}(\mathbb{Z}_{q})\times\mathbb{Z}$
where $\mathbb{Z}$ acts trivially, and let $x=Ind_{K}^{G}\tilde{\pi}$ be the
induction to $G=\mathrm{GL}_{n}(\mathbb{Q}_{q})$. Let
$\pi^{\prime},\tilde{\pi^{\prime}},x^{\prime}$ be the same for another
irreducible cuspidal representation $\pi^{\prime}$, let us calculate:

$\left<{x},{x^{\prime}}\right>$

Using mackeys theory we have:

$\left<{x},{x^{\prime}}\right>=\left<{\tilde{\pi}},{x^{\prime}|_{K}}\right>=\sum_{g\in
K\backslash G/K}\left<{\tilde{\pi}},{Ind_{K\cap
K^{g}}^{K}\tilde{\pi^{\prime}}^{g}|_{K\cap K^{g}}}\right>=$ $=\sum_{g\in
K\backslash G/K}\left<{\tilde{\pi}|_{K\cap
K^{g}}},{\tilde{\pi^{\prime}}^{g}|_{K\cap K^{g}}}\right>$

Now by definition we know that matrices in $K_{1}=I+pM_{n}(\mathbb{Z}_{q})$
act trivially on $\tilde{\pi}$, and so if there is a map from
$\tilde{\pi}|_{K\cap K^{g}}$ it must land on the $K_{1}\cap K^{g}$ invariants.
translating to our case we see it must land on the $K\cap K_{1}^{g}$
invariants of $\tilde{\pi^{\prime}}$, which is the same as the $(K\cap
K_{1}^{g})/K_{1}$ invariants of $\pi^{\prime}$.

Now it is well known that $(K\cap K^{g})/K_{1}$ is a parabolic subgroup, and
$(K\cap K_{1}^{g})/K_{1}$ is it’s unipotent subgroup, and since $\pi^{\prime}$
is cuspidal, unless this is the trivial parabolic and unipotent subgroup,
there are no invariant, in other words $\left<{\tilde{\pi}|_{K\cap
K^{g}}},{\tilde{\pi^{\prime}}^{g}|_{K\cap K^{g}}}\right>=0$ unless $K^{g}=K$,
but since the normalizer of $\mathrm{GL}_{n}(\mathbb{Z}_{q})$ is $K$ we see
that this only happens when $g\in K$.

In conclusion we see that:

$\left<{x},{x^{\prime}}\right>=\left<{\tilde{\pi}},{\tilde{\pi^{\prime}}}\right>=\left<{\pi},{\pi^{\prime}}\right>$

In particular if $\pi,\pi^{\prime}$ are different then so is $x,x^{\prime}$,
and since $\pi$ is irreducible then $\left<{x},{x}\right>=1$ and therefore $x$
is irreducible. ∎

######  Remark 3.0.3.

Proving that $x$ is cuspidal can be done very similarly, as it amounts to
calculating $\left<{1_{U}},{x|_{U}}\right>$ which again can be done by Mackey
theory.

Now we are ready to prove:

######  Theorem 3.0.4.

Let $\pi$ be a cuspidal irreducible representation of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$, $A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ such
that $\sigma_{A}$ is an involution of $\mathrm{GL}_{n}(\mathbb{F}_{q})$, and
assume that $\pi$ is $H_{A}$ distinguished, then $\pi$ is self dual.

###### Proof.

Let $\tilde{A}$ be a lift of $A$ to $\mathrm{GL}_{n}(\mathbb{Z}_{q})$, and
$H_{\tilde{A}}$ be the invarinats of $\sigma_{\tilde{A}}$ in
$\mathrm{GL}_{n}(\mathbb{Q}_{q})$. let us show that $x$ (from the lemma) is
$H_{\tilde{A}}$ distinguished.

$\left<{x|_{H_{\tilde{A}}}},{1_{H_{\tilde{A}}}}\right>\geq\left<{ind_{H_{\tilde{A}}\cap
K}^{H_{\tilde{A}}}(\tilde{\pi}|_{H_{\tilde{A}}\cap
K})},{1_{H_{\tilde{A}}}}\right>=\left<{\tilde{\pi}|_{H_{\tilde{A}}\cap
K}},{1_{H_{\tilde{A}}\cap K}}\right>$

Where the inequality is by Mackey’s theory.

Now $K_{1}$ acts trivially on $\tilde{\pi}$, so we can consider this as
representations mod $K_{1}$, and $(H_{\tilde{A}}\cap K)/K_{1}\subseteq H_{A}$,
so the existence of such a map is followed from the fact that $\pi$ is $H_{A}$
distinguished.

Now since $x$ is distinguished we know by 3.0.1 that it is self-dual
(admissibility of $x$ is obvious). However both the induction and trivial
extension commute with duality, and since we proved that on irreducible
cuspidal representations this operation is injective, this must mean
$\pi\cong\pi^{*}$ as wanted. ∎

##  4\. The General Case

Now that we know the result for cuspidal representations, our goal is to
extend from cuspidal to general irreducible representations.

We start by showing in 4.2 that if a parabolic induction is distinguished,
then there is some Jacques restriction which is also distinguished (with
respect to a different involution).

In 4.4 we use the restriction to show that if a primary representation is
distinguished, then the cuspidal representation below it is self-dual, we then
use the theory in [Zel06] to show that this implies that the primary
representation is self-dual.

Finally, in 4.5 we again use the restriction to now complete the general case.

###  4.1. The Geometric Lemma

Before we start we need some results about $\mathrm{H}$, and how $P$ acts on
$G_{n}/H$. these results come from [HW93].

######  Lemma 4.1.1.

Let $G$ be a connected reductive algebraic group over $k$,$\theta$ an
involution of $G$ defined over $k$, $H=G^{\theta}$ the fixed points of
$\theta$, and $P$ a minimal parabolic over $k$. Then $P$ contains a $\theta$
stable maximal $k$ split torus $A$, and every double coset $H(k)gP(k)$
contains an element $x$ such that $x\cdot\theta(x)^{-1}\in N(A(k))$.

The $\theta$-stable torus part is lemma 2.4 of [HW93], while the rest follows
from chapter 6 (specifically 6.6).

######  Remark 4.1.2.

Notice that if $P$ is any parabolic that contains a minimal $k$ parabolic then
the lemma is still true.

###  4.2. A distinguished Restriction

In this section, our goal is to develop the tool that will let us prove the
theorem for big representations using smaller ones which we already know the
result for.

We fix some $n$ and an involution $\sigma=\sigma_{A}$ of $G_{n}$. We assume
$A$ normalizes the standard torus (This is fine since $A$ is diagonizbele)

The exact statement we prove in this section is as follows:

######  Lemma 4.2.1.

Let $T=\\{T_{i}\\}_{i\in[m]}$ be an ordered partition of $[n]$, let
$\pi_{i}\in rep(L(T)_{i})$ be representations. Assume that
$\pi=\prod_{i\in[m]}\pi_{i}$ is $H$ distinguished, then there exist some
$A^{\prime}$ that normalizes the torus,and partitions $T_{a,b}=\\{i\in
T_{a}|f(\tau_{A^{\prime}}(i))=b\\}$ of $T_{a}$, such that:

$\boxtimes_{a}\mathcal{J}_{T_{a,b}}(\pi_{a}) $

as a representation of $L(T_{a,b})$ is distinguished with respect to
$\sigma_{A^{\prime}}$.

######  Remark 4.2.2.

Notice that this is a representation of the levy of $T_{a,b}$, which is a
product of groups, and $\sigma_{A^{\prime}}$ indeed act on it so the statement
makes sense. While it does not act on every block separately, one can see that
since $\sigma_{A^{\prime}}$ is an involution it does act on pairs of blocks.

We start by using Mackey theorem to get:

######  Claim 4.2.3.

There is some $PgH\in P\backslash G/H$ such that
$x=\boxtimes_{a\in[m]}\pi_{a}$ is distinguished with respect to $H^{g}\cap P$.

###### Proof.

$\pi$ is $\mathrm{H}$ distinguished which means:

$\left<{\pi|_{\mathrm{H}}},{{1}_{\mathrm{H}}}\right>>\neq 0$

Now by definition $\pi=Ind_{P}^{G}(x)$, by mackey theory we get:

$\pi|_{\mathrm{H}}=Ind_{P}^{G}(x)|_{\mathrm{H}}=\bigoplus_{g\in P\backslash
G/H}Ind_{H\cap P^{g}}^{H}(x^{g}|_{H\cap P^{g}})$

Therefore:

$\left<{\pi|_{\mathrm{H}}},{{1}_{\mathrm{H}}}\right>=\sum_{g\in P\backslash
G/H}\left<{Ind_{H\cap P^{g}}^{H}(x^{g}|_{H\cap
P^{g}})},{{1}_{\mathrm{H}}}\right>=$ $=\sum_{g\in P\backslash
G/H}\left<{x^{g}|_{H\cap P^{g}}},{{1}_{\mathrm{H\cap
P^{g}}}}\right>=\sum_{g\in P\backslash G/H}\left<{x|_{H^{g}\cap
P}},{{1}_{\mathrm{H^{g}\cap P}}}\right>$

And since the LHS is positive, then so is the RHS, so one of those terms is
non-zero, which is exactly what we wished to prove. ∎

Now by 4.1.1 we know that any $g\in P\backslash G/H$ can be chosen such that
$g^{-1}\sigma(g)=Q(g)$ is in $N(A)$. Now $a\in H^{g}$ if and only if:

$gag^{-1}=\sigma(gag^{-1})$

which is the same as saying:

$a=Q(g)\sigma(a)Q(g)^{-1}$

which means those are exactly matrices in $P$ which are invariant under this
new involution, notice that $Q(g)$ normalizes the torus, so it is a
permutation up to an element of the torus. so now we know that $x$ is
distinguished by matrices that are preserved by this involution, call the
invariant vector $v$,and call the corresponding premutiaion $\tau$, for
$a,b\in[m]$ denote by $T_{a,b}$ all $i\in[n]$ such that $f(i)=a,f(\tau(i))=b$.

######  Claim 4.2.4.

Let $a,b,c\in[m]$ and assume $a<b$. Let $A$ be a matrix s.t $A_{i,j}=0$ unless
$f(i)=f(j)=c$ and $f(\tau(i))=a,f(\tau(j))=b$. then $(I+A)v=v$.

###### Proof.

consider $\sigma^{g}(A)$, it is only non-zero on $(i,j)$ s.t $f(i)=a<b=f(j)$
and therefore $1+\sigma^{g}(A)$ is in $U$, which acts trivially on all of $x$.
Furthermore I claim that $\sigma^{g}(A)$ and $A$ commute, for this consider
$T_{a,b}$ as a vector space spanned by those coordinates, $A$ is a map from
$T_{c,a}$ to $T_{c,b}$ while $\sigma^{g}(A)$ is a map from $T_{a,c}$ to
$T_{b,c}$, since we can’t have that $T_{b,c}=T_{c,a}$ or $T_{c,b}=T_{a,c}$
then the composition of $A$ and $\sigma^{g}(A)$ is zero either way.

Now denote $B=1+A$, we see that
$B\sigma^{g}(B)=\sigma^{g}(B)B=\sigma^{g}(B\sigma^{g}(B))$ and therefore
$B\sigma^{g}(B)v=v$ but $\sigma^{g}(B)v=v$ so we get $Bv=v$ ∎

######  Corollary 4.2.5.

If $A$ is a matrix s.t $A_{i,j}=0$ unless $f(i)=f(j)$ and
$f(\tau(i))<f(\tau(j))$ then $(1+A)v=v$.

###### Proof.

This group is obviously generated by the matrices of the previous claim. ∎

Now consider the levy group $L^{\prime}$ corresponding to the $T_{a,b}$,
obviously $L^{\prime}\subseteq L$, and the unipotent factor is exactly the
matrices of the corollary, so we conclude that the Jacques restriction from
$L$ to $L^{\prime}$ of $x$ is distinguished with respect to $\sigma^{g}$.

###  4.3. PSH-algebras

To complete the proof we need to review the way in which general represntaions
are built up from cuspidal ones, for that we review the description in
[Zel06].

######  Definition 4.3.1.

A Hopf algebra over a comutative ring $K$ is a graded $K$ module
$R=\bigoplus_{n\geq 0}R_{n}$ with graded morphisms (over $K$)
$m:R\otimes_{K}R\rightarrow R$, $m^{*}:R\rightarrow R\otimes_{K}R$,
$e:K\rightarrow R$, $e^{*}:R\rightarrow K$ s.t $m,e$ turn $R$ to a ring,
$m^{*},e^{*}$ turns it into a co-algebra, and $m^{*}$ is a ring map.

In other words, a Hopf algebra is something that is both an algebra and a co-
algebra, and both structures commute.

######  Definition 4.3.2.

A PSH-algebra is a Hopf algebra over $\mathbb{Z}$ together with a free
homogeneous basis for $R$ (as an abelian group), s.t $R_{0}\cong\mathbb{Z}$
with isomorphisms $e,e^{*}$, all the maps of the Hopf algebra take basis
elements to a positive-sum of basis elements, and with respect to the inner
product in which our basis is an orthonormal basis, $m,m^{*}$ and $e,e^{*}$
are adjoint pairs.

One should think of examples of the form $R_{n}=R(G_{n})$ where $R(G)$ is the
ring of virtual representations, the free basis is just irreducible
representations, the multiplication and co-multiplication will be a form of
induction and restriction, the positivity will correspond to the fact that
those operations take actual representations to actual representations, the
adjointness will correspond to the adjointness (as functors) of induction and
restriction, and the most non-trivial part will be the fact that
multiplication and co-multiplication commute, which will follow from Mackey’s
theory.

######  Claim 4.3.3.

If we denote $G_{n}=S_{n}$ or $G_{n}=\mathrm{GL}_{n}(\mathbb{F}_{q})$ for all
$n$, then $R=\bigoplus_{n\geq 0}R(G_{n})$ is a PSH-algebra. In the case of
$S_{n}$ the multipication and co-multipication comes from the natural
inclusion $S_{n}\times S_{m}\subseteq S_{n+m}$ and the usual induction and
restriction. In the case of $\mathrm{GL}_{n}(\mathbb{F}_{q})$ it is the same
but with parabolic induction and Jacques restriction.

It turns out that PSH-algebras have a very simple structure theorem.

######  Definition 4.3.4.

A basis element of a PSH-algebra is called irreducible, an element $x$ s.t
$m^{*}(x)=x\otimes 1+1\otimes x$ is called primitive.

In the example of $\mathrm{GL}_{n}(\mathbb{F}_{q})$ we see that the basis
elements are exactly irreducible representations, and it’s easy to see that
the definition of primitive is the same as the usual definition of a cuspidal
representation.

######  Theorem 4.3.5.

Let R be a PSH-algebra, denote $\mathscr{C}$ as the set of irreducible
primitive elements, then $R\cong\bigotimes_{\rho\in\mathscr{C}}R(\rho)$ where
$R(\rho)$ is a PSH-algebra with only one irreducible primitive element (and is
in fact the PSH-algebra generated by $\rho$).

In the theorem one has to be careful, as there is an infinite tensor product,
we mean by it the colimit over finite tensors, where maps are induced by the
product with the unit.

The algebra generated by $\rho$ is easily described, for each $\rho^{n}$ we
write it as a sum of basis elements, and then take the space generated by
those basis elements.

This theorem in particular says that:

######  Claim 4.3.6.

For a PSH-algebra, we call an element $\rho$-primary if it is in $R(\rho)$,
then every irreducible element can be uniquely written as a product of primary
irreducible elements over different $\rho$.

If we apply this to the PSH-algebra of $\mathrm{GL}_{n}(\mathbb{F}_{q})$ we
get the same statement for representations of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$, where the product is parabolic induction,
and the $\rho$ are irreducible cuspidal representations.

The theorem is complemented by:

######  Theorem 4.3.7.

All PSH-algebra with one irreducible primitive element of degree $1$ are
isomorphic, the isomorphism is not unique, but there are only two
isomorphisms.

First, notice that the restriction on the degree is not essential, we saw that
$R(\rho)$ only has elements of degree $n\cdot deg(\rho)$, so we can just
divide all the degrees by $deg(\rho)$. Also notice that for $S_{n}$ there are
no irreducible primitive elements except the trivial representation of
$S_{1}$, so this gives an example of this unique algebra.

We can also describe the only automorphism:

######  Claim 4.3.8.

If $R$ has only one primitive irreducible element $\rho$, then
$\rho^{2}=x_{2}+y_{2}$ where $x_{2},y_{2}$ are irreducible, the unique non
trivial automorphism of $R$ swaps $x_{2},y_{2}$, In particular an isomorphism
of this algebra is defined by what it does to $y_{2}$.

For example, one can see that for $S_{n}$ tensoring with the sign
representation is an automorphism, and it indeed swaps $x_{2},y_{2}$ which in
this case are exactly the trivial and sign representations of $S_{2}$.

Another example of an automorphism comes from duality, for $S_{n}$ this is of
course the identity automorphism. For $\mathrm{GL}_{n}(\mathbb{F}_{q})$ this
is not the case, we get a map ${}^{*}:R(\rho)\rightarrow R(\rho^{*})$, and not
every cuspidal is self-dual, however, we do claim:

######  Claim 4.3.9.

If $\rho$ is self dual, then ${}^{*}:R(\rho)\rightarrow R(\rho^{*})=R(\rho)$
is the identity.

###### Proof.

By what we said before it’s enough to see what we do on the irreducible
representations inside $\rho^{2}$, The idea is that we can distinguish between
the two irreducible inside using a Whitaker character, specifically let
$\chi:\mathbb{F}_{q}\rightarrow\mathbb{C}^{*}$ be the non-trivial real
character and extend it to $U$ by $\chi(A)=\sum_{1\leq i<n}\chi(a_{i,i+1})$,
for any representation we can look at the dimension of the $\chi$ equivariant
vectors in it, it is known that for $\rho^{n}$ there is only one, in
particular, this means exactly one of the two irreducibles in $\rho^{2}$ has
such a vector, we call that one $y_{2}$. now notice that $y_{2}^{*}$ has a
$\chi^{*}$ equivariant functional, but $\chi^{*}=\chi$ since it’s real, and
since we are working with finite groups having an equivariant functional or
vector is the same (both correspond to a map from or to the representation
$\chi$). So $y_{2}^{*}$ has a $\chi$ equivariant vector and is, therefore,
$y_{2}$, so we are done. ∎

######  Remark 4.3.10.

The fact that duality is an isomorphism of the PSH-algebra is not immediate,
one needs to show that it commutes with the multiplication and co-
multiplication, for the usual induction and restriction this is obvious, for
parabolic induction this is also easy, for Jacques restriction however this is
more delicate. indeed for $\pi\in rep(\mathrm{GL}_{n}(\mathbb{F}))$ we need to
take the dual of $(\pi|_{P})^{U}$, which is $((\pi^{*})|_{P})_{U}$ as for
finite-dimensional spaces duality takes invariants to co-invariants and vice-
versa, however since we work over $\mathbb{C}$ and with finite groups, we have
the averaging operator which identifies invariants with co-invariants.

Finally, the last claim can be restated as:

######  Corollary 4.3.11.

A $\rho$-primary representation is self-dual iff $\rho$ is.

###### Proof.

If $\pi\in R(\rho)$ is self dual, then $\pi=\pi^{*}\in R(\rho^{*})$ so we must
have $\rho=\rho^{*}$. On the other hand if $\rho=\rho^{*}$ then 4.3.9 says
that ∗ is identity on $R(\rho)$ so we are done. ∎

###  4.4. Primary Representations

The goal of the section is to prove the primary case:

######  Theorem 4.4.1.

If $\pi$ is a $\rho$-primary representation, and $\pi$ is $\mathrm{H}$
distinguished, then $\pi$ is self-dual.

Because of 4.3.11 we only have to prove that $\rho$ is self-dual, and since
any primary representation is a sub-representation of $\rho^{n}$ for some $n$
it’s enough to prove:

######  Theorem 4.4.2.

If $\rho^{n}$ is $H$ distinguished then $\rho$ is self dual.

###### Proof.

We apply 4.2.1 on the product $\rho^{n}$, we get that there is a torus
normalising matrix $Q$, it’s permutation of the indexes is $\tau$, and we
consider the levi that corresponds to the spaces
$T_{a,b}=\\{i|f(i)=a,f(\tau(b)\\}$. The Jacques restriction to it is
distinguished with respect to the $Q$-centraliser, however $\rho$ is cuspidal,
and all it’s non-trivial restrictions are zero, we see that $T_{a,b}$ is
either empty or all of $T_{a}$. since $\tau$ is an involution this means that
$[m]$ is split to pairs and singletons, where in the singletons
$T_{a,a}\neq\phi$ and in the pairs $T_{a,b}\neq\phi\neq T_{b,a}$. so now we
have two cases.

Case 1: we have $T_{a,a}\neq\phi$. In this case the $\rho$ siting in $T_{a}$
is distinguished by the restriction of $\sigma^{Q}$ to $T_{a}$, but since it
is cuspidal, we can use 3.0.4 and therefore $\rho$ is self dual.

Case 2: We have $T_{a,b}\neq\phi\neq T_{b,a}$, in this case we have
$\sigma^{Q}$ takes $L_{a}$ to $L_{b}$ and vice versa. If we write this map as
$\sigma^{\prime}:\mathrm{GL}_{r}(\mathbb{F}_{q})\rightarrow\mathrm{GL}_{r}(\mathbb{F}_{q})$,
then the invariant matrix are exactly $(A,\sigma^{\prime}(A))$. restricting
$\rho\boxtimes\rho$ we get $\rho\otimes\sigma^{\prime}(\rho)$ where here this
is the tensor in $rep(\mathrm{GL}_{n}(\mathbb{F}_{q}))$. but since
$\sigma^{\prime}$ is essentially the restriction of a conjugation we can see
that it is a conjugation map, and conjugation doesn’t change representations,
so we get that $\rho\otimes\rho$ is $\mathrm{GL}_{n}(\mathbb{F}_{q})$
distinguished. Therefore we can write
$0\neq(\rho\otimes\rho)^{\mathrm{GL}_{n}(\mathbb{F}_{q})}=(\mathrm{Hom}(\rho,\rho^{*}))^{\mathrm{GL}_{n}(\mathbb{F}_{q})}$,
which means we have a non-zero equivariant map from $\rho$ to $\rho^{*}$, but
since they are irreducible this means they are isomorphic, as wanted. ∎

###  4.5. End of Proof

Now we are only left with proving:

######  Theorem 4.5.1.

If $\pi$ is a product of $\rho_{i}$-primary representation $\pi_{\rho_{i}}$,
and $\pi$ is $\mathrm{H}$ distinguished, then $\pi$ is self dual.

The proof is done in a very similar way to the previous case.

###### Proof.

Again we apply 4.2.1 on the product, so we have a matrix $Q$, a permutation
$\tau$ and the partition $T_{a,b}$ as before.

For each $a$, if $T_{a,a}$ is non-empty, then we have some Jacques restriction
of $\pi_{\rho_{a}}$ which is distinguished, since a restriction of a
$\rho_{a}$ primary representation is still primary, this means that $\rho_{a}$
is self dual. On the other hand if $T_{a,b}$ is not empty (and in particular
$T_{b,a}$ is also non-empty) then we get that the product of a Jacques
restriction of $\pi_{\rho_{a}}$ and of $\pi_{\rho_{b}}$ is distinguished. just
like in the previous case this means that these restrictions are dual to each
other, and therefore $\rho_{a}$ is dual to $\rho_{b}$.

Combining these two results we see that we cannot have $T_{a,b},T_{a,c}$ both
non-empty for $b\neq c$, as then $\rho_{b}=\rho_{a}^{*}=\rho_{c}$, So we see
that again the indexes are divided to singletons and pairs.

The $\rho_{a}$ such that $T_{a,a}$ is non empty are self dual and therefore
also $\pi_{\rho_{a}}$ is self dual. If $T_{a,b}$ is non empty, then since the
restrictions don’t do anything, we get $\pi_{\rho_{a}}^{*}=\pi_{\rho_{b}}$.

And since duality commutes with the product, we get that $\pi$ is self-dual. ∎

## References

  * [HW93] Aloysius G Helminck and Shu Ping Wang  “On rationality properties of involutions of reductive groups”  In _Adv. Math_ 99.1 Citeseer, 1993, pp. 26–96
  * [JR96] Hervé Jacquet and Stephen Rallis  “Uniqueness of linear periods”  In _Compositio Mathematica_ 102.1 Kluwer Academic Publishers, 1996, pp. 65–123
  * [MP96] Allen Moy and Gopal Prasad  “Jacquet functors and unrefined minimal K-types”  In _Commentarii Mathematici Helvetici_ 71.1, 1996, pp. 98–121
  * [Art01] James Arthur  “A Note on L-packets”  In _Pure and Applied Mathematics Quarterly Volume_ 2, 2001
  * [Zel06] Andrey V Zelevinsky  “Representations of finite classical groups: a Hopf algebra approach”  Springer, 2006
  * [FLO12] Brooke Feigon, Erez Lapid and Omer Offen  “On representations distinguished by unitary groups”  In _Publications mathématiques de l’IHÉS_ 115, 2012, pp. 185–323
  * [Pra15] Dipendra Prasad  “A ‘relative’ local Langlands correspondence”, 2015
  * [AA16] Avraham Aizenbud and Nir Avni  “Bounds on multiplicities of spherical spaces over finite fields”, 2016
  * [Gla17] Itay Glazer  “Representations of reductive groups distinguished by symmetric subgroups”  In _Mathematische Zeitschrift_ 289.1-2 Springer ScienceBusiness Media LLC, 2017, pp. 471–489
  * [Fin19] Jessica Fintzen  “On the Moy-Prasad filtration”, 2019


11institutetext: Department of Software Engineering, Shamoon College of
Engineering, Israel
11email<EMAIL_ADDRESS>22institutetext: Department of Computer Science,
Indian Institute of Technology Bombay, India 22email<EMAIL_ADDRESS>33institutetext: Computer Science Department, Ben-Gurion University, Israel
33email<EMAIL_ADDRESS>
# Dynamic Euclidean Bottleneck Matching

A. Karim Abu-Affash 11 Sujoy Bhore 22 Paz Carmi 33

###### Abstract

A fundamental question in computational geometry is for a set of input points
in the Euclidean space, that is subject to discrete changes
(insertion/deletion of points at each time step), whether it is possible to
maintain an approximate bottleneck matching in sublinear update time. In this
work, we answer this question in the affirmative for points on a real line and
for points in the plane with a bounded geometric spread.

For a set $P$ of $n$ points on a line, we show that there exists a dynamic
algorithm that maintains a bottleneck matching of $P$ and supports insertion
and deletion in $O(\log n)$ time. Moreover, we show that a modified version of
this algorithm maintains a minimum-weight matching with $O(\log n)$ update
(insertion and deletion) time. Next, for a set $P$ of $n$ points in the plane,
we show that a ($6\sqrt{2}$)-factor approximate bottleneck matching of
$P_{k}$, at each time step $k$, can be maintained in $O(\log{\Delta})$
amortized time per insertion and $O(\log{\Delta}+|P_{k}|)$ amortized time per
deletion, where $\Delta$ is the geometric spread of $P$.

###### Keywords:

Bottleneck matching Minimum-weight matching Dynamic matching.

##  1 Introduction

Let $P$ be a set of $n$ points in the plane. Let $G=(P,E)$ denote the complete
graph over $P$, which is an undirected weighted graph with $P$ as the set of
vertices and the weight of every edge $(p,q)\in E$ is the Euclidean distance
$|pq|$ between $p$ and $q$. For a perfect matching $M$ in $G$, let $bn(M)$ be
the length of the longest edge. A perfect matching $M^{*}$ is called a
bottleneck matching of $P$, if for any other perfect matching $M$, $bn(M)\geq
bn(M^{*})$.

Computing Euclidean bottleneck matching was studied by Chang et al. [13]. They
proved that such kind of matching is a subset of $17$-RNG (relative
neighborhood graph) and presented an $O(n^{3/2}\log^{1/2}n)$-time algorithm to
compute a bottleneck matching. In fact, a major caveat of the Euclidean
bottleneck matching algorithms was that they relied on Gabow and Tarjan [17]
as an initial step (as also noted by Katz and Sharir [21]). In recent work,
Katz and Sharir [21] showed that the Euclidean bottleneck matching for a set
of $n$ points in the plane can be computed in $O(n^{\omega/2}\log n)$
deterministic time, where $\omega\approx 2.37$ is the exponent of matrix
multiplication. For general graphs of $n$ vertices and $m$ edges, Gabow and
Tarjan [17] gave an algorithm for maximum bottleneck matching that runs in
$O(n^{5/2}\sqrt{\log n})$ time. Bottleneck matchings were also studied for
points in higher dimensions and in other metric spaces [16], with non-crossing
constraints [4, 3], and on multichromatic instances [2].

In many applications, the input instance changes over a period of time, and
the typical objective is to build dynamic data structures that can update
solutions efficiently rather than computing everything from scratch. In recent
years, several dynamic algorithms were designed for geometric optimization
problems; see [5, 10, 9, 11, 12]. Motivated by this, we study the bottleneck
matching for dynamic point set in the Euclidean plane. In our setting, the
input is a set of points in the Euclidean plane and the goal is to devise a
dynamic algorithm that maintains a bottleneck matching of the points and
supports dynamic changing of the input due to insertions and deletions of
points. Upon a modification to the input, the dynamic algorithm should
efficiently update the bottleneck matching of the new set.

###  1.1 Related Work

Euclidean matchings have been a major subject of investigation for several
decades due to their wide range of applications in operations research,
pattern recognition, statistics, robotics, and VLSI; see [14, 23]. The
Euclidean minimum-weight matching, where the objective is to compute a perfect
matching with the minimum total weight, was studied by Vaidya [29] who gave
the first sub-cubic algorithm ($O(n^{5/2}\log^{4}n)$) by exploiting geometric
structures. Varadrajan [30] presented an $O(n^{3/2}\log^{5}n)$-time algorithm
for computing a minimum-weight matching in the plane, which is the best-known
running time for Euclidean minimum-weight matching till date. Agarwal et al.
[7] gave a near quadratic time algorithm for the bipartite version of the
problem, improving upon the sub-cubic algorithm of Vaidya [29]. Several recent
approximation algorithms were developed with improved running times for
bipartite and non-bipartite versions; see [6, 25, 8].

#### Dynamic Graph Matching.

In this problem, the objective is to maintain a maximal cardinality matching
as the input graph is subject to discrete changes, i.e., at each time step,
either a vertex (or edge) is added or deleted. Dynamic graph matching
algorithms have been extensively studied over the past few decades. However,
most of these algorithms consider dynamic graphs which are subject to discrete
edge updates, as also noted by Grandoni et al. [27]. Sankowski [26] showed how
to maintain the size of the maximum matching with $O(n^{1.495})$ worst-case
update time. Moreover, it is known that maintaining an exact matching requires
polynomial update time under complexity conjectures [1]. Therefore, most of
the research has been focused on maintaining an approximate solution. It is
possible to maintain a $2$-approximate matching with constant amortized update
time [27]. However, one can maintain a $(1+\varepsilon)$-approximate solution
in the fully-dynamic setting with update time $O(\sqrt{m}/\varepsilon^{2})$
[19].

#### Online Matching.

Karp, Vazirani, and Vazirani studied the bipartite vertex-arrival model in
their seminal work [20]. Most of the classical online matching algorithms are
on the server-client paradigm, where one side of a bipartite graph is revealed
at the beginning. Raghvendra [24] studied the online bipartite matching
problem for a set of points on a line (see also [22]). Gamlath et al. [18]
studied the online matching problem on edge arrival model. Despite of the
remarkable progress of the online matching problem over the decades, the
online minimum matching with vertex arrivals has not been studied (where no
side is revealed at the beginning).

###  1.2 Our contribution

In Section 2, we present a dynamic algorithm that maintains a bottleneck
matching of a set $P$ of $n$ points on a line with $O(\log n)$ update
(insertion or deletion) time. Then, in Section 3, we generalize this algorithm
to maintain a minimum-weight matching of $P$ with $O(\log n)$ update time. For
a set $P$ of points in the plane with bounded geometric spread $\Delta$, in
Section 4, we present a dynamic algorithm that maintains a
$(6\sqrt{2})$-approximate bottleneck matching of $P_{k}$, at each time step
$k$, and supports insertion in $O(\log{\Delta})$ amortized time and deletion
in $O(\log{\Delta}+|P_{k}|)$ amortized time.

##  2 Dynamic Bottleneck Matching in 1D

Let $P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ be a set of $n$ points located on a
horizontal line, such that $p_{i}$ is to the left of $p_{i+1}$, for every
$0\leq i<n$. In this section, we present a dynamic algorithm that maintains a
bottleneck matching of $P$ with logarithmic update time. Throughout this
section, we assume that $n$ is even and two points are added or deleted in
each step. However, our algorithm can be generalized for every $n$ and every
constant number of points added or deleted in each step, regardless of the
parity of $n$; see Section 3.

###### Observation 2.1

There exists a bottleneck matching $M$ of $P$, such that each point $p_{i}\in
P$ is matched to a point from $\\{p_{i-1},p_{i+1}\\}$.

###### Proof

Let $M^{\prime}$ be a bottleneck matching of $P$ in which there exists at
least one point $p_{i}$ that is not matched to $p_{i-1}$ or to $p_{i+1}$. We
do the following for each such a point $p_{i}$. Let $p_{i}$ be the leftmost
point in $P$ that is matched in $M^{\prime}$ to a point $p_{j}$, where
$j>i+1$. Let $p_{j^{\prime}}$ be the point that is matched to $p_{i+1}$, and
notice that $j^{\prime}>i+1$. Let $M^{\prime\prime}$ be the matching obtained
by replacing the edges $(p_{i},p_{j})$ and $(p_{i+1},p_{j^{\prime}})$ in
$M^{\prime}$ by the edges $(p_{i},p_{i+1})$ and $(p_{j},p_{j^{\prime}})$; see
Figure 1. Clearly, $|p_{i}p_{i+1}|\leq|p_{i}p_{j}|$ and
$|p_{j}p_{j^{\prime}}|\leq\max\\{|p_{i}p_{j}|,|p_{i+1}p_{j^{\prime}}|\\}$.
Therefore, $M^{\prime\prime}$ is also a bottleneck matching in which $p_{i}$
is matched to $p_{i+1}$.

Figure 1: The matching of the points
$\\{p_{i},p_{i+1},p_{j},p_{j^{\prime}}\\}$ in $M^{\prime}$ (in black) and in
$M^{\prime\prime}$ (in blue).

Throughout the rest of this section, we refer to the bottleneck matching that
satisfies Observation 2.1 as the optimal matching, and notice that this
matching is unique.

###  2.1 Preprocessing

Let $M$ be the optimal matching of $P$ and let $bn(M)$ denote its bottleneck.
Clearly, $M$ can be computed in $O(n)$ time. We maintain $M$ in a full AVL
tree ${{\cal{T}}}$, such that the leaves of ${{\cal{T}}}$ are the points of
$P$, and each intermediate node has exactly two children and contains some
extra information, propagated from its children. For a node $v$ in
${{\cal{T}}}$, let $T_{v}$ be the sub-tree of ${{\cal{T}}}$ rooted at $v$, and
let $P_{v}$ be the subset of $P$ containing the points in the leaves of
$T_{v}$. For each node $v$ in ${{\cal{T}}}$, let $lc(v),rc(v)$ be the left and
the right children of $v$, respectively, and $p(v)$ be the parent of $v$.

Each node $v$ in ${{\cal{T}}}$ contains the following seven attributes about
the optimal matching of the points in $P_{v}$:

  1. 1.

LeftMost$(v)$ \- the leftmost point in $P_{v}$.

  2. 2.

RightMost$(v)$ \- the rightmost point in $P_{v}$.

  3. 3.

$\pi(v)=|{{\textsc{RightMost}}}(lc(v)){{\textsc{LeftMost}}}(rc(v)|$ \- the
Euclidean distance
between ${{\textsc{RightMost}}}(lc(v))$ and ${{\textsc{RightMost}}}(lc(v))$.

  4. 4.

All$(v)$ \- cost of the matching of the points in $P_{v}$.

  5. 5.

All-L$(v)$ \- cost of the matching of the points in
$P_{v}\setminus\\{{{\textsc{LeftMost}}}(v)\\}$.

  6. 6.

All-R$(v)$ \- cost of the matching of the points in
$P_{v}\setminus\\{{{\textsc{RightMost}}}(v)\\}$.

  7. 7.

All-LR$(v)$ \- cost of the matching of the points in
$P_{v}\setminus\\{{{\textsc{LeftMost}}}(v),$
${{\textsc{RightMost}}}(v)\\}$.

Now, we describe how to compute the values of the attributes in each node $v$.
The computation is bottom-up. That is, we first initialize the attributes of
the leaves and then, for each intermediate node $v$, we compute its attributes
from the attributes of its children $lc(v)$ and $rc(v)$.

For each leaf $v$ in ${{\cal{T}}}$, we set ${{\textsc{All}}}(v)$ and
${{\textsc{All-LR}}}(v)$ to be $\infty$, ${{\textsc{All-L}}}(v)$ and
${{\textsc{All-R}}}(v)$ to be 0, and ${{\textsc{LeftMost}}}(v)$ and
${{\textsc{RightMost}}}(v)$ to be $v$. For each intermediate $v$ in
${{\cal{T}}}$, we compute its attributes as follows.

$\displaystyle{{\textsc{All}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(lc(v))\,,{{\textsc{All}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(lc(v))\,,{{\textsc{All-L}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$
$\displaystyle{{\textsc{All-L}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(lc(v))\,,{{\textsc{All}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(lc(v))\,,{{\textsc{All-L}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$
$\displaystyle{{\textsc{All-R}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(lc(v))\,,{{\textsc{All-R}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(lc(v))\,,{{\textsc{All-
LR}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$ $\displaystyle{{\textsc{All-
LR}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(lc(v))\,,{{\textsc{All-R}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(lc(v))\,,{{\textsc{All-LR}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$

Clearly, these values can be computed in constant time, for each node $v$ in
${{\cal{T}}}$, given the attributes of its children. Therefore, the
preprocessing time is $O(n)$.

###### Lemma 1

Let $r^{*}$ be the root of ${{\cal{T}}}$. Then,
${{\textsc{All}}}(r^{*})=bn(M)$.

###### Proof

For a node $v$ in ${{\cal{T}}}$ where $|P_{v}|$ is even, let $M_{v}$ denote
the optimal matching of the points in $P_{v}$, and let ${{\textsc{Mlr}}}_{v}$
denote the optimal matching of the points in
$P_{v}\setminus\\{{{\textsc{LeftMost}}}(v),{{\textsc{RightMost}}}(v)\\}$. For
a node $v$ in ${{\cal{T}}}$ where $|P_{v}|$ is odd, let ${{\textsc{Ml}}}_{v}$
denote the optimal matching of the points in
$P_{v}\setminus\\{{{\textsc{LeftMost}}}(v)\\}$, and let ${{\textsc{Mr}}}_{v}$
denote the optimal matching of the points in
$P_{v}\setminus\\{{{\textsc{RightMost}}}(v)\\}$.

To prove the lemma, we prove a stronger claim. For each node $v$ in
${{\cal{T}}}$, we prove that

  * •

if $|P_{v}|$ is even, then ${{\textsc{All}}}(v)=bn(M_{v})$,
${{\textsc{All-L}}}(v)={{\textsc{All-R}}}(v)=\infty$, and ${{\textsc{All-
LR}}}(v)=bn({{\textsc{Mlr}}}_{v})$.

  * •

if $|P_{v}|$ is odd, then ${{\textsc{All}}}(v)={{\textsc{All-LR}}}(v)=\infty$,
${{\textsc{All-L}}}(v)=bn({{\textsc{Ml}}}_{v})$, and
${{\textsc{All-R}}}(v)=bn({{\textsc{Mr}}}_{v})$.

The proof is by induction on the height of $v$ in ${{\cal{T}}}$.
Base case: The claim holds for each leaf $v$ in ${{\cal{T}}}$, since
$|P_{v}|=1$ and we initialize the attributes of $v$ by the values
${{\textsc{All}}}(v)={{\textsc{All-LR}}}(v)=\infty$ and
${{\textsc{All-L}}}(v)={{\textsc{All-R}}}(v)=0$. Moreover, for each node $v$
in height one, we have $|P_{v}|=2$ and $v$ has two leaves $l$ and $r$ at
height zero. Therefore,

$\displaystyle{{\textsc{All}}}(r)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(l)\,,{{\textsc{All}}}(r))\big{\\}}\,,\max\big{\\{}{{\textsc{All-R}}}(l)\,,{{\textsc{All-L}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}\infty\,,\infty\big{\\}}\,,\max\big{\\{}0\,,0\,,|lr|\big{\\}}\Big{\\}}=|lr|\,.$
$\displaystyle{{\textsc{All-L}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(l)\,,{{\textsc{All}}}(r)\big{\\}}\,,\max\big{\\{}{{\textsc{All-
LR}}}(l)\,,{{\textsc{All-L}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$
$\displaystyle\
\min\Big{\\{}\max\big{\\{}\infty\,,0\big{\\}}\,,\max\big{\\{}0\,,\infty\,,|lr|\big{\\}}\Big{\\}}=\infty\,.$
$\displaystyle{{\textsc{All-R}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(l)\,,{{\textsc{All-R}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(l)\,,{{\textsc{All-
LR}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}0\,,\infty\big{\\}}\,,\max\big{\\{}\infty\,,0\,,|lr|\big{\\}}\Big{\\}}=\infty\,.$
$\displaystyle{{\textsc{All-LR}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(l)\,,{{\textsc{All-R}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(l)\,,{{\textsc{All-LR}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$
$\displaystyle\
\min\Big{\\{}\max\big{\\{}0\,,0\big{\\}}\,,\max\big{\\{}\infty\,,\infty\,,|lr|\big{\\}}\Big{\\}}=0\,.$

Induction step: We prove the claim for each node $v$ at height $h>1$. Let
$l=lc(v)$ and $r=rc(v)$. Let $p$ and $q$ be the rightmost and the leftmost
points in $P_{l}$ and $P_{r}$, respectively. Thus, $\pi(v)=|pq|$. We
distinguish between four cases.

Case 1: $|P_{v}|$ is even and both $|P_{l}|$ and $|P_{r}|$ are even.
Since $|P_{v}|$ is even, $M_{v}$ consists of the optimal matching $M_{l}$ of
$P_{l}$ and the optimal matching $M_{r}$ of $P_{r}$, and
$bn(M_{v})=\max\\{bn(M_{l}),bn(M_{r})\\}$. Moreover, ${{\textsc{Mlr}}}_{v}$
consists of the optimal matching ${{\textsc{Mlr}}}_{l}$ of
$P_{l}\setminus\\{{{\textsc{LeftMost}}}(l),{{\textsc{RightMost}}}(l)\\}$, the
optimal matching ${{\textsc{Mlr}}}_{r}$ of
$P_{r}\setminus\\{{{\textsc{LeftMost}}}(r),{{\textsc{RightMost}}}(r)\\}$, and
the edge $(p,q)$. Thus,
$bn({{\textsc{Mlr}}}_{v})=\max\\{bn({{\textsc{Mlr}}}_{l}),bn({{\textsc{Mlr}}}_{r}),|pq|\\}$.

By the induction hypothesis, ${{\textsc{All}}}(l)=bn(M_{l})$,
${{\textsc{All}}}(r)=bn(M_{r})$, ${{\textsc{All-
LR}}}(l)=bn({{\textsc{Mlr}}}_{l})$, ${{\textsc{All-
LR}}}(r)=bn({{\textsc{Mlr}}}_{r})$, and
${{\textsc{All-L}}}(l)={{\textsc{All-R}}}(l)={{\textsc{All-L}}}(l)={{\textsc{All-R}}}(l)=\infty$.
Therefore, we have

$\displaystyle{{\textsc{All}}}(r)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(l)\,,{{\textsc{All}}}(r))\big{\\}}\,,\max\big{\\{}{{\textsc{All-R}}}(l)\,,{{\textsc{All-L}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}bn(M_{l})\,,bn(M_{r})\big{\\}}\,,\max\big{\\{}\infty\,,\infty\,,|pq|\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\ \max\\{bn(M_{l})\,,bn(M_{r})\\}=bn(M_{v})\,.$
$\displaystyle{{\textsc{All-L}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(l)\,,{{\textsc{All}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(l)\,,{{\textsc{All-L}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$
$\displaystyle\
\min\Big{\\{}\max\big{\\{}\infty\,,bn(M_{r})\big{\\}}\,,\max\big{\\{}bn({{\textsc{Mlr}}}_{l})\,,\infty\,,|pq|\big{\\}}\Big{\\}}=\infty\,.$
$\displaystyle{{\textsc{All-R}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(l)\,,{{\textsc{All-R}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(l)\,,{{\textsc{All-
LR}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}bn(M_{l})\,,\infty\big{\\}}\,,\max\big{\\{}\infty\,,bn({{\textsc{Mlr}}}_{r})\,,|pq|\big{\\}}\Big{\\}}=\infty\,.$
$\displaystyle{{\textsc{All-LR}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(l)\,,{{\textsc{All-R}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(l)\,,{{\textsc{All-LR}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$
$\displaystyle\
\min\Big{\\{}\max\big{\\{}\infty\,,\infty\big{\\}}\,,\max\big{\\{}bn({{\textsc{Mlr}}}_{l})\,,bn({{\textsc{Mlr}}}_{r})\,,|pq|\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\max\big{\\{}bn({{\textsc{Mlr}}}_{l})\,,bn({{\textsc{Mlr}}}_{r})\,,|pq|\big{\\}}=bn({{\textsc{Mlr}}}_{v})\,.$

Case 2: $|P_{v}|$ is even and both $|P_{l}|$ and $|P_{r}|$ are odd.
Since $|P_{v}|$ is even, $M_{v}$ consists of the optimal matching
${{\textsc{Ml}}}_{r}$ of $P_{r}\setminus\\{{{\textsc{LeftMost}}}(r)\\}$, the
optimal matching ${{\textsc{Mr}}}_{l}$ of
$P_{l}\setminus\\{{{\textsc{RightMost}}}(l)\\}$, and the edge $(p,q)$. Thus,
$bn(M_{v})=\max\\{bn({{\textsc{Ml}}}_{r}),bn({{\textsc{Mr}}}_{l}),|pq|\\}$.
Moreover, ${{\textsc{Mlr}}}_{v}$ consists of the optimal matching
${{\textsc{Ml}}}_{l}$ of $P_{l}\setminus\\{{{\textsc{LeftMost}}}(l)\\}$ and
the optimal matching ${{\textsc{Mr}}}_{r}$ of
$P_{r}\setminus\\{{{\textsc{RightMost}}}(r)\\}$, and
$bn({{\textsc{Mlr}}}_{v})=\max\\{bn({{\textsc{Ml}}}_{l}),bn({{\textsc{Mr}}}_{r})\\}$.

By the induction hypothesis, ${{\textsc{All}}}(l)={{\textsc{All-
LR}}}(l)={{\textsc{All}}}(r)={{\textsc{All-LR}}}(r)=\infty$,
${{\textsc{All-R}}}(l)=bn({{\textsc{Mr}}}_{l})$,
${{\textsc{All-L}}}(l)=bn({{\textsc{Ml}}}_{l})$,
${{\textsc{All-R}}}(r)=bn({{\textsc{Mr}}}_{r})$, and
${{\textsc{All-L}}}(r)=bn({{\textsc{Ml}}}_{r})$. Therefore, we have

$\displaystyle{{\textsc{All}}}(r)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(l)\,,{{\textsc{All}}}(r))\big{\\}}\,,\max\big{\\{}{{\textsc{All-R}}}(l)\,,{{\textsc{All-L}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}\infty\,,\infty\big{\\}}\,,\max\big{\\{}bn({{\textsc{Mr}}}_{l})\,,bn({{\textsc{Ml}}}_{r})\,,|pq|\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\max\big{\\{}bn({{\textsc{Mr}}}_{l})\,,bn({{\textsc{Ml}}}_{r})\,,|pq|\big{\\}}=bn(M_{v})\,.$
$\displaystyle{{\textsc{All-L}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(l)\,,{{\textsc{All}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(l)\,,{{\textsc{All-L}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$
$\displaystyle\
\min\Big{\\{}\max\big{\\{}bn({{\textsc{Ml}}}_{l})\,,\infty\big{\\}}\,,\max\big{\\{}\infty\,,bn({{\textsc{Ml}}}_{r})\,,|pq|\big{\\}}\Big{\\}}=\infty\,.$
$\displaystyle{{\textsc{All-R}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(l)\,,{{\textsc{All-R}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(l)\,,{{\textsc{All-
LR}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}\infty\,,bn({{\textsc{Mr}}}_{r})\big{\\}}\,,\max\big{\\{}bn({{\textsc{Mr}}}_{l})\,,\infty\,,|pq|\big{\\}}\Big{\\}}=\infty\,.$
$\displaystyle{{\textsc{All-LR}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(l)\,,{{\textsc{All-R}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(l)\,,{{\textsc{All-LR}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$
$\displaystyle\
\min\Big{\\{}\max\big{\\{}bn({{\textsc{Ml}}}_{l})\,,bn({{\textsc{Mr}}}_{r})\big{\\}}\,,\max\big{\\{}\infty\,,\infty\,,|pq|\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\max\big{\\{}bn({{\textsc{Ml}}}_{l})\,,bn({{\textsc{Mr}}}_{r})\big{\\}}=bn({{\textsc{Mlr}}}_{v})\,.$

Case 3: $P_{v}$ is odd, $|P_{l}|$ is even, and $|P_{r}|$ is odd.
Since $P_{v}$ is odd, there is no optimal matching $M_{v}$ of $P_{v}$, and
thus $bn(M_{v})=\infty$. Moreover, ${{\textsc{Mr}}}_{v}$ consists of the
optimal matching $M_{l}$ of $P_{l}$ and the optimal matching
${{\textsc{Mr}}}_{r}$ of $P_{r}\setminus\\{{{\textsc{RightMost}}}(r)\\}$, and
${{\textsc{Ml}}}_{v}$ consists of the optimal matching ${{\textsc{Mlr}}}_{l}$
of $P_{l}\setminus\\{{{\textsc{LeftMost}}}(l),{{\textsc{RightMost}}}(l)\\}$,
the optimal matching ${{\textsc{Ml}}}_{r}$ of
$P_{r}\setminus\\{{{\textsc{LeftMost}}}(r)\\}$, and the edge $(p,q)$. Thus,
$bn({{\textsc{Mr}}}_{v})=\max\\{bn(M_{l}),bn({{\textsc{Mr}}}_{r})\\}$ and
$bn({{\textsc{Ml}}}_{v})=\max\\{bn({{\textsc{Mlr}}}_{l}),bn({{\textsc{Ml}}}_{r}),|pq|\\}$.

By the induction hypothesis, ${{\textsc{All}}}(r)={{\textsc{All-
LR}}}(r)={{\textsc{All-L}}}(l)={{\textsc{All-R}}}(l)=\infty$,
${{\textsc{All}}}(l)=bn(M_{l})$, ${{\textsc{All-
LR}}}(l)=bn({{\textsc{Mlr}}}_{l})$,
${{\textsc{All-R}}}(r)=bn({{\textsc{Mr}}}_{r})$, and
${{\textsc{All-L}}}(r)=bn({{\textsc{Ml}}}_{r})$. Therefore, we have

$\displaystyle{{\textsc{All}}}(r)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(l)\,,{{\textsc{All}}}(r))\big{\\}}\,,\max\big{\\{}{{\textsc{All-R}}}(l)\,,{{\textsc{All-L}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}bn(M_{l})\,,\infty\big{\\}}\,,\max\big{\\{}\infty\,,bn({{\textsc{Ml}}}_{r})\,,|pq|\big{\\}}\Big{\\}}=\infty\,.$
$\displaystyle{{\textsc{All-L}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(l)\,,{{\textsc{All}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(l)\,,{{\textsc{All-L}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$
$\displaystyle\
\min\Big{\\{}\max\big{\\{}\infty\,,\infty\big{\\}}\,,\max\big{\\{}bn({{\textsc{Mlr}}}_{l})\,,bn({{\textsc{Ml}}}_{r})\,,|pq|\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\max\big{\\{}bn({{\textsc{Mlr}}}_{l})\,,bn({{\textsc{Ml}}}_{r})\,,|pq|\big{\\}}=bn({{\textsc{Ml}}}_{v})\,.$
$\displaystyle{{\textsc{All-R}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(l)\,,{{\textsc{All-R}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(l)\,,{{\textsc{All-
LR}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}bn(M_{l})\,,bn({{\textsc{Mr}}}_{r})\big{\\}}\,,\max\big{\\{}\infty\,,\infty\,,|pq|\big{\\}}\Big{\\}}$
$\displaystyle=$ $\displaystyle\
\max\big{\\{}bn(M_{l})\,,bn({{\textsc{Mr}}}_{r})\big{\\}}=bn({{\textsc{Mr}}}_{v})\,.$
$\displaystyle{{\textsc{All-LR}}}(v)=$ $\displaystyle\
\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(l)\,,{{\textsc{All-R}}}(r)\big{\\}}\,,$
$\displaystyle\ \quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(l)\,,{{\textsc{All-LR}}}(r)\,,\pi(v)\big{\\}}\Big{\\}}$ $\displaystyle=$
$\displaystyle\
\min\Big{\\{}\max\big{\\{}\infty\,,bn({{\textsc{Mr}}}_{r})\big{\\}}\,,\max\big{\\{}bn({{\textsc{Mlr}}}_{l})\,,\infty\,,|pq|\big{\\}}\Big{\\}}=\infty\,.$

Case 4: $P_{v}$ is odd, $|P_{l}|$ is odd, and $|P_{r}|$ is even.
This case is symmetric to Case 3.

###  2.2 Dynamization

Let $P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ be the set of points at some time step
and let ${{\cal{T}}}$ be the AVL tree maintaining the optimal matching $M$ of
$P$. Let $r$ denote the root of ${{\cal{T}}}$. In the following, we describe
how to update ${{\cal{T}}}$ when inserting two points to $P$ or deleting two
points from $P$.

### Insertion

Let $q$ and $q^{\prime}$ be the two points inserted to $P$. We describe the
procedure for inserting $q$. The same procedure is applied for inserting
$q^{\prime}$. We initialize a leaf node corresponding to $q$ and insert it to
${{\cal{T}}}$. Then, we update the attributes of the intermediate nodes along
the path from $q$ to the root of ${{\cal{T}}}$.

Let $M^{\prime}$ be the optimal matching of $P\cup\\{q,q^{\prime}\\}$. Then,
by Lemma 1, after inserting $q$ and $q^{\prime}$ to $P$,
${{\textsc{All}}}(r)=bn(M^{\prime})$.

### Deletion

Let $q$ and $q^{\prime}$ be the two points deleted from $P$. We describe the
procedure for deleting $q$. The same procedure is applied for deleting
$q^{\prime}$. Assume w.l.o.g. that $q$ is the right child of $p(q)$. If the
left child $t$ of $p(q)$ is a leaf, then we set the attributes of $t$ to
$p(q)$, remove $q$ and $t$ from ${{\cal{T}}}$, and update the attributes of
the intermediate nodes along the path from $p(q)$ to the root of
${{\cal{T}}}$; see Figure 2(top). Otherwise, the left child $t$ of $p(q)$ is
an intermediate node with left leaf $l$ and right leaf $r$. We set the
attributes of $l$ to $t$ and the attributes of $r$ to $q$, remove $l$ and $r$
from ${{\cal{T}}}$, and update the attributes of the intermediate nodes along
the path from $p(q)$ to the root of ${{\cal{T}}}$; see Figure 2(bottom).

Figure 2: Deleting $q$ from ${{\cal{T}}}$.

Let $M^{\prime}$ be the optimal matching of $P\setminus\\{q,q^{\prime}\\}$.
Then, by Lemma 1, after deleting $q$ and $q^{\prime}$ from $P$,
${{\textsc{All}}}(r)=bn(M^{\prime})$.

Finally, since we use an AVL tree, we may need to make some rotations after an
insertion or a deletion. For each rotation performed on ${{\cal{T}}}$, we also
update the attributes of the (constant number of) intermediate nodes involved
in the rotation.

###### Lemma 2

The running time of an update operation (insertion or deletion) is
$O(\log{n})$.

###### Proof

Since ${{\cal{T}}}$ is an AVL tree, the height of ${{\cal{T}}}$ is
$O(\log{n})$ [15]. Each operation requires updating the attributes of the
nodes along the path from a leaf to the root, and each such update takes
$O(1)$ time. Moreover, each rotation also requires updating the attributes of
the nodes involved in the rotation, and each such update also takes $O(1)$
time . Since in insertion there is at most one rotation and in deletion there
are at most $O(\log{n})$ rotations, the total running time of each insertion
and each deletion is $O(\log{n})$.

The following theorem summarizes the result of this section.

###### Theorem 2.2

Let $P$ be a set of $n$ points on a line. There exists a dynamic algorithm
that maintains a bottleneck matching of $P$ and supports insertion and
deletion in $O(\log n)$ time.

##  3 Extensions for 1D

In this section, we extend our algorithm to maintain a minimum-weight matching
of $P$ (instead of bottleneck matching). Moreover, we extend the algorithm to
allow inserting/deleting a constant (even or odd) number of points to/from
$P$.

###  3.1 Minimum-weight matching

We modify our algorithm to maintain a minimum-weight matching and support
insertion and deletion, without affecting the running time. The difference
lies in the way we compute the attributes of the intermediate nodes from their
children. That is, for each intermediate node $v$, we compute its attributes
as follows:

$\displaystyle{{\textsc{All}}}(v)\leftarrow$
$\displaystyle\min\big{\\{}{{\textsc{All}}}(lc(v))+{{\textsc{All}}}(rc(v))\,,$
$\displaystyle\quad\ \quad\
{{\textsc{All-R}}}(lc(v))+{{\textsc{All-L}}}(rc(v))+\pi(v)\big{\\}}\,.$
$\displaystyle{{\textsc{All-L}}}(v)\leftarrow$
$\displaystyle\min\big{\\{}{{\textsc{All-L}}}(lc(v))+{{\textsc{All}}}(rc(v))\,,$
$\displaystyle\quad\ \quad\ {{\textsc{All-
LR}}}(lc(v))+{{\textsc{All-L}}}(rc(v))+\pi(v)\big{\\}}\,.$
$\displaystyle{{\textsc{All-R}}}(v)\leftarrow$
$\displaystyle\min\big{\\{}{{\textsc{All}}}(lc(v))+{{\textsc{All-R}}}(rc(v))\,,$
$\displaystyle\quad\ \quad\ {{\textsc{All-R}}}(lc(v))+{{\textsc{All-
LR}}}(rc(v))+\pi(v)\big{\\}}\,.$ $\displaystyle{{\textsc{All-
LR}}}(v)\leftarrow$
$\displaystyle\min\big{\\{}{{\textsc{All-L}}}(lc(v))+{{\textsc{All-R}}}(rc(v))\,,$
$\displaystyle\quad\ \quad\ {{\textsc{All-LR}}}(lc(v))+{{\textsc{All-
LR}}}(rc(v))+\pi(v)\big{\\}}\,.$

Notice that the running time of an update operation ($O(\log{n})$ per
insertion or deletion) is as in the bottleneck matching. The proof of the
correctness of this algorithm for the minimum-weight matching is similar to
the proof of the correctness of the bottleneck matching.

###  3.2 Insertion and deletion of $k$ points

Let $P$ be a set of $n$ points on a line. In this section, we extend our
algorithm to support insertion/deletion of $k$ points to/from $P$ at each time
step. Notice that since we allow $k$ to be odd, $n$ can be odd and the
matching should skip one point. Even though there are linear different
candidate points that could be skipped, we can still maintain a bottleneck
matching with $O(k\log{n})$ time per $k$ insertions or deletions, by adding
some more attributes for each node. Each node $v$ in ${{\cal{T}}}$ contains
the following four attributes, in addition to the seven attributes that are
described in Section 2.1.

  1. 8.

${{\textsc{All-1}}}(v)$ \- cost of the matching of $|P_{v}|-1$ points of
$P_{v}$.

  2. 9.

${{\textsc{All-1-L}}}(v)$ \- cost of the matching of $|P_{v}|-1$ points of
$P_{v}\setminus\\{{{\textsc{LeftMost}}}(v)\\}$.

  3. 10.

${{\textsc{All-1-R}}}(v)$ \- cost of the matching of $|P_{v}|-1$ points of
$P_{v}\setminus\\{{{\textsc{RightMost}}}(v)\\}$.

  4. 11.

${{\textsc{All-1-LR}}}(v)$ \- cost of the matching of $|P_{v}|-1$ points of
$P_{v}\setminus\\{{{\textsc{LeftMost}}}(v),$
${{\textsc{RightMost}}}(v)\\}$.

For each leaf $v$ in ${{\cal{T}}}$, we initialize ${{\textsc{All-1}}}(v)$ to
be 0, and ${{\textsc{All-1-L}}}(v)$, ${{\textsc{All-1-R}}}(v)$, and
${{\textsc{All-1-LR}}}(v)$ to be $\infty$. For each intermediate node $v$ in
${{\cal{T}}}$, we compute its attributes as follows.

$\displaystyle{{\textsc{All}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(lc(v))\,,{{\textsc{All}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(lc(v))\,,{{\textsc{All-L}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$
$\displaystyle{{\textsc{All-L}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(lc(v))\,,{{\textsc{All}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(lc(v))\,,{{\textsc{All-L}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$
$\displaystyle{{\textsc{All-R}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All}}}(lc(v))\,,{{\textsc{All-R}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(lc(v))\,,{{\textsc{All-
LR}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$ $\displaystyle{{\textsc{All-
LR}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All-L}}}(lc(v))\,,{{\textsc{All-R}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(lc(v))\,,{{\textsc{All-LR}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$
$\displaystyle{{\textsc{All-1}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All-1}}}(lc(v))\,,{{\textsc{All}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All}}}(lc(v))\,,{{\textsc{All-1}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-1-R}}}(lc(v))\,,{{\textsc{All-L}}}(rc(v))\,,\pi(v)\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(lc(v))\,,{{\textsc{All-1-L}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$
$\displaystyle{{\textsc{All-1-L}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All-1-L}}}(lc(v))\,,{{\textsc{All}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-L}}}(lc(v))\,,{{\textsc{All-1}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-1-LR}}}(lc(v))\,,{{\textsc{All-L}}}(rc(v))\,,\pi(v)\big{\\}}\,,$
$\displaystyle\quad\ \quad\ \max\big{\\{}{{\textsc{All-
LR}}}(lc(v))\,,{{\textsc{All-1-L}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$
$\displaystyle{{\textsc{All-1-R}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All-1}}}(lc(v))\,,{{\textsc{All-R}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All}}}(lc(v))\,,{{\textsc{All-1-R}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-1-R}}}(lc(v))\,,{{\textsc{All-
LR}}}(rc(v))\,,\pi(v)\big{\\}}\,,$ $\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-R}}}(lc(v))\,,{{\textsc{All-1-LR}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$
$\displaystyle{{\textsc{All-1-LR}}}(v)\leftarrow$
$\displaystyle\min\Big{\\{}\max\big{\\{}{{\textsc{All-1-L}}}(lc(v))\,,{{\textsc{All-R}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-L}}}(lc(v))\,,{{\textsc{All-1-R}}}(rc(v))\big{\\}}\,,$
$\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-1-LR}}}(lc(v))\,,{{\textsc{All-
LR}}}(rc(v))\,,\pi(v)\big{\\}}\,,$ $\displaystyle\quad\ \quad\
\max\big{\\{}{{\textsc{All-
LR}}}(lc(v))\,,{{\textsc{All-1-LR}}}(rc(v))\,,\pi(v)\big{\\}}\Big{\\}}\,.$

Let $r^{*}$ be the root of ${{\cal{T}}}$. In the case that $n$ is even, let
$M$ be the bottleneck matching for $P_{r^{*}}$ satisfying Observation 2.1. In
the case that $n$ is odd, let $M_{q}$ be the bottleneck matching for
$P_{r^{*}}\setminus\\{q\\}$ satisfying Observation 2.1. Let $M^{\prime}$ the
bottleneck matching such that $bn(M^{\prime})=\min_{q\in
P_{r^{*}}}\\{bn(M_{q})\\}$.

###### Lemma 3

Let $r^{*}$ be the root of ${{\cal{T}}}$.

  * •

If $n$ is even, then ${{\textsc{All}}}(r^{*})=bn(M)$.

  * •

If $n$ is odd, then ${{\textsc{All-1}}}(r^{*})=bn(M^{\prime})$.

The proof of Lemma 3 is similar to the proof of Lemma 1. Moreover, the
insertion and the deletion operations are done as in Section 2.2. After each
operation, we update the attributes (including the new attributes) of the
intermediate nodes along the path from a leaf to the root.

The running time of $O(k\log{n})$ is obtained by performing the operation
(insertion or deletion) $k$ times. That is, when we are requested to
insert/delete $k$ points we add/remove them one by one. Thus, the $O(\log{n})$
time per update operation is performed $k$ times.

##  4 Dynamic Bottleneck Matching in 2D

Let ${{\mathcal{P}}}=P_{1}\cup P_{2}\cup\dots$ be a set of $n$ points in the
plane, such that each set $P_{k+1}$ is obtained by adding a pair of points to
$P_{k}$ or by removing a pair of points from $P_{k}$. Let $\lambda_{k}$ be the
distance between the closest pair of points in $P_{k}$. In our setting, we
assume that we are given a bounding box ${{\cal{B}}}$ of side length $\Lambda$
and a constant $\lambda>0$, such that $P_{k}$ is contained in ${{\cal{B}}}$
and $\lambda\leq\lambda_{k}$, for each $k\geq 1$, and
$\Delta={\Lambda\over\lambda}$ is polynomially bounded in $n$, i.e.,
$\log{\Delta}=O(\log{n})$.

At each time step $k\in\mathbb{N}$, either a pair of points of $P$ is inserted
or deleted. Let $P_{k}$ be the set of points at time step $k$ and let
$M^{*}_{k}$ be a bottleneck matching of $P_{k}$ of bottleneck $bn(M^{*}_{k})$.
In this section, we present a dynamic data structure supporting insertion in
$O(\log{\Delta})$ time and deletion in $O(\log{\Delta}+|P_{k}|)$ time, such
that a perfect matching $M_{k}$ of $P_{k}$ of bottleneck at most
$6\sqrt{2}\cdot bn(M^{*}_{k})$ can be computed in $O(\log{\Delta}+|P_{k}|)$
time.

Let ${{\cal{B}}}$ be the bounding box containing the points of
${{\mathcal{P}}}$. Set $c=\left\lceil{{\log\Delta}}\right\rceil$. For each
integer $0\leq i\leq c$, let $\Pi_{i}$ be the grid obtained by dividing
${{\cal{B}}}$ into cells of side length $2^{i}\cdot\lambda$. We say that two
cells are adjacent in $\Pi_{i}$ if they share a side or a corner in $\Pi_{i}$.

Let $P=P_{k}$ be the set of points at some time step $k$. For each grid
$\Pi_{i}$, we define an undirected graph $G_{i}$, such that the vertices of
$G_{i}$ are the non-empty cells of $\Pi_{i}$, and there is an edge between two
non-empty cells in $G_{i}$ if these cells are adjacent in $\Pi_{i}$. For a
vertex $v$ in $G_{i}$, let $P_{v}$ be the set of points of $P$ that are
contained in the cell in $\Pi_{i}$ corresponding to $v$. For a connected
component $C$ in $G_{i}$, let $P(C)=\bigcup_{v\in C}P_{v}$, i.e., the set of
the points contained in the cells corresponding to the vertices of $C$.
Moreover, we assume that each graph $G_{i}$ has a parity bit that indicates
whether all the connected components of $G_{i}$ contain an even number of
points or not.

###### Lemma 4

Let $C$ be a connected component in $G_{i}$. If $|P(C)|$ is even, then there
exists a perfect matching of the points of $P(C)$ of bottleneck at most
$3\sqrt{2}\cdot 2^{i}\cdot\lambda$. Moreover, this matching can be computed in
$O(|P(C)|)$ time.

###### Proof

Let $G_{C}$ be the subgraph of $G_{i}$ induced by $C$. Let $T$ be a spanning
tree of $G_{C}$ and assume that $T$ is rooted at a vertex $r$. We construct a
perfect matching of the points of $P(C)$ iteratively by considering $T$
bottom-up as follows. Let $v$ be the deepest vertex in $T$ which is not a
leaf, and let $v_{1},v_{2},\dots,v_{j}$ be its children in $T$. Notice that
$v_{1},v_{2},\dots,v_{j}$ are leaves. Let $P^{\prime}=\bigcup_{1\leq i\leq
j}P_{v_{i}}$ be the set of the points contained in the cells corresponding to
$v_{1},v_{2},\dots,v_{j}$. If $|P^{\prime}|$ is even, then we greedily match
the points in $P^{\prime}$ and remove the vertices $v_{1},v_{2},\dots,v_{j}$
from $T$. Otherwise, $|P^{\prime}|$ is odd. In this case, we select an
arbitrary point $p$ from the cell corresponding to $v$ and greedily match the
points in $P^{\prime}\cup\\{p\\}$. Moreover, we remove $p$ from the cell
corresponding to $v$ and remove $v_{1},v_{2},\dots,v_{j}$ from $T$. We
continue this procedure until the root $r$ is encountered, i.e., until $v=r$.

Since $|P(C)|$ is even and in each iteration, we match an even number of
points, the number of the points in the last iteration is even and we get a
perfect matching of the points of $P(C)$. Moreover, since in each iteration we
match points from the cell corresponding to $v$ and its at most eight
neighbors in $\Pi_{i}$, and these cells are contained in $3\times 3$ cells-
block, the length of each edge in the matching is at most $3\sqrt{2}\cdot
2^{i}\cdot\lambda$.

Since the degree of each vertex in $G_{C}$ is at most eight, computing $T$
takes $O(|C|)$, and matching the points of $P^{\prime}$ in each iteration
takes $O(|P^{\prime}|)$. Therefore, computing the matching of the points of
$P(C)$ takes $O(|P(C)|)$ time.

Let $M^{*}$ be a bottleneck matching of $P$ and let $bn(M^{*})$ be its
bottleneck.

###### Lemma 5

If $bn(M^{*})\leq 2^{i}\cdot\lambda$, then, for every connected component $C$
in $G_{i}$, $|P(C)|$ is even.

###### Proof

Assume by contradiction that there is a connected component $C$ in $G_{i}$,
such that $|P(C)|$ is odd. Thus, at least one point $p\in P(C)$ is matched in
$M^{*}$ to a point $q\notin P(C)$. Therefore, $|pq|>2^{i}\cdot\lambda$, which
contradicts that $bn(M^{*})\leq 2^{i}\cdot\lambda$.

###### Theorem 4.1

In $O(\log{\Delta})$ time we can compute a value $t$, such that
$t<bn(M^{*})\leq 6\sqrt{2}\cdot t$. Moreover, we can compute a perfect
matching $M$ of $P$ of bottleneck at most $6\sqrt{2}\cdot bn(M^{*})$ in
$O(\log{\Delta}+|P|)$ time.

###### Proof

Let $i$ be the smallest integer such that all the connected components in
$G_{i}$ have an even number of points. Thus, by Lemma 5,
$bn(M^{*})>2^{i-1}\cdot\lambda$, and, by Lemma 4, there exists a perfect
matching of $P$ of bottleneck at most $3\sqrt{2}\cdot 2^{i}\cdot\lambda$.
Therefore, by taking $t=2^{i-1}\cdot\lambda$, we have $t<bn(M^{*})\leq
6\sqrt{2}\cdot t$. Since each graph $G_{i}$ has a parity bit, we can compute
$t$ in $O(\log{\Delta})$ time. Moreover, by Lemma 4, we can compute a perfect
matching $M$ of $P$ of bottleneck at most $3\sqrt{2}\cdot 2^{i}\cdot\lambda$
in $O(|P|)$ time. Therefore, $bn(M)\leq 3\sqrt{2}\cdot 2^{i}\cdot\lambda\leq
6\sqrt{2}\cdot bn(M^{*})$.

###  4.1 Preprocessing

We first introduce a data structure that will be used in the preprocessing.

### Disjoint-set data structure

A _disjoint-set data structure_ is a data structure that maintains a
collection $D$ of disjoint dynamic sets of objects and each set in $D$ has a
representative, which is some member of the set (see [15] for more details).
Disjoint-set data structures support the following operations:

  * •

Make-Set$(x)$ creates a new set whose only member (and thus representative) is
the object $x$.

  * •

Union$(S_{i},S_{j})$ merges the sets $S_{i}$ and $S_{j}$ and choose either the
representative of $S_{i}$ or the representative of $S_{j}$ to be the
representative of the resulting set.

  * •

Find-Set$(x)$ returns the representative of the (unique) set containing $x$.

It has been proven in [28] that performing a sequence of $m$ Make-Set, Union,
or Find-Set operations on a disjoint-set data structures with $n$ objects
requires total time $O(m\cdot\alpha(n))$, where $\alpha(n)$ is the extremely
slow-growing _inverse Ackermann function_. More precisely, it has been shown
that the amortized time of each one of the operations Make-Set, Union, and
Find-Set is $O(1)$.

We associate each set $S$ in $D$ with a variable $v_{S}$ that represents the
parity of $S$ depending on the number of points in $S$. We also modify the
operations Make-Set$(x)$ to initialize the parity variable of the created set
to be odd, and Union$(S_{i},S_{j})$ to update the parity variable of the
joined set according to the parities of $S_{i}$ and $S_{j}$. Moreover, we
define a new operation Change-Parity$(S)$ that inverses the parity of the set
$S$. Notice that these changes do not affect the performance of the data
structure.

We now describe how to initialize our data structure, given the bounding box
${{\cal{B}}}$, the constant $\lambda$, and an initial set $P_{1}$. Set
$c=\left\lceil{{\log\Delta}}\right\rceil$. For each integer $0\leq i\leq c$,
let $\Pi_{i}$ be the grid obtained by dividing ${{\cal{B}}}$ into cells of
side length $2^{i}\cdot\lambda$. For each grid $\Pi_{i}$, we use a disjoint-
set data structure $DSS_{i}$ to maintain the connected components of $G_{i}$
that is defined on $\Pi_{i}$ and $P_{1}$. That is, the objects of $DSS_{i}$
are the non-empty cells of $\Pi_{i}$, and if two non-empty cells share a side
or a corner in $\Pi_{i}$, then they are in the same set in $DSS_{i}$. This
data structure guarantees that each connected component in $G_{i}$ is a set in
$DSS_{i}$.

As mentioned above, constructing each $DSS_{i}$ can be done in $O(|P_{1}|)$
time. Therefore, the preprocessing time is $O(\log{\Delta}\cdot|P_{1}|)$.

###  4.2 Dynamization

Let $P$ be the set of points at some time step. In the following, we describe
how to update each structure $DSS_{i}$ when inserting two points to $P$ or
deleting two points from $P$.

### Insertion

Let $p$ and $q$ be the two points inserted to set $P$. We describe the
procedure for inserting $p$. The same procedure is applied for inserting $q$.
For each grid $\Pi_{i}$, we do the following; see Procedure 1. Let
$Cell_{i}(p)$ be the cell containing $p$ in $\Pi_{i}$. If $Cell_{i}(p)$
contains points of $P$, then we find the set containing $Cell_{i}(p)$ in
$DSS_{i}$ and change its parity. Otherwise, we make a new set in $DSS_{i}$
containing the cell $Cell_{i}(p)$ and merge (union) it with all the sets in
$DSS_{i}$ that contain a non-empty adjacent cell of $Cell_{i}(p)$, and update
the parity of the joined set.

Procedure 1 Insert($p$)

1: for each $0\leq i\leq c$ do

2: $Cell_{i}(p)\leftarrow$ the cell containing $p$ in $\Pi_{i}$

3: if $Cell_{i}(p)\cap P=\emptyset$ then /* $Cell_{i}(p)$ contains only $p$ */

4: Make-Set($Cell_{i}(p)$)

5: for each non-empty adjacent cell $C$ of $Cell_{i}(p)$ do

6: $S_{C}\leftarrow$ Find-Set($C$)

7: $S_{p}\leftarrow$ Find-Set($Cell_{i}(p)$)

8: Union($S_{C},S_{p}$)

9: else /* $Cell_{i}(p)$ contains points other than $p$ */

10: $S_{i}(p)\leftarrow$ Find-Set($Cell_{i}(p)$)

11: Change-Parity($S_{i}(p)$)

###### Lemma 6

Insert($p$) takes amortized $O(\log{\Delta})$ time.

###### Proof

Finding the cell containing $p$ in each grid $\Pi_{i}$ can be done in constant
time. If $Cell_{i}(p)$ contains points of $P$, then we change the parity of
the set containing $Cell_{i}(p)$ in $DSS_{i}$ in constant time. Otherwise,
making a new set in $DSS_{i}$ and merging it with at most eight sets in
$DSS_{i}$ that contain non-empty adjacent cells of $Cell_{i}(p)$ can be also
done in amortized constant time. Since
$c=\left\lceil{{\log\Delta}}\right\rceil$, Insert($p$) takes amortized
$O(\log{\Delta})$ time.

### Deletion

Let $p$ and $q$ be the two points deleted from $P$. We describe the procedure
for deleting $p$. The same procedure is applied for deleting $q$. Let
$Cell_{i}(p)$ be the cell containing $p$ in $\Pi_{i}$ and let $S_{i}(p)$ be
the set containing $Cell_{i}(p)$ in $DSS_{i}$. For each grid $\Pi_{i}$, we
change the parity of $S_{i}(p)$ in $DSS_{i}$. Then, we find the smallest $i$
such that, in $\Pi_{i}$, $Cell_{i}(p)$ contains no other points of $P$ than
$p$. If no such $\Pi_{i}$ exists, then we do not make any change. If all the
adjacent cells of $Cell_{i}(p)$ are empty, then we just remove $S_{i}(p)$ from
$DSS_{i}$. Otherwise, we check whether removing $Cell_{i}(p)$ disconnects the
component containing it. That is, we check whether there are two non-empty
adjacent cells of $Cell_{i}(p)$ that were in the same set $S_{i}(p)$ together
with $Cell_{i}(p)$ in $DSS_{i}$ and after removing $Cell_{i}(p)$ they should
be in different sets. If there are two such cells, then we remove the set
$S_{i}(p)$ from $DSS_{i}$ and reconstruct new sets for the cells in
$S_{i}(p)\setminus\\{Cell_{i}(p)\\}$.

###### Lemma 7

There is at most one grid $\Pi_{i}$, such that removing $Cell_{i}(p)$
disconnects the component containing it in $DSS_{i}$.

###### Proof

Assume by contradiction that there are two grids $\Pi_{i}$ and $\Pi_{j}$, such
that $i<j$ and removing $Cell_{i}(p)$ and $Cell_{j}(p)$ disconnect the
component containing it in $DSS_{i}$ and in $DSS_{j}$, respectively. Let
$\sigma_{1}$ and $\sigma_{2}$ be two non-empty adjacent cells of $Cell_{i}(p)$
in $\Pi_{i}$ that were in the same set $S_{i}(p)$ together with $Cell_{i}(p)$
in $DSS_{i}$. Notice that $\sigma_{1}$ and $\sigma_{2}$ are contained in the
$3\times 3$ cells-block around $Cell_{i}(p)$ in $\Pi_{i}$; see Figure 3.
Moreover, one of the corners of $Cell_{i}(p)$ is a grid-vertex in $\Pi_{i+1}$,
as depicted in Figure 3. Therefore, $\sigma_{1}$ and $\sigma_{2}$ are either
in the same cell or in adjacent cells in $\Pi_{i+1}$, and in $\Pi_{j}$, for
each $j\geq i+1$. This contradicts that $Cell_{j}(p)$ disconnects the
component containing it in $DSS_{j}$.

Figure 3: $\Pi_{i}$ (in black) and $\Pi_{i+1}$ (in red). The $3\times 3$
cells-block (in blue) around $Cell_{i}(p)$ in $\Pi_{i}$. One of the corners of
$Cell_{i}(p)$ is a grid-vertex in $\Pi_{i+1}$.

###### Lemma 8

Deleting $p$ from $P$ takes amortized $O(\log{\Delta}+|P|)$ time.

###### Proof

Changing the parity of $S_{i}(p)$ in $DSS_{i}$ can be done in constant time,
for each $1\leq i\leq c$. Finding the smallest $i$ such that $Cell_{i}(p)$
contains no other points of $P$ than $p$ takes $O(\log{\Delta})$ time. If all
the adjacent cells of $Cell_{i}(p)$ are empty, then we just remove $S_{i}(p)$
from $DSS_{i}$ in constant time. Otherwise, reconstruct new sets for the cells
in amortized $S_{i}(p)\setminus\\{Cell_{i}(p)\\}$ in $O(|S_{i}(p)|)=O(|P|)$
time. Since $c=\left\lceil{{\log\Delta}}\right\rceil$, Deleting $p$ from $P$
takes amortized $O(\log{\Delta}+|P|)$ time.

The following theorem summarizes the result of this section.

###### Theorem 4.2

Let $P$ be a set of points in the plane and let $\Delta$ be the geometric
spread of $P$. There exists a dynamic algorithm that maintains a
$(6\sqrt{2})$-approximate bottleneck matching of $P_{k}$, at each time step
$k$, and supports insertion in $O(\log{\Delta})$ amortized time and deletion
in $O(\log{\Delta}+|P_{k}|)$ amortized time.

## References

  * [1] A. Abboud and V. V. Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 434–443, 2014.
  * [2] A. K. Abu-Affash, S. Bhore, and P. Carmi.  Monochromatic plane matchings in bicolored point set.  Information Processing Letters, 153, 2020.
  * [3] A. K. Abu-Affash, A. Biniaz, P. Carmi, A. Maheshwari, and M. H. M. Smid.  Approximating the bottleneck plane perfect matching of a point set.  Computational Geometry, 48(9):718–731, 2015.
  * [4] A. K. Abu-Affash, P. Carmi, M. J. Katz, and Y. Trabelsi.  Bottleneck non-crossing matching in the plane.  Computational Geometry, 47(3):447–457, 2014.
  * [5] P. Agarwal, H.-C. Chang, S. Suri, A. Xiao, and J. Xue.  Dynamic geometric set cover and hitting set.  ACM Transactions on Algorithms, 18(4):1–37, 2022.
  * [6] P. K. Agarwal, H.-C. Chang, S. Raghvendra, and A. Xiao.  Deterministic, near-linear _$\epsilon$_ -approximation algorithm for geometric bipartite matching.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1052–1065, 2022.
  * [7] P. K. Agarwal, A. Efrat, and M. Sharir.  Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications.  SIAM Journal on Computing, 29(3):912–953, 2000.
  * [8] P. K. Agarwal and K. R. Varadarajan.  A near-linear constant-factor approximation for euclidean bipartite matching.  In Proceedings of the 20th ACM Symposium on Computational Geometry (SoCG), pages 247–252, 2004.
  * [9] S. Bhore, P. Bose, P. Cano, J. Cardinal, and J. Iacono.  Dynamic schnyder woods.  arXiv:2106.14451, 2021.
  * [10] S. Bhore, J. Cardinal, J. Iacono, and G. Koumoutsos.  Dynamic geometric independent set.  arXiv:2007.08643, 2020.
  * [11] S. Bhore, G. Li, and M. Nöllenburg.  An algorithmic study of fully dynamic independent sets for map labeling.  ACM Journal of Experimental Algorithmics, 27(1):1–36, 2022.
  * [12] T. M. Chan.  A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries.  Journal of the ACM, 57(3):1–15, 2010.
  * [13] M. S. Chang, C. Y. Tang, and R. C. T. Lee.  Solving the Euclidean bottleneck matching problem by $k$-relative neighborhood graphs.  Algorithmica, 8(1–6):177–194, 1992.
  * [14] H. Cho, E. K. Kim, and S. Kim.  Indoor SLAM application using geometric and ICP matching methods based on line features.  Robotics and Autonomous Systems, 100:206–224, 2018.
  * [15] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.  Chapter 21: Data structures for Disjoint Sets, Introduction to Algorithms, 3rd edition,.  The MIT Press, 2009.
  * [16] A. Efrat and M. J. Katz.  Computing euclidean bottleneck matchings in higher dimensions.  Information Processing Letters, 75(4):169–174, 2000.
  * [17] Harold N Gabow and Robert E Tarjan.  Algorithms for two bottleneck optimization problems.  Journal of Algorithms, 9(3):411–417, 1988.
  * [18] B. Gamlath, M. Kapralov, A. Maggiori, O. Svensson, and D. Wajc.  Online matching with general arrivals.  In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 26–37, 2019.
  * [19] M. Gupta and R. Peng.  Fully dynamic $(1+e)$-approximate matchings.  In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 548–557, 2013.
  * [20] R. M. Karp, U. V. Vazirani, and V. V. Vazirani.  An optimal algorithm for on-line bipartite matching.  In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358, 1990.
  * [21] M. J. Katz and M. Sharir.  Bottleneck matching in the plane.  arXiv:2205.05887, 2022.
  * [22] E. Koutsoupias and A. Nanavati.  The online matching problem on a line.  In International Workshop on Approximation and Online Algorithms, pages 179–191, 2003.
  * [23] O. Marcotte and S. Suri.  Fast matching algorithms for points on a polygon.  SIAM Journal on Computing, 20(3):405–422, 1991.
  * [24] S. Raghvendra.  Optimal analysis of an online algorithm for the bipartite matching problem on a line.  arXiv:1803.07206, 2018.
  * [25] S. Raghvendra and P. K. Agarwal.  A near-linear time $\epsilon$-approximation algorithm for geometric bipartite matching.  Journal of the ACM, 67(3):18:1–18:19, 2020.
  * [26] P. Sankowski.  Faster dynamic matchings and vertex connectivity.  In Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 118–126, 2007.
  * [27] S. Solomon.  Fully dynamic maximal matching in constant update time.  In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 325–334, 2016.
  * [28] R. E. Tarjan and J. van Leeuwen.  Worst-case analysis of set union algorithms.  Journal of the ACM, 31(2):245–281, 1984.
  * [29] P. M. Vaidya.  Geometry helps in matching.  SIAM Journal on Computing, 18(6):1201–1225, 1989.
  * [30] K. R. Varadarajan.  A divide-and-conquer algorithm for min-cost perfect matching in the plane.  In Proceedings 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 320–329, 1998.