# Fully Dynamic Geometric Vertex Cover and Matching

Sujoy Bhore Timothy M. Chan Department of Computer Science & Engineering,
Indian Institute of Technology Bombay, Mumbai, India.
Email<EMAIL_ADDRESS>of Computer Science, University of
Illinois at Urbana-Champaign. Email<EMAIL_ADDRESS>Work supported in part
by NSF Grant CCF-2224271.

###### Abstract

In this work, we study two fundamental graph optimization problems, minimum
vertex cover (MVC) and maximum-cardinality matching (MCM), for intersection
graphs of geometric objects, e.g., disks, rectangles, hypercubes, etc., in
$d$-dimensional Euclidean space. We consider the problems in fully dynamic
settings, allowing insertions and deletions of objects.

We develop a general framework for dynamic MVC in intersection graphs,
achieving sublinear amortized update time for most natural families of
geometric objects. In particular, we show that -

  * •

For a dynamic collection of disks in $\mathbb{R}^{2}$ or hypercubes in
$\mathbb{R}^{d}$ (for constant $d$), it is possible to maintain a
$(1+\varepsilon)$-approximate vertex cover in $\operatorname{polylog}$
amortized update time. These results also hold in the bipartite case.

  * •

For a dynamic collection of rectangles in $\mathbb{R}^{2}$, it is possible to
maintain a $(\frac{3}{2}+\varepsilon)$-approximate vertex cover in
$\operatorname{polylog}$ amortized update time.

Along the way, we obtain the first near-linear time static algorithms for MVC
in the above two cases with the same approximation factors.

Next, we turn our attention to the MCM problem. Although our MVC algorithms
automatically allow us to approximate the size of the MCM in bipartite
geometric intersection graphs, they do not produce a matching. We give another
general framework to maintain an approximate maximum matching, and further
extend the approach to handle non-bipartite intersection graphs. In
particular, we show that -

  * •

For a dynamic collection of (bichromatic or monochromatic) disks in
$\mathbb{R}^{2}$ or hypercubes in $\mathbb{R}^{d}$ (for constant $d$), it is
possible to maintain a $(1+\varepsilon)$-approximate matching in
$\operatorname{polylog}$ amortized update time.

##  1 Introduction

Dynamic geometric algorithms form a vital area of research in Computational
Geometry. In dynamic settings, the input is subject to discrete changes over
time, that is, insertions and deletions of geometric objects. Over the years,
dynamic algorithms have been developed for a variety of geometric problems,
including convex hull [OvL81, Cha01, BJ02, Cha10, Cha20b], closest/farthest
pair [Epp95, Cha20a], connectivity [Cha06, AC09, CPR11, KKK+22], width and
other measures [Cha01, Cha03b, Cha20b], coresets [Cha09], and many others.
More recently, much attention has turned towards NP-hard geometric
optimization problems—building dynamic data structures that can maintain
solutions for an optimization task at hand, in truly sublinear update time.
Since it is only possible to maintain some approximate solution for an NP-hard
problem, the broad goal is to explore the trade-offs between update time and
approximation ratio. Optimization problems that are solvable in polynomial
time but do not have subquadratic exact algorithms may also benefit from
allowing approximation. Several fundamental geometric optimization problems
have been studied in dynamic settings over the last few years, for instance,
set cover [ACS+22, CH21, CHSX22, KLR+23], piercing or hitting set [ACS+22,
AHRS24], and independent set [BCIK21, HNW20, BLN22, BNTW23].

In this work, we focus on two other fundamental optimization problems: minimum
vertex cover (MVC) and maximum-cardinality matching (MCM). Let $G=(V,E)$ be an
undirected graph. A subset of vertices $S\subseteq V$ is a vertex cover if
each edge has at least one endpoint in $S$. An MVC refers to a vertex cover
with the minimum cardinality. A simple algorithm that greedily computes a
maximal matching111A matching in an input graph $G$ is a subset of edges
$M\subseteq E$ such that no two edges in $M$ share a common endpoint. A
matching $M$ is maximal if for every edge $(u,v)\in E\setminus M$, either $u$
or $v$ is matched in $M$. and outputs its vertices gives a $2$-approximation
for MVC. This is likely to be the best possible for general graphs, as the
problem is hard to approximate within factor $2-o(1)$ under the unique games
conjecture [KR08].

MVC stands out as one of the most important problems, due to its connection to
other fundamental problems. For example, in the exact setting, the maximum
independent set (MIS) problem is equivalent to MVC, as the complement of an
MIS is an MVC. However, from the approximation perspective, a sharp dichotomy
exists between these problems; for instance, MIS on general graphs is much
harder to approximate222No polynomial time algorithm can achieve an
approximation factor $n^{1-\varepsilon}$, unless $\textsf{P}=\textsf{ZPP}$
[Zuc07]. Throughout this paper, $\varepsilon$ denotes an arbitrarily small
positive constant.. Another closely related classical optimization on graphs
is MCM, where the objective is to find a matching with the largest number of
edges. The size of an MVC is obviously at least as large as the size of an
MCM; for bipartite graphs, they are well-known to be equal. MCM is polynomial-
time solvable: the classical algorithm by Hopcroft and Karp [HK73] runs in
$O(m\sqrt{n})$ time for bipartite graphs with $n$ vertices and $m$ edges, and
Vazirani’s algorithm [Vaz94] achieves the same run time for general graphs. By
recent breakthrough results [CKL+22], MCM can be solved in $m^{1+o(1)}$ time
for bipartite graphs. Earlier, Duan and Pettie [DP10] obtained $O(m)$-time
$(1+\varepsilon)$-approximation algorithms for general graphs.

#### Geometric MVC & MCM.

We focus on the intersection graph of a collection
$\mathcal{L}=\\{\ell_{1},\ldots,\ell_{n}\\}$ of geometric objects in
$d$-dimensional Euclidean space $\mathbb{R}^{d}$ (for $d$ constant). In the
intersection graph $G_{\mathcal{L}}=(V_{\mathcal{L}},E_{\mathcal{L}})$ of
$\mathcal{L}$, each object $\ell_{i}\in\mathcal{L}$ is represented by a vertex
$v_{i}\in V_{\mathcal{L}}$, and any pair of intersecting objects
$\ell_{i},\ell_{j}\in\mathcal{L}$ corresponds to an edge $(v_{i},v_{j})\in
E_{\mathcal{L}}$. A wide range of optimization problems have been studied over
the years for various families of geometric intersection graphs, and better
results are often possible in such geometric graphs. Concerning MVC, the
problem remains NP-hard, even for intersection graphs of unit disks [CCJ90],
but there exist PTASs for intersection graphs of disks, squares, or other
“fat” objects in any constant dimension [EJS05]. For rectangles333All
rectangles and boxes are axis-aligned by default in this paper. in the plane,
Bar-Yehuda, Hermelin, and Rawitz [BYHR11] obtained a
$(\frac{3}{2}+\varepsilon)$-approximation algorithm. Bar-Yehuda et al.’s work
made use of Nemhauser and Trotter’s standard LP-based kernelization for vertex
cover [NTJ75], which allows us to approximate the MVC by flipping to an MIS
instance. Following the same kernelization approach, Har-Peled [Har23] noted
that by using the known QQPTAS444We refer to a $(1+\varepsilon)$-approximation
algorithm with running time of the form $n^{O(\operatorname{polylog}n)}$ or
$n^{O(\operatorname{poly}(\log\log n))}$, for any fixed $\varepsilon>0$, as a
QPTAS or QQPTAS respectively. for MIS for rectangles [CE16], one can
immediately obtain a QQPTAS for MVC for rectangles. Similarly, by using the
known QPTAS for MIS for polygons in the plane [AHW19], one can obtain a QPTAS
for MVC for polygons.

MCM on geometric intersection graphs has also been studied. Efrat, Itai, and
Katz [EIK01] showed how to compute the maximum matching in bipartite unit disk
graphs in $O(n^{3/2}\log n)$ time. Their algorithm works for other geometric
objects; for example, it runs in $O(n^{3/2}\operatorname{polylog}n)$ time for
bipartite intersection graphs of arbitrary disks, by using known dynamic data
structures for disk intersection searching [KKK+22]. Bonnet, Cabello, and
Mulzer [BCM23] improved the running time to $O(n^{\omega/2})$ for certain
cases, e.g., translates of a convex object, or geometric objects with low
“density”, where $\omega<2.38$ is the matrix multiplication exponent.
Recently, Har-Peled and Yang [HY22] presented near-linear time
$(1+\varepsilon)$-approximation algorithms for MCM in (bipartite or non-
bipartite) intersection graphs of arbitrary disks, among other things.

#### Dynamic geometric MVC & MCM.

In this paper, we are interested in the dynamic version of MVC and MCM
problems, for geometric intersection graphs, subject to insertions and
deletions of objects in $\mathcal{L}$. The goal is to obtain a data structure
that can efficiently maintain an approximate MVC or MCM in $G_{\mathcal{L}}$
at any point in time, with truly sublinear update times for both insertions
and deletions.

######  Problem 1.

Given a dynamic collection of geometric objects in $\mathbb{R}^{d}$, is it
possible to maintain a $(1+\varepsilon)$-approximate MVC in truly sublinear
update time?

######  Problem 2.

Given a dynamic collection of geometric objects in $\mathbb{R}^{d}$, is it
possible to maintain a $(1+\varepsilon)$-approximate MCM in truly sublinear
update time?

Dynamic MVC & MCM are well-studied problems in the dynamic graph algorithms
literature, under edge updates; see [OR10, GP13, BS15, BS16, PS16, Sol16,
BHI18, BK19, Beh23, BKSW23, ABR24] for a non-exhaustive list. However, none of
these results particularly apply to our scenario, since the insertion/deletion
of a single object corresponds to a vertex update, which may require many edge
updates. A natural barrier for designing dynamic graph algorithms under vertex
updates is the maximum degree of the input graph, which may be $\Omega(n)$.
For geometric intersection graphs, however, the challenge is to break such
barriers by not explicitly maintaining the graph itself, which may have
$m=\Omega(n^{2})$ size in the worst case.

Although geometric versions of dynamic set cover, dynamic hitting set, and
dynamic independent set have received much attention recently (as we have
mentioned), we are not aware of any prior work on dynamic geometric vertex
cover or dynamic geometric matching.

For unit disks in the plane, or more generally, fat objects of roughly the
same size in $\mathbb{R}^{d}$ (for constant $d$), it is not difficult to
maintain a $(1+\varepsilon)$-approximate MVC in constant update time, by using
the standard shifted-grid technique [HM85]. Moreover, this technique extends
to maintain a $(1+\varepsilon)$-approximate non-bipartite MCM in constant
update time (see also [HY22] in the static setting). However, the problems
become much more challenging for more general families of objects, such as
disks of arbitrary radii, or arbitrary (non-fat) rectangles.

In this work, we resolve Problems 1 and 2 in an affirmative sense for many
types of geometric objects:

#### Our contributions to MVC.

We develop a general framework for dynamic geometric MVC (Theorem 1), which
implies all the specific results listed in Table 1.

Objects | Approx. Ratio | Amortized update time | Reference
---|---|---|---
Disks in $\mathbb{R}^{2}$ | $1+\varepsilon$ | $O(2^{O(1/\varepsilon^{2})}\log^{O(1)}n)$ | Corollary 1
Rectangles in $\mathbb{R}^{2}$ | $\frac{3}{2}+\varepsilon$ | $O(2^{O(1/\varepsilon^{2})}\log^{O(1)}n)$ | Corollary 2
Fat boxes in $\mathbb{R}^{d}$ | $1+\varepsilon$ | $O(2^{O(1/\varepsilon^{d})}\log^{O(1)}n)$ | Corollary 3
Bipartite disks in $\mathbb{R}^{2}$ | $1+\varepsilon$ | $O((1/\varepsilon^{7})\log^{O(1)}n)$ | Corollary 4
Bipartite boxes (non-fat) in $\mathbb{R}^{d}$ | $1+\varepsilon$ | $O((1/\varepsilon^{7})\log^{O(1)}n)$ | Corollary 5
Table 1: Summary of results on dynamic MVC for intersection graphs of
geometric objects.

