Source-linked AI summary
Beyond 3SUM-Hardness for Geometric Problems
Nick Fischer
TL;DR
The refutation of the 3SUM Hypothesis left many geometric lower bounds without their previous hardness foundation. This note adapts GeomBase reductions to k-GeomBase and uses the k-AP Hypothesis to recover lower bounds for many of those problems. The resulting proofs require only small changes to the original reductions.
Problem
The refutation of the 3SUM Hypothesis made many geometric lower bounds based on it vacuous, leaving their complexity open.
Source: §1 · p. 1Method
The note generalizes GeomBase to k lines and adapts reductions through it, using the equivalence between collinear points and arithmetic progressions.
Source: §1 · pp. 2–3Results
Under the k-AP Hypothesis for all constants k ≥4, the listed geometric problems cannot be solved in O(n^(2−ε)) time for any constant ε > 0.
Source: §1 · p. 3Takeaways & Limitations
Many classical geometric lower bounds can be retained under the k-AP Hypothesis with essentially unchanged proofs.
Source: §1 · p. 1The note covers only geometric hardness proofs routed through GeomBase; reductions that do not use it, including direct 3SUM reduction for three-collinear-points detection, are excluded.
Source: §1 · p. 4
Abstract
from arXiv · showhide
Since the early days of fine-grained complexity, many geometric problems have been shown to require quadratic time under the 3SUM Hypothesis. But as the 3SUM Hypothesis was recently refuted, these lower bounds have lost their foundation. In this note we point out that many of them can be recovered under an alternative hardness assumption, the $k$-AP Hypothesis. The required changes to the proofs are trivial, so the lower bounds remain just as easy to teach.
1 Introduction
After the 3SUM Hypothesis was refuted, many geometric lower bounds lost their foundation; this note recovers a broad family under the k-AP Hypothesis using essentially unchanged reductions. Its central observation is that the GeomBase reductions still work when their starting problem is generalized from three lines to k lines.
1 Introduction
- The motivation is that the refuted 3SUM Hypothesis made many conditional lower bounds vacuous, while no polynomial improvement over the trivial algorithm for k-AP Detection is known for k ≥4.The note presents k-AP as a signpost for geometric problems and observes that the breakthrough for 3SUM does not seem to extend easily to 4-AP.Source: §1 · pp. 1–2
- In k-GeomBase, k points on k horizontal lines must lie on a common non-horizontal line, which occurs exactly when their x-coordinates form a k-term arithmetic progression.The construction from k-AP Detection uses color coding to place progression terms on distinct lines; a nontrivial progression yields a solution with constant probability.Source: §1 · pp. 2–3
- The transfer works because the typical reduction turns each horizontal line into a wall with holes, and the geometric object must pass through a hole in every wall.The number of walls does not affect this argument.Source: §1 · p. 3
- Under the k-AP Hypothesis for all constants k ≥4, the note establishes quadratic-time lower bounds for a broad set of geometric problems.Examples include separating axis-parallel segments and covering problems involving strips, rectangles, and triangles.Source: §1 · pp. 3–4
- The lower-bound list also includes holes and union area of triangles, maximum halfplane depth, and several visibility problems.The visibility examples cover pairs of segments, a segment viewed from infinity, and a triangle viewed from a point in 3D.Source: §1 · p. 4
- Further covered problems include rod motion planning, perfect BSP for disjoint segments, mold fillability, and narrowest color-spanning strips.The list also includes counting distant-horizon edges.Source: §1 · p. 4
- The list extends to stabbing and avoiding segments and double-wedge intersection.The proofs are omitted because the cited reductions can be inspected with k-GeomBase as the starting problem.Source: §1 · p. 4
- The note covers only 3SUM-based geometric hardness proofs routed through GeomBase; direct reductions such as three-collinear-points detection are outside its scope.The authors describe the proof changes as trivial and say the note is intended to preserve teachable lower bounds.Source: §1 · pp. 1, 4
2 Example: Planar Motion Planning
The example reduces k-GeomBase to planar rod motion: walls encode points as holes, and a rod can cross the chamber exactly when the corresponding points are collinear. This yields a conditional quadratic-time lower bound under the k-AP Hypothesis.
2 Example: Planar Motion Planning
- The classical problem has a near-quadratic-time algorithm, and earlier work showed a polynomial improvement would refute the 3SUM Hypothesis, even for a rod and disjoint axis-parallel segments.The reduction from k-GeomBase gives the conditional lower bound stated in Theorem 2.1.Source: §2 · p. 5
- Planar motion planning for a rod among n disjoint axis-parallel segments requires quadratic time under the k-AP Hypothesis, unless it fails for all constants k ≥4.The theorem rules out O(n^2−ϵ) time for any constant ϵ > 0.Source: §2 · p. 5
- The construction places k horizontal walls with holes for input points around a chamber the rod must cross between two large rooms.The rod is longer than the chamber diagonal, so it reaches into one or both rooms throughout the motion.Source: §2 · p. 5
- The obstacle environment has O(n) segments and can be constructed in O(n log n) time.Source: §2 · p. 6
- A non-horizontal line through k points yields a rod path through every wall, while any collision-free crossing forces the corresponding points to be collinear.The holes are narrow and centered at integer coordinates, which enforces collinearity.Source: §2 · p. 6
AI Disclosure
The author used Claude Opus 5.5 and ChatGPT Astra 6 for writing, figures, and reference search, but not for mathematical ideas.
AI Disclosure
- Claude Opus 5.5 and ChatGPT Astra 6 assisted with the write-up, figure generation, and reference search, but not the mathematical ideas.Source: AI Disclosure · p. 6