Conditional Lower Bounds for Dynamic Geometric Measure Problems
Open Access
- 30 April 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (2) , 1-35
Abstract
We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word RAM model, conditioned on the hardness of 3SUM, APSP, or the Online Matrix-Vector Multiplication problem [Henzinger et al., STOC 2015]. In particular, we get lower bounds in the incremental and fully dynamic settings for counting maximal or extremal points in \(\mathbb{R}^{3}\) , different variants of Klee’s Measure Problem, problems related to finding the largest empty disk in a set of points, and querying the size of the i th convex layer in a planar set of points. We also answer a question of Chan et al. [SODA 2022] by giving a conditional lower bound for dynamic approximate square set cover. While many conditional lower bounds for dynamic data structures have been proven since the seminal work of Pătraşcu [STOC 2010], few of them relate to computational geometry problems. This is the first article focusing on this topic. Most problems we consider can be solved in \(O(n\log n)\) time in the static case, and their dynamic versions have only been approached from the perspective of improving known upper bounds. One exception to this is Klee’s measure problem in \(\mathbb{R}^{2}\) , for which Chan [CGTA 2010] gave an unconditional \(\Omega(\sqrt{n})\) lower bound on the worst-case update time in a variant of the Word RAM machine with large words. By a similar approach, we show that such a lower bound also holds for an important special case of Klee’s measure problem in \(\mathbb{R}^{3}\) known as the Hypervolume Indicator problem, even for amortized runtime in the incremental setting.
Keywords
All Related Versions
Funding Information
- FRIA
- Fonds De La Recherche Scientifique-FNRS (MISU F 6001 1)
This publication has 36 references indexed in Scilit:
- Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry2021
- Dynamic Geometric Data Structures via Shallow CuttingsDiscrete & Computational Geometry, 2020
- Mind the Gap!Algorithmica, 2018
- Fast and Simple Connectivity in Graph Timelines2015
- On Hardness of Jumbled Indexing2014
- Bringing Order to Special Cases of Klee’s Measure Problem2013
- The Union of Probabilistic Boxes: Maintaining the VolumeLecture Notes in Computer Science, 2011
- Subquadratic Algorithms for 3SUMAlgorithmica, 2007
- Lower Bounds for Dynamic Algebraic ProblemsInformation and Computation, 2001
- Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and DynamizationJournal of Algorithms, 1995