These results on geometric vertex cover are notable when compared against
recent results on related dynamic geometric problems such as set cover and
independent set:

  * •

The _polylogarithmic_ update times in Table 1 are significantly better than
known results for dynamic geometric set cover. For example, even for the
simple case of squares in $\mathbb{R}^{2}$, the best update time for set cover
was near $\sqrt{n}$ [CHSX22]; for the case of disks in $\mathbb{R}^{2}$, the
best update time was near $n^{12/13}$ [CH21] (and was only for maintaining the
approximate size but not a cover).

  * •

Many of the results in Table 1 achieve the _ideal approximation ratio_ ,
namely, $1+\varepsilon$. In contrast, previous dynamic algorithms for
geometric set cover [CH21, CHSX22] were all in the regime of $O(1)$
approximation ratio. Similarly, for dynamic geometric MIS, recent algorithms
for squares or hypercubes [HNW20] and disks [BNTW23] all achieved $O(1)$
approximation only.

  * •

Our framework is _general_ and applicable to more types of objects. Though not
stated in the table, we can handle any class of semialgebraic objects with
constant description complexity in sublinear time with approximation ratio
$2+\varepsilon$ (or $1+\varepsilon$ in the bipartite cases). In contrast, the
known results for dynamic geometric set cover [CH21, CHSX22] were limited to
certain specific types of objects; for example, they did not extend to balls
in $\mathbb{R}^{3}$ or rectangles in $\mathbb{R}^{2}$. There were no
nontrivial results for dynamic MIS for rectangles with constant approximation
ratio.

A prerequisite to a $(1+\varepsilon)$-approximate dynamic algorithm with
polylogarithmic update time is the existence of a near-linear-time _static_
algorithm. MIS for disks (or fat objects) admits static PTASs [EJS05, Cha03a],
but not an EPTAS555An EPTAS refers to a PTAS with running time $O(n^{c})$ for
a constant $c$ independent of $\varepsilon$. under standard hypotheses in
parameterized complexity [Mar05]; similarly, set cover for disks admits static
PTASs [MR10] but not an EPTAS [Mar05]. In contrast, an EPTAS for MVC for disks
(or fat objects) can be obtained by known techniques using the aforementioned
Nemhauser–Trotter kernel [NTJ75]. This explains why in some sense, geometric
vertex cover is actually a better problem to study in dynamic settings than
geometric independent set or geometric set cover.

However, a static EPTAS for MVC for disks (or fat objects) that runs in _near
linear time_ has not been explicitly given before, to the best of our
knowledge. Similarly, the static $(\frac{3}{2}+\varepsilon)$-approximation
algorithm for MVC for rectangles by Bar-Yehuda, Heremelin, and Rawitz [BYHR11]
runs in polynomial time but not in near linear time. In deriving our dynamic
results, we obtain the first static near-linear-time algorithms in these
cases, which may be of independent interest.

#### Our contributions to MCM.

Next, we focus on MCM. Our approximation algorithms for MVC in bipartite
geometric intersection graphs allows us to automatically approximate the size
of the MCM in such bipartite graphs. However, it does not compute a matching.
We develop another general framework for dynamic geometric MCM (Theorem 2),
and further extend it to non-bipartite intersection graphs. The framework
implies the specific results in Table 2:

Objects | Approx. Ratio | Amortized update time | Reference
---|---|---|---
Bipartite disks in $\mathbb{R}^{2}$ | $1+\varepsilon$ | $O((1/\varepsilon^{3})\log^{O(1)}n)$ | Corollary 6
Bipartite boxes in $\mathbb{R}^{d}$ | $1+\varepsilon$ | $O((1/\varepsilon^{3})\log^{O(1)}n)$ | Corollary 7
Disks in $\mathbb{R}^{2}$ | $1+\varepsilon$ | $O(2^{O(1/\varepsilon)}\log^{O(1)}n)$ | Corollary 8
Boxes in $\mathbb{R}^{d}$ | $1+\varepsilon$ | $O(2^{O(1/\varepsilon)}\log^{O(1)}n)$ | Corollary 9
Table 2: Summary of results on dynamic MCM for intersection graphs of
geometric objects.

In particular, we succeed in efficiently dynamizing the known static near-
linear-time $(1+\varepsilon)$-approximation MCM algorithms for (bipartite or
non-bipartite) disks by Har-Peled and Yang [HY22].

#### Our framework and techniques for MVC.

Our framework for MVC has only 2 requirements on the geometric object family:

  1. (i)

the existence of an efficient data structure for _dynamic intersection
detection_ (maintaining a set of input objects under insertions and deletions
so that we can quickly decide whether a query object intersects any of the
input objects), and

  2. (ii)

the existence of an efficient _static approximation algorithm_.

If the data structure in (i) takes polylogarithmic query and update time and
the algorithm in (ii) takes near linear time ignoring polylogarithmic factors,
then the resulting dynamic algorithm achieves polylogarithmic (amortized)
update time, and its approximation ratio is the same as the static algorithm,
up to $1+\varepsilon$ factors.

In some sense, the framework is as general as possible: Requirement (ii) is an
obvious prerequisite (as we have already noted); in fact, we only require a
static algorithm for the case when the optimal value is promised to be at
least $n/2$ roughly. Requirement (i) is also natural, as some kind of
geometric range searching data structures is provably necessary. For example,
consider the case of disks in $\mathbb{R}^{2}$. Any dynamic approximate MVC
algorithm needs to recognize whether the MVC size is zero, and so must know
whether the intersection graph is empty. Dynamic disk range emptiness
(maintaining a set of input points under insertions and deletions so that we
can quickly decide whether a query disk contains any of the input points) can
be reduced to this problem, by inserting all the input points, and repeatedly
inserting a query disk and deleting it. (This explains why for our result on
disks, we need multiple logarithmic factors in the update time, since the best
algorithm for dynamic disk range emptiness requires multiple logarithmic
factors [Cha10], although the current best algorithm for dynamic disk
intersection detection requires still more logarithmic factors [KKK+22].)

Our framework for MVC is established by combining a number of ideas. The
initial idea is a standard one: _periodic rebuilding_. The intuition is that
when the optimal value is large, we can afford to do nothing for a long period
of time, without hurting the approximation ratio by much. This idea has been
used before in a number of recent works on dynamic geometric independent set
(e.g., [CIK21]), dynamic piercing (e.g., [AHRS24]), and dynamic graph
algorithms (e.g., [GP13]), although the general approach of periodic
rebuilding is commonplace and appeared in much earlier works in dynamic
computational geometry (e.g., [Cha01, Cha03b]).

The main challenge now lies in the case when the optimal value OPT is small.
Our idea is to compute Nemhauser and Trotter’s standard LP-based kernel for
MVC, and then run a static algorithm on the kernel. Unfortunately, we are
unable to solve the LP exactly in sublinear time. However, by using the
_multiplicative weight update_ (MWU) method, we show that it is possible to
solve the LP approximately in time roughly linear in OPT (and thus sublinear
in $n$ in the small OPT case), by using the intersection detection data
structure provided by (i). We further show that an approximate solution to the
LP is still sufficient to yield a kernel with approximately the same size. The
idea of using MWU in the design of dynamic geometric algorithms was pioneered
in Chan and He’s recent work on dynamic geometric set cover [CH21], and also
appeared in subsequent work on dynamic piercing [AHRS24]; however, these works
solved the LP in time superlinear in OPT, which is why their final update time
bounds were significantly worse.

In geometric approximation algorithms, the best-known application of MWU is
geometric set cover or hitting set [BG95]. Our work highlights its usefulness
also to geometric vertex cover—ironically, the application to vertex cover is
even simpler (and so our work might have additional pedagogical value).
Furthermore, the efficient implementation of MWU for dynamic geometric vertex
cover turns out to lead to a nice, unexpected application of another known
technique: namely, Eppstein’s data structure technique for _generalized
dynamic closest pair_ problems [Epp95] (see also [Cha20a]).

#### Our framework and techniques for MCM.

For MCM, our framework only needs requirement (i). Here, we need different
ideas, since kernels for matching do not seem to work as efficiently. In the
bipartite case, we use an approach based on Hopcroft and Karp’s classical
matching algorithm [HK73], which is known to yield good approximation after a
constant number of iterations. We show how to implement the approximate
version of Hopcroft and Karp’s algorithm in time roughly linear in OPT, by
using the data structure from (i). Previously, Efrat, Itai, and Katz [EIK01]
showed how to implement Hopcroft and Karp’s algorithm faster using geometric
data structures, but their focus was on static algorithms whereas our goal is
in getting sublinear time. Thus, our adaptation of Hopcroft–Karp will be a
little more delicate.

In the general non-bipartite case, we apply a technique by Lotker, Patt-
Shamir, and Pettie [LPP15]. which reduces non-bipartite to the bipartite case
in the approximate setting. Har-Peled and Yang [HY22] also applied the same
technique to derive their static approximation algorithms for geometric non-
bipartite MCM. We reinterpret this technique in terms of _color-coding_
[AYZ95], which allows for efficient derandomization and dynamization, as well
as a simpler analysis.

##  2 Minimum Vertex Cover

In this section, we study the MVC problem for dynamic intersection graphs of
geometric objects.

###  2.1 Approximating the LP via MWU

For a graph $G=(V,E)$, a _fractional vertex cover_ is a vector $(x_{v})_{v\in
V}$ such that $x_{u}+x_{v}\leq 1$ for all $uv\in E$ and $x_{v}\in[0,1]$ for
all $v\in V$. Its _size_ is defined as $\sum_{v\in V}x_{v}$. Finding a
minimum-size fractional vertex cover corresponds to solving an LP, namely, the
standard LP relaxation of the MVC problem.

It is known that this LP is equivalent to computing the MVC in a related
bipartite graph, and thus can be solved exactly by known bipartite MCM
algorithms—in fact, in time almost linear in the number of edges by recent
breakthrough results [CKL+22]. However, there are two issues that prevent us
from applying such algorithms. First of all, we are considering geometric
intersection graphs, which may have $\Omega(n^{2})$ number of edges; this
issue could potentially be fixed by using known techniques involving _biclique
covers_ to sparsify the graph (maximum matching in a bipartite graph then
reduces to maximum flow in a sparser 3-layer graph [FM95]). Second, we want
efficient data structures that can solve the LP still faster, in _sublinear_
time when OPT is small.

For our purposes, we only need to solve the LP approximately. Our idea is to
use a different well-known technique: _multiplicative weight update_ (MWU).
The key lemma is stated below. The MWU algorithm and analysis here are nothing
new (the description is short enough that we opt to include it to be self-
contained), and such algorithms have been used before for static and dynamic
geometric set cover and other geometric optimization problems (the application
to vertex cover turns out to be a little simpler). However, our contribution
is not in the proof of the lemma, but in the realization that MWU reduces the
problem to designing a dynamic data structure (for finding min-weight edges
subject to vertex-weight updates), which geometric intersection graphs happen
to possess, as we will see.

######  Lemma 1.

We are given a graph $G=(V,E)$. Suppose there is a data structure
$\mathcal{DS}$ for storing a vector $(w_{v})_{v\in V}$ that can support the
following two operations in $\tau$ time: (i) find an edge $uv\in E$ minimizing
$w_{u}+w_{v}$, and (ii) update a number $w_{v}$.

Given a data structure $\mathcal{DS}$ for the vector that currently has
$w_{v}=1$ for all $v\in V$, we can compute a $(1+O(\delta))$-approximation to
the minimum fractional vertex cover in
$\widetilde{O}((1/\delta^{2})\,\mbox{\rm OPT}\cdot\tau)$ time. Here, OPT
denotes the minimum vertex cover size.

