  We present fully dynamic approximation algorithms for the Maximum Independent
Set problem on several types of geometric objects: intervals on the real line,
arbitrary axis-aligned squares in the plane and axis-aligned $d$-dimensional
hypercubes.
  It is known that a maximum independent set of a collection of $n$ intervals
can be found in $O(n\log n)$ time, while it is already \textsf{NP}-hard for a
set of unit squares. Moreover, the problem is inapproximable on many important
graph families, but admits a \textsf{PTAS} for a set of arbitrary pseudo-disks.
Therefore, a fundamental question in computational geometry is whether it is
possible to maintain an approximate maximum independent set in a set of dynamic
geometric objects, in truly sublinear time per insertion or deletion. In this
work, we answer this question in the affirmative for intervals, squares and
hypercubes.
  First, we show that for intervals a $(1+\varepsilon)$-approximate maximum
independent set can be maintained with logarithmic worst-case update time. This
is achieved by maintaining a locally optimal solution using a constant number
of constant-size exchanges per update.
  We then show how our interval structure can be used to design a data
structure for maintaining an expected constant factor approximate maximum
independent set of axis-aligned squares in the plane, with polylogarithmic
amortized update time. Our approach generalizes to $d$-dimensional hypercubes,
providing a $O(4^d)$-approximation with polylogarithmic update time.
  Those are the first approximation algorithms for any set of dynamic arbitrary
size geometric objects; previous results required bounded size ratios to obtain
polylogarithmic update time. Furthermore, it is known that our results for
squares (and hypercubes) cannot be improved to a
$(1+\varepsilon)$-approximation with the same update time.

Data Structures and Algorithms;Computational Geometry