Worst-Case Efficient Dynamic Geometric Independent Set

DOI10.4230/LIPICS.ESA.2021.25MaRDI QIDQ6075911zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, John Iacono, Grigorios Koumoutsos

Publication date 20 September 2023

Full work available at URL https://arxiv.org/abs/2108.08050

zbMATH Keywords

approximationdeamortizationmaximum independent set

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present data structures that maintain a constant-factor approximate maximum independent set for broad classes of fat objects in $d$ dimensions, where $d$ is assumed to be a constant, in sublinear extit{worst-case} update time. This gives the first results for dynamic independent set in a wide variety of geometric settings, such as disks, fat polygons, and their high-dimensional equivalents. Our result is obtained via a two-level approach. First, we develop a dynamic data structure which stores all objects and provides an approximate independent set when queried, with output-sensitive running time. We show that via standard methods such a structure can be used to obtain a dynamic algorithm with extit{amortized} update time bounds. Then, to obtain worst-case update time algorithms, we develop a generic deamortization scheme that with each insertion/deletion keeps (i) the update time bounded and (ii) the number of changes in the independent set constant. We show that such a scheme is applicable to fat objects by showing an appropriate generalization of a separator theorem. Interestingly, we show that our deamortization scheme is also necessary in order to obtain worst-case update bounds: If for a class of objects our scheme is not applicable, then no constant-factor approximation with sublinear worst-case update time is possible. We show that such a lower bound applies even for seemingly simple classes of geometric objects including axis-aligned rectangles in the plane.

Cited in

(7)

• On streaming algorithms for geometric independent set and clique
• New partitioning techniques and faster algorithms for approximate interval scheduling
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Conditional lower bounds for dynamic geometric measure problems
• Conditional lower bounds for dynamic geometric measure problems
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Dynamic streaming algorithms for geometric independent set

This page was built for publication: Worst-Case Efficient Dynamic Geometric Independent Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075911)