###### Proof.

Given a number $z$, the following algorithm attempts to find a fractional
vertex cover of size at most $z$ (below, $W$ denotes $\sum_{v\in V}w_{v}$):

> let $w_{v}=1$ for all $v\in V$, and $W=n$
> ---
> while there exists $uv\in E$ with $w_{u}+w_{v}<W/z$ do
> | let $uv$ be such an edge
> |  $W\leftarrow W+\delta(w_{u}+w_{v})$, $w_{u}\leftarrow(1+\delta)w_{u}$, $w_{v}\leftarrow(1+\delta)w_{v}$

If and when the algorithm terminates, we have $w_{u}+w_{v}\geq W/z$ for all
$uv\in E$. Thus, defining $x_{v}:=\min\\{zw_{v}/W,\,1\\}$, we have
$x_{u}+x_{v}\geq 1$ for all $uv\in E$, and $\sum_{v\in V}x_{v}\leq z$, i.e.,
$(x_{v})_{v\in V}$ is a fractional vertex cover of size at most $z$.

We now bound the number of iterations $t$. In each iteration, $W$ increases by
at most a factor of $1+\delta/z$. Thus, at the end,

$W\leq(1+\delta/z)^{t}n.$

Write each $w_{v}$ as $(1+\delta)^{c_{v}}$ for some integer $c_{v}$. Let
$(x_{v}^{*})_{v\in V}$ be an optimal fractional vertex cover of size $z^{*}$.
In each iteration, $\sum_{v\in V}c_{v}x_{v}^{*}$ increases by at least 1
(since we increment $c_{u}$ and $c_{v}$ for the chosen edge $uv$, and we know
$x_{u}^{*}+x_{v}^{*}\geq 1$). Thus, at the end, $\sum_{v\in
V}c_{v}x_{v}^{*}\geq t$. Since $\sum_{v\in V}x_{v}^{*}=z^{*}$, it follows that
$\max_{v\in V}c_{v}\geq t/z^{*}$. Thus,

$W\geq(1+\delta)^{t/z^{*}}.$

Therefore, $(1+\delta)^{t/z^{*}}\leq(1+\delta/z)^{t}n\leq e^{\delta t/z}n$,
implying $(t/z^{*})\ln(1+\delta)\leq\delta t/z+\ln n$. So, if
$z\geq(1+\delta)z^{*}$, then $t\leq\frac{z^{*}\ln
n}{\ln(1+\delta)-\delta/(1+\delta)}=O((1/\delta^{2})z^{*}\log n)$.

Note that only $O(t)=O((1/\delta^{2})z^{*}\log n)$ of the numbers $w_{v}$ are
not equal to 1, so the vector $(x_{v})_{v\in V}$ can be encoded in
$\widetilde{O}(z^{*})$ space.

We can try different $z$ values by binary or exponential search till the
algorithm terminates in $O((1/\delta^{2})z^{*}\log n)$ iterations. Each run
can be implemented with $O((1/\delta^{2})z^{*}\log n)$ operations in
$\mathcal{DS}$. After each run, we reset all the modified values $w_{v}$ back
to 1 by $O((1/\delta^{2})z^{*}\log n)$ update operations in $\mathcal{DS}$. ∎

###  2.2 Kernel via Approximate LP

Our approach for solving the vertex cover problem is to use a standard
_kernel_ by Nemhauser and Trotter [NTJ75], which allows us to reduce the
problem to an instance where the number of vertices is at most $2\,\mbox{\rm
OPT}$. Nemhauser and Trotter’s construction is obtained from the LP solution:
the kernel is simply the subset of all vertices $v\in V$ with
$x_{v}=\frac{1}{2}$.

In our scenario, we are only able to solve the LP approximately. We observe
that this is still enough to give a kernel of approximately the same size. We
adapt the standard analysis of Nemhauser and Trotter, but some extra ideas are
needed. The proof below will be self-contained.

######  Lemma 2.

Let $c\geq 1$ and $0\leq\delta<\gamma<\frac{1}{4}$. Given a
$(1+O(\delta))$-approximation to the minimum fractional vertex cover in a
graph $G=(V,E)$, we can compute a subset $K\subseteq V$ of size at most
$(2+O(\gamma))\,\mbox{\rm OPT}$, in $O(\mbox{\rm OPT})$ time, such that a
$c(1+O(\sqrt{\delta/\gamma}))$-approximation to the minimum vertex cover of
$G$ can be obtained from a $c$-approximation to the minimum vertex cover of
$G[K]$ (the subgraph of $G$ induced by $K$). Here, OPT denotes the minimum
vertex cover size of $G$.

###### Proof.

Let $(x_{v})_{v\in V}$ be the given fractional vertex cover. Let
$\lambda<\gamma$ be a parameter to be set later. Pick a value
$\alpha\in[\frac{1}{2}-\gamma-\lambda,\frac{1}{2}-\lambda]$ which is an
integer multiple of $\lambda$, minimizing $|\\{v\in V:\alpha\leq
x_{v}<\alpha+\lambda\\}|$. This can be found in $O(|\\{v\in
V:x_{v}\geq\frac{1}{2}-\gamma-\lambda\\}|)\leq O(\mbox{\rm OPT})$ time.666
This assumes an appropriate encoding of the vector $(x_{v})_{v\in V}$, for
example, the encoding from the proof of Lemma 1.

Partition $V$ into 3 subsets: $L=\\{v\in V:x_{v}<\alpha\\}$, $H=\\{v\in
V:x_{v}>1-\alpha\\}$, and $K=\\{v\in V:\alpha\leq x_{v}\leq 1-\alpha\\}$. Note
that $|K|\leq\frac{1}{\alpha}\sum_{v\in
V}x_{v}\leq(2+O(\gamma))(1+\delta)\mbox{\rm OPT}=(2+O(\gamma))\mbox{\rm OPT}$.

Let $S_{K}$ be a $c$-approximate minimum vertex cover of $G[K]$. We claim that
$S:=S_{K}\cup H$ is a $c(1+O(\sqrt{\delta/\gamma}))$-approximation to the
minimum vertex cover of $G$.

First, $S_{K}\cup H$ is a vertex cover of $G$, since vertices in $L$ can only
be adjacent to vertices in $H$.

Let $S^{*}$ be a minimum vertex cover of $G$, with $|S^{*}|=\mbox{\rm OPT}$.
Since $K\cap S^{*}$ is a vertex cover of $G[K]$, we have $|S_{K}|\leq c|K\cap
S^{*}|$, and so $|S|\leq c(|K\cap S^{*}|+|H|)=c(|S^{*}|+|H\setminus
S^{*}|-|L\cap S^{*}|)$.

We will upper-bound $|H\setminus S^{*}|-|L\cap S^{*}|$. To this end, let
$L^{\prime}=\\{v\in V:\alpha\leq x_{v}<\alpha+\lambda\\}$, and define the
following modified vector $(x_{v}^{\prime})_{v\in V}$:

