
arXiv: 2112.10095
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.
Computational Geometry (cs.CG), FOS: Computer and information sciences, Dynamic data structures, Data structures, Fine-grained complexity, Généralités, dynamic data structures, Théorie des algorithmes, Computational geometry, 004, fine-grained complexity, Computer graphics; computational geometry (digital and algorithmic aspects), computational geometry, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Computer Science - Computational Geometry, ddc: ddc:004
Computational Geometry (cs.CG), FOS: Computer and information sciences, Dynamic data structures, Data structures, Fine-grained complexity, Généralités, dynamic data structures, Théorie des algorithmes, Computational geometry, 004, fine-grained complexity, Computer graphics; computational geometry (digital and algorithmic aspects), computational geometry, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Computer Science - Computational Geometry, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