$x^{\prime}_{v}=\left\\{\begin{array}[]{ll}x_{v}-\lambda&\mbox{if $v\in
H\setminus S^{*}$}\\\ x_{v}+\lambda&\mbox{if $v\in(L\cup L^{\prime})\cap
S^{*}$}\\\ x_{v}&\mbox{otherwise.}\end{array}\right.$

Note that $(x^{\prime}_{v})_{v\in V}$ is still a fractional vertex cover,
since for each edge $uv\in E$ with $u\in H\setminus S^{*}$ and $v\in(L\cup
L^{\prime})\cap S^{*}$, we have
$x^{\prime}_{u}+x^{\prime}_{v}=(x_{u}-\lambda)+(x_{v}+\lambda)\geq 1$; on the
other hand, for each edge $uv\in E$ with $u\in H\setminus S^{*}$ and
$v\not\in(L\cup L^{\prime})\cap S^{*}$, we have $v\in S^{*}$ (since $S^{*}$ is
a vertex cover) and so $v\not\in L\cup L^{\prime}$, implying that
$x^{\prime}_{u}+x^{\prime}_{v}\geq(1-\alpha-\lambda)+(\alpha+\lambda)\geq 1$.
Now, $\sum_{v\in V}x_{v}-\sum_{v\in V}x^{\prime}_{v}=\lambda(|H\setminus
S^{*}|-|L\cap S^{*}|-|L^{\prime}\cap S^{*}|)$. On the other hand, $\sum_{v\in
V}x_{v}-\sum_{v\in V}x^{\prime}_{v}\leq(1-\frac{1}{1+O(\delta)})\sum_{v\in
V}x_{v}\leq O(\delta)|S^{*}|$. It follows that $|H\setminus S^{*}|-|L\cap
S^{*}|\leq O(\frac{\delta}{\lambda})|S^{*}|+|L^{\prime}\cap S^{*}|$.

By our choice of $\alpha$, we have $|L^{\prime}|\leq
O(\frac{1}{\gamma/\lambda})\cdot|\\{v\in
V:x_{v}\geq\frac{1}{2}-\gamma-\lambda\\}|\leq
O(\frac{\lambda}{\gamma})|S^{*}|$. We conclude that $|S|\leq
c(|S^{*}|+|H\setminus S^{*}|-|L\cap S^{*}|)\leq
c(1+O(\frac{\delta}{\lambda}+\frac{\lambda}{\gamma}))|S^{*}|$. Choose
$\lambda=\sqrt{\gamma\delta}$. ∎

###  2.3 Dynamic Geometric Vertex Cover via Kernels

We now use kernels to reduce the dynamic vertex cover for geometric
intersection graphs to a special case of static vertex cover where the number
of objects is approximately at most $2\,\mbox{\rm OPT}$. We use a simple,
standard idea for dynamization: be lazy, and periodically recompute the
solution only after every $\varepsilon\,\mbox{\rm OPT}$ updates (since the
optimal size changes by at most 1 per update). We observe that the data
structure subproblem of dynamic min-weight intersecting pair, needed in Lemma
1, is reducible to dynamic intersection detection by known techniques.

######  Lemma 3.

Let $\mathcal{C}$ be a class of geometric objects, where there is a dynamic
data structure $\mathcal{DS}_{0}$ for $n$ objects in $\mathcal{C}$ that can
detect whether there is an object intersecting a query object, and supports
insertions and deletions of objects, with $O(\tau_{0}(n))$ query and update
time.

Then there is a dynamic data structure $\mathcal{DS}$ for $n$ weighted objects
in $\mathcal{C}$ that maintains an intersecting pair of objects minimizing the
sum of the weights, under insertions and deletions of weighted objects, with
$\widetilde{O}(\tau_{0}(n))$ amortized time.

###### Proof.

Eppstein [Epp95] gave a general technique to reduce the problem of dynamic
closest pair to the problem of dynamic nearest neighbor search, for arbitrary
distance functions, while increasing the time per operation by at most two
logarithmic factors (with amortization). Chan [Cha20a] gave an alternative
method to achieve a similar result. The $\mathcal{DS}$ problem can be viewed
as a dynamic closest pair problem, where the distance between objects $u$ and
$v$ is $w_{u}+w_{v}$ if they intersect, and $\infty$ otherwise. Thus, our
problem reduces to designing a data structure that can find a min-weight
object intersecting a query object, subject to insertions and deletions of
objects (_dynamic min-weight intersection searching_).

We can further reduce this to the $\mathcal{DS}_{0}$ problem (_dynamic
intersection detection_) by a standard _multi-level_ data structuring
technique [AE99], where the primary data structure is a 1D search tree over
the weights, and each node of the tree stores a secondary data structure for
dynamic intersection detection. Query and update time increase by one more
logarithmic factor. ∎

######  Theorem 1.

Let $c\geq 1$, $\varepsilon>0$, and $0\leq\delta<\gamma<\frac{1}{4}$. Let
$\mathcal{C}$ be a class of geometric objects with the following oracles:

  1. (i)

a dynamic data structure $\mathcal{DS}_{0}$ for $n$ objects in $\mathcal{C}$
that can detect whether there is an object intersecting a query object, and
supports insertions and deletions of objects, with $O(\tau_{0}(n))$ query and
update time;

  2. (ii)

a static algorithm $\mathcal{A}$ for computing a $c$-approximation of the
minimum vertex cover of the intersection graph of $n$ objects in $\mathcal{C}$
in $T(n)$ time, under the promise that $n\leq(2+O(\gamma))\,\mbox{\rm OPT}$,
where OPT is the optimal vertex cover size.

Then there is a dynamic data structure for $n$ objects in $\mathcal{C}$ that
maintains a $c(1+O(\sqrt{\delta/\gamma}+\varepsilon))$-approximation of the
minimum vertex cover of the intersection graph, under insertions and deletions
of objects, in
$\widetilde{O}((1/(\delta^{2}\varepsilon))\tau_{0}(n)+(1/\varepsilon)T(n)/n)$
amortized time, assuming that $T(n)/n$ is monotonically increasing and
$T(2n)=O(T(n))$.

###### Proof.

Assume that $b\leq\mbox{\rm OPT}<2b$ for a given parameter $b$. Divide into
phases with $\varepsilon b$ updates each. At the beginning of each phase:

  1. 1.

Compute a $(1+\delta)$-approximation to the minimum fractional vertex cover by
Lemma 1 in $\widetilde{O}((1/\delta^{2})b\cdot\tau_{0}(n))$ amortized time
using the data structure $\mathcal{DS}$ from Lemma 3. (A weight change can be
done by a deletion and an insertion. It is important to note that we don’t
rebuild $\mathcal{DS}$ at the beginning of each phase; we continue using the
same structure $\mathcal{DS}$ in the next phase, after resetting the modified
weights back to 1.)

  2. 2.

Generate a kernel $K$ with size at most $(2+O(\gamma))\,\mbox{\rm OPT}$ by
Lemma 2 in $O(b)$ time.

  3. 3.

Compute a $c$-approximation to the minimum vertex cover of the intersection
graph of $K$ by the static algorithm $\mathcal{A}$ in
$O(T((2+O(\gamma))\,\mbox{\rm OPT}))=O(T(b))$ time, from which we obtain a
$c(1+O(\sqrt{\delta/\gamma}))$-approximation of the minimum vertex cover of
the entire intersection graph.

Since the above is done only at the beginning of each phase, the amortized
cost per update is
$\widetilde{O}(\frac{(1/\delta^{2})b\cdot\tau_{0}(n)+T(b)}{\varepsilon b})$.

During a phase, we handle an object insertion simply by inserting it to the
current cover, and we handle an object deletion simply by removing it from the
current cover. This incurs an additive error at most $O(\varepsilon
b)=O(\varepsilon\,\mbox{\rm OPT})$. We also perform the insertion/deletion of
the object in $\mathcal{DS}$, with initial weight 1, in
$\widetilde{O}(\tau_{0}(n))$ amortized time.

How do we obtain a correct guess $b$? We build the above data structure for
each $b$ that is a power of 2, and run the algorithm simultaneously for each
$b$ (with appropriate cap on the run time based on $b$). ∎

###  2.4 Specific Results

We now apply our framework to solve the dynamic geometric vertex cover problem
for various specific families of geometric objects. By Theorem 1, it suffices
to provide (i) a dynamic data structure $\mathcal{DS}_{0}$ for intersection
detection queries, and (ii) a static algorithm $\mathcal{A}$ for solving the
special case of the vertex cover problem when $n\leq(2+O(\gamma))\mbox{\rm
OPT}$.

#### Disks in $\mathbb{R}^{2}$.

Intersection detection queries for disks in $\mathbb{R}^{2}$ reduce to
additively weighted Euclidean nearest neighbor search, where the weights
(different from the weights from MWU) are the radii of the disks. Kaplan et
al. [KKK+22] adapted Chan’s data structure [Cha20b, Cha01] for dynamic
Euclidean nearest neighbor search in $\mathbb{R}^{2}$ and obtained a data
structure for additively weighted Euclidean nearest neighbor search with
polylogarithmic amortized update time and query time. Thus, $\mathcal{DS}_{0}$
can be implemented in $\tau_{0}(n)=O(\log^{O(1)}n)$ amortized time for disks
in $\mathbb{R}^{2}$.

In Appendix A.1, we give a static $(1+O(\varepsilon))$-approximation algorithm
$\mathcal{A}$ for MVC for disks, under the promise that $n=O(\mbox{\rm OPT})$,
with running time $T(n)=\widetilde{O}(2^{O(1/\varepsilon^{2})}n)$. The
algorithm is obtained by modifying a known PTAS for MIS for disks [Cha03a].

Applying Theorem 1 with $c=1+O(\varepsilon)$, $\gamma=\Theta(1)$, and
$\delta=\varepsilon^{2}$, we obtain our main result for disks:

######  Corollary 1.

There is a dynamic data structure for $n$ disks in $\mathbb{R}^{2}$ that
maintains a $(1+O(\varepsilon))$-approximation of the minimum vertex cover of
the intersection graph, under insertions and deletions, in
$O(2^{O(1/\varepsilon^{2})}\log^{O(1)}n)$ amortized time.

#### Rectangles in $\mathbb{R}^{2}$.

For rectangles in $\mathbb{R}^{2}$, dynamic intersection detection requires
$\tau_{0}(n)=O(\log^{O(1)}n)$ query and update time, by standard orthogonal
range searching techniques (range trees) [PS85, AE99].

(Note: There is an alternative approach that bypasses Eppstein’s technique and
directly solves the $\mathcal{DS}$ data structure problem: We dynamically
maintain a _biclique cover_ , which can be done in polylogarithmic time for
rectangles [Cha06]. It is then easy to maintain the minimum weight of each
biclique, by maintaining the minimum weight of each of the two sides of the
biclique with priority queues.)

In Appendix A.2, we give a static $(\frac{3}{2}+O(\varepsilon))$-approximation
algorithm for MVC for rectangles, with running time
$T(n)=\widetilde{O}(2^{O(1/\varepsilon^{2})}n)$. The algorithm is obtained by
modifying the method by Bar-Yehuda, Hermelin, and Rawitz [BYHR11], and
combining with our efficient kernelization method.

Applying Theorem 1 with $c=\frac{3}{2}+O(\varepsilon)$, $\gamma=\Theta(1)$,
and $\delta=\varepsilon^{2}$, we obtain our main result for rectangles:

######  Corollary 2.

There is a dynamic data structure for $n$ axis-aligned rectangles in
$\mathbb{R}^{2}$ that maintains a $(\frac{3}{2}+O(\varepsilon))$-approximation
of the minimum vertex cover of the intersection graph, under insertions and
deletions, in $O(2^{O(1/\varepsilon^{2})}\log^{O(1)}n)$ amortized time.

#### Fat boxes (e.g., hypercubes) in $\mathbb{R}^{d}$.

For the case of fat axis-aligned boxes (e.g., hypercubes) in a constant
dimension $d$, dynamic intersection detection can again be solved with
$\tau_{0}(n)=O(\log^{O(1)}n)$ amortized query and update time by orthogonal
range searching [PS85, AE99]. We can design the static algorithm $\mathcal{A}$
in exactly the same way as in the case of disks (since the method in Appendix
A.1 holds for fat objects in $\mathbb{R}^{d}$), achieving
$T(n)=\widetilde{O}(2^{O(1/\varepsilon^{d})}n)$.

######  Corollary 3.

There is a dynamic data structure for $n$ fat axis-aligned boxes in
$\mathbb{R}^{d}$ for any constant $d$ that maintains a
$(1+O(\varepsilon))$-approximation of the minimum vertex cover of the
intersection graph, under insertions and deletions, in
$O(2^{O(1/\varepsilon^{d})}\log^{O(1)}n)$ amortized time.

We can also obtain results for balls or other types of fat objects in
$\mathbb{R}^{d}$, but because intersection detection data structures have
higher complexity, the update time would be sublinear rather than
polylogarithmic.

#### Bipartite disks in $\mathbb{R}^{2}$.

For the case of a bipartite intersection graph between two sets of disks in
$\mathbb{R}^{2}$, we have $\tau_{0}(n)=O(\log^{O(1)}n)$ as already noted. In
the bipartite case, the static algorithm $\mathcal{A}$ is trivial: we just
return the smaller of the two parts in the bipartition, which yields a vertex
cover of size at most $n/2\leq(1+O(\varepsilon))\,\mbox{\rm OPT}$ under the
promise that $n\leq(2+O(\varepsilon))\,\mbox{\rm OPT}$.

Applying Theorem 1 with $c=1+O(\varepsilon)$, $\gamma=\varepsilon$, and
$\delta=\varepsilon^{3}$, we obtain:

######  Corollary 4.

There is a dynamic data structure for two sets of $O(n)$ disks in
$\mathbb{R}^{2}$ that maintains a $(1+O(\varepsilon))$-approximation of the
minimum vertex cover of the bipartite intersection graph, under insertions and
deletions, in $O((1/\varepsilon^{7})\log^{O(1)}n)$ amortized time.

#### Bipartite boxes in $\mathbb{R}^{d}$.

For the case of a bipartite intersection graph between two sets of (not
necessarily fat) boxes in $\mathbb{R}^{d}$, we have
$\tau_{0}(n)=O(\log^{O(1)}n)$ by orthogonal range searching. As already noted,
in bipartite cases, the static algorithm $\mathcal{A}$ is trivial.

######  Corollary 5.

There is a dynamic data structure for two sets of $O(n)$ axis-aligned boxes in
$\mathbb{R}^{d}$ for any constant $d$ that maintains a
$(1+O(\varepsilon))$-approximation of the minimum vertex cover of the
bipartite intersection graph, under insertions and deletions, in
$O((1/\varepsilon^{7})\log^{O(1)}n)$ amortized time.

We did not write out the number of logarithmic factors in our results, as we
have not attempted to optimize them, but it is upper-bounded by 3 plus the
number of logarithmic factors in $\tau_{0}(n)$.

##  3 Bipartite Maximum-Cardinality Matching

The approach in the previous section finds a
$(1+O(\varepsilon))$-approximation of the MVC of bipartite geometric
intersection graphs, and so it allows us to approximate the size of the MCM in
such bipartite graphs. However, it doesn’t compute a matching. In this
section, we give a different approach to maintain a
$(1+O(\varepsilon))$-approximation of the MCM in bipartite intersection
graphs. The first thought that comes to mind is to compute a kernel, as we
have done for MVC, but for MCM, known approaches seem to yield only a kernel
of $O(\mbox{\rm OPT}^{2})$ size (e.g., see Gupta and Peng [GP13]). Instead, we
will bypass kernels and construct an approximate MCM directly.

###  3.1 Approximate Bipartite MCM via Modified Hopcroft–Karp

It is well known that Hopcroft and Karp’s $O(m\sqrt{n})$-time algorithm for
exact MCM in bipartite graphs [HK73] can be modified to give a
$(1+\varepsilon)$-approximation algorithm that runs in near-linear time,
simply by terminating early after $O(1/\varepsilon)$ iterations (for example,
see the introduction in [DP10]). We describe a way to reimplement the
algorithm in sublinear time when OPT is small by using appropriate data
structures, which correspond to dynamic intersection detection in the case of
geometric intersection graphs. Note that earlier work by Efrat, Itai, and Katz
[EIK01] has already combined Hopcroft and Karp’s algorithm with geometric data
structures to obtain static exact algorithm [EIK01] for maximum matching in
bipartite geometric intersection graphs (see also Har-Peled and Yang’s paper
[HY22] on static approximation algorithms). However, to achieve bounds
sensitive to OPT, our algorithm will work differently (in particular, it will
be DFS-based instead of BFS-based).

######  Lemma 4.

We are given an unweighted bipartite graph $G=(V,E)$. Suppose there is a data
structure $\mathcal{DS}_{0}$ for storing a subset $S\subseteq V$ of vertices,
initially with $S=\emptyset$, that supports the following two operations in
$\tau_{0}$ time: given a vertex $u\in V$, find a neighbor of $u$ that is in
$S$ (if exists), and insert/delete a vertex to/from $S$.

Given a data structure $\mathcal{DS}_{0}$ that currently has $S=V$, and given
a maximal matching $M_{0}$, we can compute a
$(1+O(\varepsilon))$-approximation to the maximum-cardinality matching in
$\widetilde{O}((1/\varepsilon^{2})\,\mbox{\rm OPT}\cdot\tau_{0})$ time. Here,
OPT denotes the maximum matching size.

###### Proof.

The algorithm proceeds iteratively. We maintain a matching $M$. At the
beginning of the $\ell$-th iteration, we know that the current matching $M$
does not have augmenting paths of length $\leq 2\ell-1$. We find a maximal
collection $\Gamma$ of vertex-disjoint augmenting paths of length $2\ell+1$.
We then augment $M$ along the paths in $\Gamma$. As shown by Hopcroft and Karp
[HK73], the new matching $M$ will then not have augmenting paths of length
$\leq 2\ell+1$.

As shown by Hopcroft and Karp [HK73], there are at least $\mbox{\rm OPT}-|M|$
vertex-disjoint augmenting paths, and so $|M|\geq(\ell+1)(\mbox{\rm
OPT}-|M|)$, i.e., $\mbox{\rm OPT}\leq(1+\frac{1}{\ell+1})|M|$. Thus, once
$\ell$ reaches $\Theta(1/\varepsilon)$, we may terminate the algorithm.
Initially, we can set $M=M_{0}$ before the first iteration.

It suffices to describe how to find a maximal collection $\Gamma$ of vertex-
disjoint augmenting paths of length $2\ell+1$ in the $\ell$-th iteration,
under the assumption that there are no shorter augmenting paths. Hopcroft and
Karp originally proposed a BFS approach, starting at the “exposed” vertices
not covered by the current matching $M$. Unfortunately, this approach does not
work in our setting: because we want the running time to be near OPT, the
searches need to start at vertices of $M$. We end up adopting a DFS approach,
but the vertices of $M$ need to be duplicated $\ell$ times in $\ell$ “layers”
(this increases the running time by a factor of $\ell$, but fortunately,
$\ell$ is small in our setting).

Let $V_{M}$ be the $2|M|$ vertices of the current matching $M$. As is well
known, $\mbox{\rm OPT}\leq 2|M|$. A walk $v_{0}u_{1}v_{1}\cdots
u_{\ell}v_{\ell}u_{\ell+1}$ in $G$ is an _augmenting walk_ of length $2\ell+1$
if $v_{0}\not\in V_{M}$, $v_{0}u_{1}\not\in M$, $u_{1}v_{1}\in M$, …,
$v_{\ell}u_{\ell+1}\not\in M$, and $u_{\ell+1}\not\in V_{M}$. In such an
augmenting walk of length $\ell$, we automatically have $v_{0}\neq u_{\ell+1}$
(because $G$ is bipartite) and the walk must automatically be a simple path
(because otherwise we could short-cut and obtain an augmenting path of length
$\leq 2\ell-1$). In the procedure $\textsc{extend}(v_{0}u_{1}v_{1}\cdots
u_{i},\ell)$ below, the input is a walk $v_{0}u_{1}v_{1}\cdots u_{i}$ with
$v_{0}u_{1}\not\in M$, $u_{1}v_{1}\in M$, …, $v_{i-1}u_{i}\not\in M$, and the
output is true if it is possible to extend it to an augmenting walk
$v_{0}u_{1}v_{1}\cdots u_{\ell}v_{\ell}u_{\ell+1}$ of length $2\ell+1$ that is
vertex-disjoint from the augmenting walks generated so far.

> $\textsc{maximal-aug-paths}(\ell)$:
> ---
> 1. | let $S=V\setminus V_{M}$ and $S_{1}=\cdots=S_{\ell}=V_{M}$
> 2. | for each $u_{1}\in S_{1}$ do
> 3. |  | let $v_{0}$ be a neighbor of $u_{1}$ with $v_{0}\in S$
> 4. |  | if $v_{0}$ does not exist then delete $u_{1}$ from $S_{1}$
> 5. |  | else $\textsc{extend}(v_{0}u_{1},\ell)$
> $\textsc{extend}(v_{0}u_{1}v_{1}\cdots u_{i},\ell)$:
> 1. | let $v_{i}$ be the partner of $u_{i}$ in $M$
> 2. | if $i=\ell$ then
> 3. |  | let $u_{\ell+1}$ be a neighbor of $v_{\ell}$ with $u_{\ell+1}\in S$
> 4. |  | if $u_{\ell+1}$ does not exist then delete $u_{\ell}$ from $S_{\ell}$ and return false
> 5. |  | output the augmenting path $v_{0}u_{1}v_{1}\cdots u_{\ell}v_{\ell}u_{\ell+1}$
> 6. |  | delete $v_{0}$ and $u_{\ell+1}$ from $S$, and $u_{1},\ldots,u_{\ell}$ from all of $S_{1},\ldots,S_{\ell}$, and return true
> 7. | for each neighbor $u_{i+1}$ of $v_{i}$ with $u_{i+1}\in S_{i+1}\setminus\\{u_{i}\\}$ do
> 8. |  | if $\textsc{extend}(v_{0}u_{1}v_{1}\cdots u_{i+1},\ell)=$ true then return true
> 9. | delete $u_{i}$ from $S_{i}$ and return false

Note that if it is not possible to extend the walk $v_{0}u_{1}v_{1}\cdots
u_{i}$ to an augmenting walk of length $2\ell+1$, then it is not possible to
extend any other walk $v_{0}^{\prime}u_{1}^{\prime}v_{1}^{\prime}\cdots
u_{i}^{\prime}$ of the same length with $u_{i}^{\prime}=u_{i}$. This justifies
why we may delete $u_{i}$ from $S_{i}$ in line 9 of extend (and similarly why
we may delete $u_{\ell}$ from $S_{\ell}$ in line 4 of extend, and why we may
delete $u_{1}$ from $S_{1}$ in line 4 of maximal-aug-paths).

For the running time analysis, note that each vertex may be a candidate for
$u_{i}$ in only one call to extend per $i$, because we delete $u_{i}$ from
$S_{i}$, either in line 9 if false is returned, or in line 6 if true is
returned. Thus, the number of calls to extend is at most $O(\ell|M|)$.

We use the given data structure $\mathcal{DS}_{0}$ to maintain $S$. This
allows us to do line 3 of maximal-aug-paths. Line 1 of maximal-aug-paths
requires $O(|M|)$ initial deletions from $S$. At the end, we reset $S$ to $V$
by performing $O(|M|)$ insertions of the deleted elements.

We also maintain $S_{1},\ldots,S_{\ell}$ in $\ell$ new instances of the data
structure $\mathcal{DS}_{0}$. This allows us to do lines 3 and 7 of extend.
Line 1 of maximal-aug-paths requires $O(\ell|M|)$ initial insertions to
$S_{1},\ldots,S_{\ell}$. We conclude that maximal-aug-paths takes
$O(\ell|M|\cdot\tau_{0})$ time. Hence, the overall running time of all
$\ell=\Theta(1/\varepsilon)$ iterations is
$O((1/\varepsilon^{2})|M|\cdot\tau_{0})$. ∎

###  3.2 Dynamic Geometric Bipartite MCM

To solve dynamic bipartite MCM for geometric intersection graphs, we again use
a standard idea for dynamization: be lazy, and periodically recompute the
solution only after every $\varepsilon\,\mbox{\rm OPT}$ updates (since the
optimal size changes by at most 1 per update).

######  Theorem 2.

Let $\mathcal{C}$ be a class of geometric objects, where there is a dynamic
data structure $\mathcal{DS}_{0}$ for $n$ objects in $\mathcal{C}$ that can
find an object intersecting a query object (if exists), and supports
insertions and deletions of objects, with $O(\tau_{0}(n))$ query and update
time.

Then there is a dynamic data structure for two sets of $O(n)$ objects in
$\mathcal{C}$ that maintains a $(1+O(\varepsilon))$-approximation of the
maximum-cardinality matching in the bipartite intersection graph, under
insertions and deletions of objects, in
$\widetilde{O}((1/\varepsilon^{3})\tau_{0}(n))$ amortized time.

###### Proof.

First, observe that we can maintain a maximal matching $M_{0}$ with
$O(\tau_{0}(n))$ update time: We maintain the subset $S$ of all vertices not
in $M_{0}$ in a data structure $\mathcal{DS}_{0}$. When we insert a new object
$u$, we match it with an object in $S$ intersecting $u$ (if exists) by
querying $\mathcal{DS}_{0}$. When we delete an object $u$, we delete $u$ and
its partner $v$ in $M_{0}$, and reinsert $v$.

Assume that $b\leq\mbox{\rm OPT}<2b$ for a given parameter $b$. Divide into
phases with $\varepsilon b$ updates each. At the beginning of each phase,
compute a $(1+O(\varepsilon))$-approximation of the maximum-cardinality
matching by Lemma 4 in $\widetilde{O}((1/\varepsilon^{2})b\cdot\tau_{0}(n))$
time. (It is important to note that we don’t rebuild the data structure
$\mathcal{DS}$ for $S=V$ at the beginning of each phase; we continue using the
same structure $\mathcal{DS}$ in the next phase, after resetting the modified
$S$ back to $V$.)

Since the above is done only at the beginning of each phase, the amortized
cost per update is
$\widetilde{O}(\frac{(1/\varepsilon^{2})b\cdot\tau_{0}(n)}{\varepsilon b})$.

During a phase, we handle an object insertion simply by doing nothing, and we
handle an object deletion simply by removing its incident edge (if exists)
from the current matching. This incurs an additive error at most
$O(\varepsilon b)=O(\varepsilon\,\mbox{\rm OPT})$. We also perform the
insertion/deletion of the object in $\mathcal{DS}_{0}$ for $S=V$, in
$\widetilde{O}(\tau_{0}(n))$ time.

How do we obtain a correct guess $b$? We build the above data structure for
each $b$ that is a power of 2, and run the algorithm simultaneously for each
$b$. ∎

###  3.3 Specific Results

Recall that for disks in $\mathbb{R}^{2}$ as well as boxes in
$\mathbb{R}^{d}$, we have $\tau_{0}(n)=O(\log^{O(1)}n)$. (Note that most data
structures for intersection detection can be modified to report a witness
object intersecting the query object if the answer is true.) Thus, we
immediately obtain:

######  Corollary 6.

There is a dynamic data structure for two sets of $O(n)$ disks in
$\mathbb{R}^{2}$ that maintains a $(1+O(\varepsilon))$-approximation of the
maximum-cardinality matching in the bipartite intersection graph, under
insertions and deletions, in $O((1/\varepsilon^{3})\log^{O(1)}n)$ amortized
time.

######  Corollary 7.

There is a dynamic data structure for two sets of $O(n)$ axis-aligned boxes in
$\mathbb{R}^{d}$ for any constant $d$ that maintains a
$(1+O(\varepsilon))$-approximation of the maximum-cardinality matching in the
bipartite intersection graph, under insertions and deletions, in
$O((1/\varepsilon^{3})\log^{O(1)}n)$ amortized time.

##  4 General Maximum-Cardinality Matching

In this section, we adapt our results for bipartite MCM to general MCM. We use
a simple idea by Lotker, Patt-Shamir, and Pettie [LPP15] to reduce the problem
for general graphs (in the approximate setting) to finding maximal collections
of short augmenting paths in _bipartite_ graphs, which we already know how to
solve. (See also Har-Peled and Yang’s paper [HY22], which applied Lotker et
al.’s idea to obtain static approximation algorithms for geometric
intersection graphs.) The reduction has exponential dependence in the path
length $\ell$ (which is fine since $\ell$ is small), and is originally
randomized. We reinterpret their idea in terms of _color-coding_ [AYZ95],
which allows for efficient derandomization, and also simplifies the analysis
(bypassing Chernoff-bound calculations). With this reinterpretation, it is
easy to show that the idea carries over to the dynamic setting.

We begin with a lemma, which is a consequence of the standard color-coding
technique:

######  Lemma 5.

For any $n$ and $\ell$, there exists a collection $\mathcal{Z}^{(n,\ell)}$ of
$O(2^{O(\ell)}\log n)$ subsets of $[n]:=\\{1,\ldots,n\\}$ such that for any
two disjoint sets $A,B\subseteq[n]$ of total size at most $\ell$, we have
$A\subseteq Z$ and $B\subseteq[n]\setminus Z$ for some $Z\in\mathcal{Z}$.
Furthermore, $\mathcal{Z}^{(n,\ell)}$ can be constructed in
$O(2^{O(\ell)}n\log n)$ time.

###### Proof.

As shown by Alon, Yuster, and Zwick [AYZ95], there exists a collection
$\mathcal{H}^{(n,\ell)}$ of $O(2^{O(\ell)}\log n)$ mappings
$h:[n]\rightarrow[\ell]$, such that for any set $S\subseteq[n]$ of size at
most $\ell$, the elements in $\\{h(v):v\in S\\}$ are all distinct.
Furthermore, $\mathcal{H}^{(n,\ell)}$ can be constructed in
$O(2^{O(\ell)}n\log n)$ time. (This is related to the notion of
“$\ell$-perfect hash family”.)

For each $h\in\mathcal{H}^{(n,\ell)}$ and each subset $I\subseteq[\ell]$, add
the subset $Z_{h,I}=\\{v\in[n]:h(v)\in I\\}$ to $\mathcal{Z}^{(n,\ell)}$. The
number of subsets is $|\mathcal{H}^{(n,\ell)}|\cdot 2^{\ell}\leq
2^{O(\ell)}\log n$. For any two disjoint sets $A,B\subseteq[n]$ of total size
at most $\ell$, let $h\in\mathcal{H}^{(n,\ell)}$ be such that the elements in
$\\{h(a):a\in A\\}$ and $\\{h(b):b\in B\\}$ are all distinct, and let
$I=\\{h(a):a\in A\\}$; then $A\subseteq Z_{h,I}$ and $B\subseteq[n]\setminus
Z_{h,I}$. ∎

We now present a non-bipartite analog of Lemma 4:

######  Lemma 6.

We are given an unweighted graph $G=(V,E)$, with $V=[n]$. Let
$\mathcal{Z}^{(n,1/\varepsilon)}$ be as in Lemma 5. Suppose there is a data
structure $\mathcal{DS}_{0}^{*}$ for storing a subset $S\subseteq V$ of
vertices, initially with $S=\emptyset$, that supports the following two
operations in $\tau_{0}$ time: given a vertex $u\in V$ and
$Z\in\mathcal{Z}^{(n,1/\varepsilon)}$, find a neighbor of $u$ that is in
$S\cap Z$ (if exists) and a neighbor of $u$ that is in $S\setminus Z$ (if
exists); and insert/delete a vertex to/from $S$.

Given a data structure $\mathcal{DS}_{0}$ that currently has $S=V$, and given
a maximal matching $M_{0}$, we can compute a
$(1+O(\varepsilon))$-approximation to the maximum-cardinality matching in
$\widetilde{O}(2^{O(1/\varepsilon)}\,\mbox{\rm OPT}\cdot\tau_{0})$ time. Here,
OPT denotes the maximum matching size.

###### Proof.

As in the proof of Lemma 4, we iteratively maintain a current matching $M$,
and it suffices to describe how to find a maximal collection $\Gamma$ of
vertex-disjoint augmenting paths of length $2\ell+1$ in the $\ell$-th
iteration, under the assumption that there are no augmenting paths of length
$\leq 2\ell-1$. However, the presence of odd-length cycles complicates the
computation of $\Gamma$.

Initialize $\Gamma=\emptyset$. We loop through each
$Z\in\mathcal{Z}^{(n,1/\varepsilon)}$ one by one and do the following. Let
$G_{Z}$ be the subgraph of $G$ with edges $\\{uv\in E:u\in Z,\,v\not\in Z\\}$.
We find a maximal collection of vertex-disjoint augmenting paths of length
$2\ell+1$ in $G_{Z}$ that are vertex-disjoint from paths already selected to
be in $\Gamma$; we then add this new collection to $\Gamma$. Since $G_{Z}$ is
bipartite, this step can be done using the maximal-aug-paths procedure from
the proof of Lemma 4. Since we are working with $G_{Z}$ instead of $G$, when
we find neighbors of a given vertex, they are now restricted to be in $Z$ if
the given vertex is in $[n]\setminus Z$, or vice versa; the data structure
$\mathcal{DS}_{0}^{*}$ allows for such queries. The only other change is that
when we initialize $S,S_{1},\ldots,S_{\ell}$, we should remove vertices that
have appeared in paths already selected to be in $\Gamma$.

Assume $2\ell+2\leq 1/\varepsilon$. We claim that after looping through all
$Z\in\mathcal{Z}^{(n,1/\varepsilon)}$, the resulting collection $\Gamma$ of
vertex-disjoint length-$(2\ell+1)$ augmenting paths is maximal in $G$. To see
this, consider any length-$(2\ell+1)$ augmenting path $v_{0}u_{1}v_{1}\cdots
u_{\ell}v_{\ell}u_{\ell+1}$ in $G$. There exists
$Z\in\mathcal{Z}^{(n,1/\varepsilon)}$ such that $u_{1},\ldots,u_{\ell+1}\in Z$
and $v_{0},\ldots,v_{\ell}\not\in Z$. Thus, the path must intersect some path
in $\Gamma$ during the iteration when we consider $Z$. ∎

We can now obtain a non-bipartite analog of Theorem 2:

######  Theorem 3.

Let $\mathcal{C}$ be a class of geometric objects, where there is a dynamic
data structure $\mathcal{DS}_{0}$ for $n$ objects in $\mathcal{C}$ that can
find an object intersecting a query object (if exists), and supports
insertions and deletions of objects, with $O(\tau_{0}(n))$ query and update
time.

Then there is a dynamic data structure for $O(n)$ objects in $\mathcal{C}$
that maintains a $(1+O(\varepsilon))$-approximation of the maximum-cardinality
matching in the intersection graph, under insertions and deletions of objects,
in $\widetilde{O}(2^{O(1/\varepsilon)}\tau_{0}(n))$ amortized time.

###### Proof.

This is similar to the proof of Theorem 2, with Lemma 6 replacing Lemma 4. The
only difference is that to support the data structure $\mathcal{DS}_{0}^{*}$,
we maintain $O(2^{O(1/\varepsilon)}\log n)$ parallel instances of the data
structure $\mathcal{DS}_{0}$ for $S\cap Z$ and $S\setminus Z$, for every
$Z\in\mathcal{Z}^{(n,1/\varepsilon)}$. This increases the update time by a
factor of $O(2^{O(1/\varepsilon)}\log n)$.

We have assumed that the input objects are labeled by integers in $[n]$. When
a new object is inserted, we can just assign it the next available label in
$[n]$. When the number of objects exceeds $n$, we double $n$ and rebuild the
entire data structure from scratch. Similarly, when the number of objects is
below $n/4$, we halve $n$ and rebuild. ∎

######  Corollary 8.

There is a dynamic data structure for $n$ disks in $\mathbb{R}^{2}$ that
maintains a $(1+O(\varepsilon))$-approximation of the maximum-cardinality
matching in the intersection graph, under insertions and deletions, in
$O(2^{O(1/\varepsilon)}\log^{O(1)}n)$ amortized time.

######  Corollary 9.

There is a dynamic data structure for $n$ axis-aligned boxes in
$\mathbb{R}^{d}$ for any constant $d$ that maintains a
$(1+O(\varepsilon))$-approximation of the maximum-cardinality matching in the
intersection graph, under insertions and deletions, in
$O(2^{O(1/\varepsilon)}\log^{O(1)}n)$ amortized time.

##  5 Conclusion

In this paper, we studied two fundamental graph optimization problems, MVC and
MCM, in fully dynamic geometric settings. For both of the problems, we
developed general frameworks based on the dynamic intersection detection data
structures and static approximation algorithms, which are necessary
ingredients for designing dynamic algorithms for geometric intersection
graphs. These frameworks allowed us to obtain dynamic algorithms for a wide
range of geometric intersection graphs, e.g., disks/rectangles in
$\mathbb{R}^{2}$, hypercubes in $\mathbb{R}^{d}$, etc. Moreover, our results
extend to the bipartite versions of the problems as well. In this work, we
primarily focused on the unweighted case. Our approach does not readily extend
to the weighted setting. Obtaining efficient dynamic algorithms for both MVC
and MCM in the weighted setting are interesting open problems.

## References

  * [ABR24] Amir Azarmehr, Soheil Behnezhad, and Mohammad Roghani.  Fully dynamic matching: $(2-\sqrt{2})$-approximation in polylog update time.  In Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3040–3061, 2024.  doi:10.1137/1.9781611977912.109.
  * [AC09] Peyman Afshani and Timothy M. Chan.  Dynamic connectivity for axis-parallel rectangles.  Algorithmica, 53(4):474–487, 2009.  doi:10.1007/S00453-008-9234-7.
  * [ACS+22] Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue.  Dynamic geometric set cover and hitting set.  ACM Trans. Algorithms, 18(4):40:1–40:37, 2022.  doi:10.1145/3551639.
  * [AE99] Pankaj K. Agarwal and Jeff Erickson.  Geometric range searching and its relatives.  In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, pages 1–56. AMS Press, 1999.
  * [AHRS24] Pankaj K. Agarwal, Sariel Har-Peled, Rahul Raychaudhury, and Stavros Sintos.  Fast approximation algorithms for piercing boxes by points.  In Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4892–4908, 2024.  doi:10.1137/1.9781611977912.174.
  * [AHW19] Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese.  Approximation schemes for independent set and sparse subsets of polygons.  J. ACM, 66(4):29:1–29:40, 2019.  doi:10.1145/3326122.
  * [AYZ95] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  J. ACM, 42(4):844–856, 1995.  doi:10.1145/210332.210337.
  * [BCIK21] Sujoy Bhore, Jean Cardinal, John Iacono, and Grigorios Koumoutsos.  Dynamic geometric independent set.  In Abstracts of 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJDCG), 2021.  arXiv:2007.08643.
  * [BCM23] Édouard Bonnet, Sergio Cabello, and Wolfgang Mulzer.  Maximum matchings in geometric intersection graphs.  Discrete & Computational Geometry, pages 1–30, 2023.  doi:10.1007/S00454-023-00564-3.
  * [Beh23] Soheil Behnezhad.  Dynamic algorithms for maximum matching size.  In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 129–162, 2023.  doi:10.1137/1.9781611977554.CH6.
  * [BG95] Hervé Brönnimann and Michael T. Goodrich.  Almost optimal set covers in finite VC-dimension.  Discret. Comput. Geom., 14(4):463–479, 1995.  doi:10.1007/BF02570718.
  * [BHI18] Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano.  Deterministic fully dynamic data structures for vertex cover and matching.  SIAM J. Comput., 47(3):859–887, 2018.  doi:10.1137/140998925.
  * [BJ02] Gerth Stølting Brodal and Riko Jacob.  Dynamic planar convex hull.  In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS), pages 617–626, 2002.  doi:10.1109/SFCS.2002.1181985.
  * [BK19] Sayan Bhattacharya and Janardhan Kulkarni.  Deterministically maintaining a $(2+\varepsilon)$-approximate minimum vertex cover in $O(1/{\varepsilon}^{2})$ amortized update time.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1872–1885, 2019.  doi:10.1137/1.9781611975482.113.
  * [BKSW23] Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, and David Wajc.  Dynamic matching with better-than-2 approximation in polylogarithmic update time.  In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 100–128, 2023.  doi:10.1137/1.9781611977554.CH5.
  * [BLN22] Sujoy Bhore, Guangping Li, and Martin Nöllenburg.  An algorithmic study of fully dynamic independent sets for map labeling.  ACM J. Exp. Algorithmics, 27:1.8:1–1.8:36, 2022.  doi:10.1145/3514240.
  * [BNTW23] Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth, and Jules Wulms.  Fully dynamic maximum independent sets of disks in polylogarithmic update time.  CoRR, abs/2308.00979, 2023.  To appear in SoCG 2024.  arXiv:2308.00979.
  * [BS15] Aaron Bernstein and Cliff Stein.  Fully dynamic matching in bipartite graphs.  In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), Part I, volume 9134 of Lecture Notes in Computer Science, pages 167–179. Springer, 2015.  doi:10.1007/978-3-662-47672-7\\_14.
  * [BS16] Aaron Bernstein and Cliff Stein.  Faster fully dynamic matchings with small approximation ratios.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 692–711, 2016.  doi:10.1137/1.9781611974331.CH50.
  * [BYHR11] Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz.  Minimum vertex cover in rectangle graphs.  Computational Geometry, 44(6-7):356–364, 2011.  doi:10.1016/J.COMGEO.2011.03.002.
  * [CCJ90] Brent N. Clark, Charles J. Colbourn, and David S. Johnson.  Unit disk graphs.  Discrete mathematics, 86(1-3):165–177, 1990.  doi:10.1016/0012-365X(90)90358-O.
  * [CE16] Julia Chuzhoy and Alina Ene.  On approximating maximum independent set of rectangles.  In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 820–829, 2016.  doi:10.1109/FOCS.2016.92.
  * [CH21] Timothy M. Chan and Qizheng He.  More dynamic data structures for geometric set cover with sublinear update time.  In Proceedings of the 37th International Symposium on Computational Geometry (SoCG), volume 189 of LIPIcs, pages 25:1–25:14, 2021.  doi:10.4230/LIPICS.SOCG.2021.25.
  * [CH24] Timothy M. Chan and Zhengcheng Huang.  Dynamic geometric connectivity in the plane with constant query time.  CoRR, abs/arXiv:2402.05357, 2024.  To appear in SoCG 2024.  arXiv:2402.05357.
  * [Cha01] Timothy M. Chan.  Dynamic planar convex hull operations in near-logarithmaic amortized time.  J. ACM, 48(1):1–12, 2001.  doi:10.1145/363647.363652.
  * [Cha03a] Timothy M. Chan.  Polynomial-time approximation schemes for packing and piercing fat objects.  J. Algorithms, 46(2):178–189, 2003.  doi:10.1016/S0196-6774(02)00294-8.
  * [Cha03b] Timothy M. Chan.  Semi-online maintenance of geometric optima and measures.  SIAM J. Comput., 32(3):700–716, 2003.  doi:10.1137/S0097539702404389.
  * [Cha06] Timothy M. Chan.  Dynamic subgraph connectivity with geometric applications.  SIAM J. Comput., 36(3):681–694, 2006.  doi:10.1137/S009753970343912X.
  * [Cha09] Timothy M. Chan.  Dynamic coresets.  Discret. Comput. Geom., 42(3):469–488, 2009.  doi:10.1007/S00454-009-9165-3.
  * [Cha10] Timothy M. Chan.  A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries.  J. ACM, 57(3):16:1–16:15, 2010.  doi:10.1145/1706591.1706596.
  * [Cha20a] Timothy M. Chan.  Dynamic generalized closest pair: Revisiting Eppstein’s technique.  In Proceedings of the 3rd SIAM Symposium on Simplicity in Algorithms (SOSA), pages 33–37, 2020.  doi:10.1137/1.9781611976014.6.
  * [Cha20b] Timothy M. Chan.  Dynamic geometric data structures via shallow cuttings.  Discret. Comput. Geom., 64(4):1235–1252, 2020.  doi:10.1007/S00454-020-00229-5.
  * [CHSX22] Timothy M. Chan, Qizheng He, Subhash Suri, and Jie Xue.  Dynamic geometric set cover, revisited.  In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3496–3528, 2022.  doi:10.1137/1.9781611977073.139.
  * [CIK21] Jean Cardinal, John Iacono, and Grigorios Koumoutsos.  Worst-case efficient dynamic geometric independent set.  In Proceedings of the 29th Annual European Symposium on Algorithms (ESA), volume 204 of LIPIcs, pages 25:1–25:15, 2021.  doi:10.4230/LIPICS.ESA.2021.25.
  * [CKL+22] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022.  doi:10.1109/FOCS54457.2022.00064.
  * [CLP11] Timothy M. Chan, Kasper Green Larsen, and Mihai Pătraşcu.  Orthogonal range searching on the RAM, revisited.  In Proceedings of the 27th ACM Symposium on Computational Geometry (SoCG), pages 1–10, 2011.  doi:10.1145/1998196.1998198.
  * [CPR11] Timothy M. Chan, Mihai Pătraşcu, and Liam Roditty.  Dynamic connectivity: Connecting to networks and geometry.  SIAM J. Comput., 40(2):333–349, 2011.  doi:10.1137/090751670.
  * [DP10] Ran Duan and Seth Pettie.  Approximating maximum weight matching in near-linear time.  In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 673–682, 2010.  doi:10.1109/FOCS.2010.70.
  * [EIK01] Alon Efrat, Alon Itai, and Matthew J Katz.  Geometry helps in bottleneck matching and related problems.  Algorithmica, 31:1–28, 2001.  doi:10.1007/S00453-001-0016-8.
  * [EJS05] Thomas Erlebach, Klaus Jansen, and Eike Seidel.  Polynomial-time approximation schemes for geometric intersection graphs.  SIAM Journal on Computing, 34(6):1302–1323, 2005.  doi:10.1137/S0097539702402676.
  * [Epp95] David Eppstein.  Dynamic Euclidean minimum spanning trees and extrema of binary functions.  Discret. Comput. Geom., 13:111–122, 1995.  doi:10.1007/BF02574030.
  * [FM95] Tomás Feder and Rajeev Motwani.  Clique partitions, graph compression and speeding-up algorithms.  J. Comput. Syst. Sci., 51(2):261–272, 1995.  doi:10.1006/JCSS.1995.1065.
  * [GP13] Manoj Gupta and Richard Peng.  Fully dynamic $(1+\varepsilon)$-approximate matchings.  In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 548–557, 2013.  doi:10.1109/FOCS.2013.65.
  * [Har23] Sariel Har-Peled.  Approximately: Independence implies vertex cover.  CoRR, abs/2308.00840, 2023.  arXiv:2308.00840.
  * [HK73] John E. Hopcroft and Richard M. Karp.  An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs.  SIAM J. Comput., 2(4):225–231, 1973.  doi:10.1137/0202019.
  * [HM85] Dorit S. Hochbaum and Wolfgang Maass.  Approximation schemes for covering and packing problems in image processing and VLSI.  Journal of the ACM, 32(1):130–136, 1985.  doi:10.1145/2455.214106.
  * [HNW20] Monika Henzinger, Stefan Neumann, and Andreas Wiese.  Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles.  In Proceedings of the 36th International Symposium on Computational Geometry (SoCG), volume 164 of LIPIcs, pages 51:1–51:14, 2020.  doi:10.4230/LIPICS.SOCG.2020.51.
  * [HY22] Sariel Har-Peled and Everett Yang.  Approximation algorithms for maximum matchings in geometric intersection graphs.  In Proceedings of the 38th International Symposium on Computational Geometry (SoCG), volume 224 of LIPIcs, pages 47:1–47:13, 2022.  doi:10.4230/LIPICS.SOCG.2022.47.
  * [KKK+22] Haim Kaplan, Alexander Kauer, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth.  Dynamic connectivity in disk graphs.  In Proceedings of the 38th International Symposium on Computational Geometry (SoCG), volume 224 of LIPIcs, pages 49:1–49:17, 2022.  doi:10.4230/LIPICS.SOCG.2022.49.
  * [KLPS86] Klara Kedem, Ron Livne, János Pach, and Micha Sharir.  On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles.  Discret. Comput. Geom., 1:59–70, 1986.  doi:10.1007/BF02187683.
  * [KLR+23] Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese.  Online and dynamic algorithms for geometric set cover and hitting set.  In Proceedings of the 39th International Symposium on Computational Geometry (SoCG), volume 258 of LIPIcs, pages 46:1–46:17, 2023.  doi:10.4230/LIPICS.SOCG.2023.46.
  * [KR08] Subhash Khot and Oded Regev.  Vertex cover might be hard to approximate to within $2-\varepsilon$.  J. Comput. Syst. Sci., 74(3):335–349, 2008.  doi:10.1016/J.JCSS.2007.06.019.
  * [LPP15] Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie.  Improved distributed approximate matching.  J. ACM, 62(5):38:1–38:17, 2015.  doi:10.1145/2786753.
  * [LT80] Richard J. Lipton and Robert Endre Tarjan.  Applications of a planar separator theorem.  SIAM J. Comput., 9(3):615–627, 1980.  doi:10.1137/0209046.
  * [Mar05] Dániel Marx.  Efficient approximation schemes for geometric problems?  In Proceedings of the 13th Annual European Symposium on Algorithms (ESA), volume 3669 of Lecture Notes in Computer Science, pages 448–459. Springer, 2005.  doi:10.1007/11561071\\_41.
  * [MR10] Nabil H. Mustafa and Saurabh Ray.  Improved results on geometric hitting set problems.  Discret. Comput. Geom., 44(4):883–895, 2010.  doi:10.1007/S00454-010-9285-9.
  * [NTJ75] George L. Nemhauser and Leslie E. Trotter Jr.  Vertex packings: Structural properties and algorithms.  Mathematical Programming, 8(1):232–248, 1975.
  * [OR10] Krzysztof Onak and Ronitt Rubinfeld.  Maintaining a large matching and a small vertex cover.  In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 457–464. ACM, 2010.  doi:10.1145/1806689.1806753.
  * [OvL81] Mark H. Overmars and Jan van Leeuwen.  Maintenance of configurations in the plane.  J. Comput. Syst. Sci., 23(2):166–204, 1981.  doi:10.1016/0022-0000(81)90012-X.
  * [PS85] Franco P. Preparata and Michael I. Shamos.  Computational Geometry: An Introduction.  Springer, 1985.
  * [PS16] David Peleg and Shay Solomon.  Dynamic $(1+\varepsilon)$-approximate matchings: A density-sensitive approach.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 712–729, 2016.  doi:10.1137/1.9781611974331.CH51.
  * [Sol16] Shay Solomon.  Fully dynamic maximal matching in constant update time.  In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 325–334, 2016.  doi:10.1109/FOCS.2016.43.
  * [SW98] Warren D. Smith and Nicholas C. Wormald.  Geometric separator theorems & applications.  In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 232–243, 1998.  doi:10.1109/SFCS.1998.743449.
  * [Vaz94] Vijay V. Vazirani.  A theory of alternating paths and blossoms for proving correctness of the $O(\sqrt{V}E)$ general graph maximum matching algorithm.  Comb., 14(1):71–109, 1994.  doi:10.1007/BF01305952.
  * [Zuc07] David Zuckerman.  Linear degree extractors and the inapproximability of max clique and chromatic number.  Theory Comput., 3(1):103–128, 2007.  doi:10.4086/TOC.2007.V003A006.

##  Appendix A Minimum Vertex Cover: Fast Static Algorithms

###  A.1 Disks in $\mathbb{R}^{2}$

In this subsection, we give a static, near-linear-time,
$(1+O(\varepsilon))$-approximation algorithm $\mathcal{A}$ for MVC for disks
under the promise that $n=O(\mbox{\rm OPT})$. As we are aiming for a
$(1+O(\varepsilon))$-factor approximation, we may tolerate an additive error
of $O(\varepsilon n)$ because of the promise. MVC with $O(\varepsilon n)$
additive error reduces to MIS with $O(\varepsilon n)$ additive error, by
complementing the solution.

PTASs are known for MIS for disks, but allowing $O(\varepsilon n)$ additive
error, there are actually EPTASs that run in near linear time. For example, we
can adapt an approach by Chan [Cha03a] based on divide-and-conquer via
separators. Specifically, we can use the following variant of Smith and
Wormald’s geometric separator theorem [SW98]:

######  Lemma 7 (Smith and Wormald’s separator).

Given $n$ fat objects in a constant dimension $d$, there is an axis-aligned
hypercube $B$, such that the number of objects inside $B$ and the number of
objects outside $B$ are both at most $(1-\beta)n$ for some constant $\beta>0$
(dependent on $d$), and the objects intersecting $\partial B$ can be stabbed
by $O(n^{1-1/d})$ points. Furthermore, $B$ can be constructed in $O(n)$ time.

###### Proof.

(The following is a modification of a proof in [CH24], which is based on Smith
and Wormald’s original proof [SW98].)

For each object, first pick an arbitrary “reference” point inside the object.
Let $B_{0}$ be the smallest hypercube that contains at least
$\frac{n}{2^{d}+1}$ reference points. Let $r$ be the side length of $B_{0}$.
Let $h$ be a parameter to be set later. For each
$t\in\\{\frac{1}{h},\frac{2}{h},\ldots,\frac{h-1}{h}\\}$, let $B_{t}$ be the
hypercube with a scaled copy of $B_{0}$ with the same center and side length
$(1+t)r$. Since $B_{t}$ can be covered by $2^{d}$ quadtree boxes of side
length $<r$, the number of reference points inside $B_{t}$ is at most
$\frac{2^{d}n}{2^{d}+1}$.

An object of diameter $\leq r/h$ intersects $\partial B_{t}$ for at most
$O(1)$ choices of $t$. Thus, we can find a value $t$ in $O(n)$ time such that
$\partial B_{t}$ intersects $O(n/h)$ objects of diameter $\leq r/h$. On the
other hand, the objects of diameter $>r/h$ intersecting $\partial B_{t}$ can
all be stabbed by $O(h^{d-1})$ points, because of fatness. Set $h=n^{1/d}$,
and $B_{t}$ satisfies the desired properties with
$\beta=\frac{2^{d}}{2^{d}+1}$.

One remaining issue is how to find $B_{0}$ quickly. Let $C$ be a sufficiently
large constant. Form a $C\times\cdots\times C$ grid, so that the number of
reference points between any two consecutive parallel grid hyperplanes is
$n/C$. This takes $O(Cn)$ time by a linear-time selection algorithm. Round
each reference point to its nearest grid point. The rounded point set is a
multiset with $O(C^{d})$ distinct elements. Redefine $B_{0}$ as the smallest
hypercube that contains at most $\frac{n}{2^{d}+1}$ rounded reference points
(multiplicity included), which can now be computed in $C^{O(1)}$ time. For any
box, the number of reference points inside the box changes by at most $O(n/C)$
after rounding. So, we just need to increase $\beta$ by $O(1/C)$. ∎

The MIS algorithm is simple: we just recursively compute an independent set
for the disks inside $B$ and an independent set for the disks outside $B$, and
take the union of the two sets. If $n$ is below a constant $b$, we solve the
problem exactly by brute force in $2^{O(C)}$ time. (This is analogous to
Lipton and Tarjan’s original EPTAS for independent set for planar graphs
[LT80].)

Since the optimal independent set can have at most $O(\sqrt{n})$ disks
intersecting $\partial B$, the total additive error satisfies a recurrence of
the form

$E(n)\leq\left\\{\begin{array}[]{ll}\max_{n_{1},n_{2}\leq(1-\beta)n:\
n_{1}+n_{2}\leq n}(E(n_{1})+E(n_{2})+O(\sqrt{n}))&\mbox{if $n\geq b$}\\\
0&\mbox{if $n<b$.}\end{array}\right.$

This yields $E(n)=O(n/\sqrt{b})$. We set $b=1/\varepsilon^{2}$. The running
time of the resulting static algorithm $\mathcal{A}$ is
$T(n)=\widetilde{O}(2^{O(1/\varepsilon^{2})}n)$.

###  A.2 Rectangles in $\mathbb{R}^{2}$

In this subsection, we give a static, near-linear-time,
$(\frac{3}{2}+O(\varepsilon))$-approximation algorithm for MVC for rectangles,
by adapting Bar-Yehuda, Hermelin, and Rawitz’s previous, polynomial-time,
$(\frac{3}{2}+O(\varepsilon))$-approximation algorithm [BYHR11].

#### Triangle-free case.

We first start with the case when the intersection graph is triangle-free, or
equivalently, when the maximum depth of the rectangles is at most 2. (The
depth of a point $q$ among a set of rectangles refers to the number of
rectangles containing $q$; the maximum depth refers to the maximum over all
$q\in\mathbb{R}^{2}$.)

We will design a static algorithm $\mathcal{A}$ for MVC for rectangles, under
the promise that $n\leq(2+O(\varepsilon))\,\mbox{\rm OPT}$.

We say that a rectangle $r$ _dominates_ another rectangle $r^{\prime}$ if
$\partial r$ intersects $\partial r^{\prime}$ four times, with $r$ having
larger height than $r^{\prime}$. Bar-Yehuda, Hermelin, and Rawitz’s algorithm
proceeds as follows:

  1. 1.

Decompose $R$ into 2 subsets $R_{1}$ and $R_{2}$, such that there are no
dominating pairs within each subset $R_{i}$.

The existence of such a decomposition follows easily from Dilworth’s theorem,
but for an explicit construction, we can just define $R_{1}$ to contain all
rectangles in $R$ that are not dominated by any other rectangle in $R$, and
define $R_{2}$ to be $R\setminus R_{1}$. Correctness is easy to see (since the
maximum depth is 2).

We can compute $R_{1}$ (and thus $R_{2}$) by performing $O(n)$ orthogonal
range queries, after lifting each rectangle to a point in $\mathbb{R}^{4}$. In
fact, computing $R_{1}$ corresponds to the _maxima_ problem in
$\mathbb{R}^{4}$, for which $O(n\log n)$-time algorithms are known [CLP11].

  2. 2.

For each $i\in\\{1,2\\}$, compute a vertex cover $S_{i}$ of $R_{i}$ which
approximates the minimum with additive error at most $\varepsilon n$.

Since we tolerate $\varepsilon n$ additive error, it suffices to approximate
the MIS of $R_{i}$ with $\varepsilon n$ additive error.

Because $R_{i}$ has no dominating pairs, it forms a _pseudo-disk_ arrangement
(each pair intersects at most twice). It is known [BYHR11, KLPS86] that the
intersection graph of any set of pseudo-disks that have maximum depth 2 and
have no containment pair is in fact planar. (We can easily eliminate
containment pair, by removing rectangles that contain another rectangle; and
we can detect such rectangles again by orthogonal range queries.) So, we can
use known near-linear-time EPTAS for MIS for planar graphs; for example,
Lipton and Tarjan’s divide-and-conquer algorithm via planar-graph separators
runs in $\widetilde{O}(2^{O(1/\varepsilon^{2})}n)$ time [LT80].

  3. 3.

Return $S$, the smaller of the two sets: $S_{1}\cup R_{2}$ and $S_{2}\cup
R_{1}$.

Let $S^{*}$ be the minimum vertex cover. Then

$\displaystyle|S|$ $\displaystyle\leq$
$\displaystyle\tfrac{1}{2}(|S_{1}|+|R_{2}|+|S_{2}|+|R_{1}|)$
$\displaystyle\leq$ $\displaystyle\tfrac{1}{2}(|S^{*}\cap R_{1}|+|S^{*}\cap
R_{2}|+|R_{1}|+|R_{2}|)+\varepsilon n\ =\ \tfrac{1}{2}(|S^{*}|+n)+\varepsilon
n\ \leq\ (\tfrac{3}{2}+O(\varepsilon))|S^{*}|$

under the assumption that $n\leq(2+O(\varepsilon))|S^{*}|$. The running time
is $T(n)=\widetilde{O}(2^{O(1/\varepsilon^{2})}n)$.

At this point, if we apply Theorem 1 with $c=\frac{3}{2}+O(\varepsilon)$,
$\gamma=\varepsilon$, and $\delta=\varepsilon^{3}$ (and
$\tau_{0}(n)=O(\log^{O(1)}n)$ as noted in Section 2.4), we obtain:

######  Corollary 10.

There is a dynamic data structure for $n$ rectangles in $\mathbb{R}^{2}$ that
maintains a $(\frac{3}{2}+O(\varepsilon))$-approximation of the minimum vertex
cover of the intersection graph, under insertions and deletions, in
$O(2^{O(1/\varepsilon^{2})}\log^{O(1)}n)$ amortized time, under the assumption
that the intersection graph is triangle-free.

#### General case.

We now design our final static algorithm $\mathcal{A}$ for MVC for rectangles
that avoids the triangle-free assumption, again by building on Bar-Yehuda,
Hermelin, and Rawitz’s approach:

  1. 1.

Remove vertex-disjoint triangles $T_{1},\ldots,T_{\ell}$ so that the remaining
set $R^{\prime}:=R\setminus(T_{1}\cup\cdots\cup T_{\ell})$ is triangle-free.

We can implement this step greedily in polynomial time, but a faster approach
is via a plane sweep. Namely, we modify the standard sweep-line algorithm to
computing the maximum depth of $n$ rectangles in $\mathbb{R}^{2}$ (similar to
Klee’s measure problem) [PS85]. The algorithm uses a data structure for a 1D
problem: maintaining the maximum depth of intervals in $\mathbb{R}^{1}$,
subject to insertions and deletions of intervals. Simple modification of
standard search trees achieve $O(\log n)$ time per insertion and deletion. As
we sweep a vertical line $\ell$ from left to right, we maintain the maximum
depth of the $y$-intervals of the rectangles intersected by $\ell$. When
$\ell$ hits the left side of a rectangle, we insert an interval. When $\ell$
hits the right side of a rectangle, we delete an interval. When the maximum
depth becomes 3, we remove the 3 intervals containing the maximum-depth point,
which correspond to a triangle in the intersection graph, and continue the
sweep. The total time is $O(n\log n)$.

  2. 2.

Compute a vertex cover $S^{\prime}$ of $R^{\prime}$ which is a
$(\frac{3}{2}+O(\varepsilon))$-approximation to the minimum. This can be done
by Corollary 10 in $\widetilde{O}(2^{O(1/\varepsilon^{2})}n)$ time (we
actually don’t need the full power of a dynamic data structure, since we just
want a static algorithm for this step).

  3. 3.

Return $S=S^{\prime}\cup T$ with $T:=T_{1}\cup\cdots\cup T_{\ell}$.

Let $S^{*}$ be the minimum vertex cover. The key observation is that $S^{*}$
must contain at least 2 of the 3 vertices in each triangle $T_{i}$, and so
$|S^{*}\cap T|\geq\frac{2}{3}|T|$. Thus,

$|S|\ =\ |S^{\prime}|+|T|\ \leq\ (\tfrac{3}{2}+O(\varepsilon))|S^{*}\cap
R^{\prime}|+\tfrac{3}{2}|S^{*}\cap T|\ \leq\
(\tfrac{3}{2}+O(\varepsilon))|S^{*}|.$

The running time of our final static algorithm $\mathcal{A}$ is
$T(n)=\widetilde{O}(2^{O(1/\varepsilon^{2})}n)$.