Beyond 3SUM-Hardness for Geometric Problems

Introduction

Even before “fine-grained complexity” became a field with a name, Gajentaan and Overmars [21] established some of its very first conditional lower bounds. Their starting point was the 3SUM Hypothesis, which postulated that no algorithm can decide in time $O(n^{2-\varepsilon})$ (for any constant $\varepsilon> 0$) whether a given set of $n$ numbers contains a solution to $a+b=c$. From this assumption, they derived quadratic-time lower bounds for a diverse set of geometric problems: detecting three collinear points, finding separating lines, covering, visibility and motion planning problems, and many more. Follow-up work kept adding to this list [15, 2, 11, 18, 4, 9, 26, 3, 17, 12, 5, 13, 10, 23, 19, 20, 1 BFK+26, 24]. Part of the appeal of these lower bounds is their simplicity: most of the reductions are elementary and can be explained with a single picture. Unsurprisingly, they have become standard material in courses on fine-grained complexity, where they are often among the very first lower bounds that students encounter.

But recently, fine-grained complexity witnessed a spectacular breakthrough: Alman and Vassilevska Williams [6] gave a truly subquadratic algorithm for 3SUM, thereby refuting the 3SUM Hypothesis. At the same time and based on the same new technique, the APSP Hypothesis was refuted as well.¹ As a consequence, a large body of conditional lower bounds based on these two hypotheses has become vacuous. The reductions themselves of course remain correct, but a reduction from 3SUM or APSP no longer constitutes evidence that a problem is hard. For algorithm design, this is good news: the complexity of the many 3SUM- or APSP-hard problems is now open, and for each of them we may hope for a polynomially faster algorithm. But at the same time, many of these problems will likely remain hard for other reasons. Sorting out which is which, either by designing faster algorithms or by restoring hardness results under other credible hypotheses, will be an important task for the fine-grained complexity community now.

In this note we point out that, for many geometric problems, this task is surprisingly easy: many of the classical 3SUM-based lower bounds remain valid, with essentially unchanged proofs, under a different hardness assumption from fine-grained complexity, the $k$-AP Hypothesis [DFG+26]. The observation is simple, and we make no claim of technical depth. The reason for writing this note is more practical: several colleagues I talked to are teaching courses on fine-grained complexity this semester, and many of the lower bounds they had planned to cover have disappeared overnight. This note offers a way to keep many lower bounds for geometric problems on the syllabus, with only small changes. We hope that it will be useful to anyone teaching fine-grained complexity, now or in the future.

Arithmetic Progression Detection. A $k$-term arithmetic progression (or $k$-AP for short) is a sequence of numbers of the form $a, a+d, a+2d, \ldots, a+(k-1)d$; we call it nontrivial if $d \ne0$. In the $k$-AP Detection problem the task is to decide whether a given set $A \subseteq\{1,\ldots,N\}$ contains a nontrivial $k$-AP. (Note that $N$ bounds the universe, and not just the size of $A$.) The trivial algorithm enumerates the first two terms $a,a+d \in A$ and tests whether the remaining $k-2$ terms are present in $A$, in total time $O(N^2)$. For $k=3$ there is a much faster $O(N \log N)$-time algorithm based on the Fast Fourier Transform. For $k \ge4$, however, no polynomial improvement over the trivial algorithm is known, which motivated the following hypothesis for all constants $k \ge4$ [DFG+26].

As argued before, the smallest interesting case is $k=4$. Moreover, it is known that the $k$-AP Hypothesis implies the $(k+1)$-AP Hypothesis [DFG+26], and so the $4$-AP Hypothesis is the strongest member of this family. The lower bounds in this note hold even under the weakest one: it suffices that the $k$-AP Hypothesis holds for some constant $k \ge4$.

Why should we believe in the $k$-AP Hypothesis, especially now that 3SUM has been refuted? First, let us take a step back. Fine-grained complexity has never been about hardness for its own sake. Its ultimate goal is to find the fastest possible algorithm for every problem, and its hypotheses serve as signposts that tell us where not to look: as long as a problem is hard under some hypothesis, any faster algorithm for it would refute the hypothesis, so there is little point in attacking the problem directly while the hypothesis stands. In this view, whether a hypothesis is ultimately true is less important than whether it faithfully marks the limits of our current algorithmic techniques. Read in this way, this note puts many of the signposts for geometric problems back in place: whoever hopes to solve one of these problems faster should first find a faster algorithm for detecting arithmetic progressions. Second, there is good reason to trust this particular signpost: despite the problem’s natural appeal and its close connection to additive combinatorics, the fastest known algorithms for $k$-AP Detection improve upon the trivial running time by merely subpolynomial factors [DFG+26, Section 5].³ Third, the recent breakthrough [6] does not seem to extend to 4-APs easily. At its core, their algorithm is still a Strassen-like algebraic algorithm. Algorithms of this type are tailored to trilinear problems, such as matrix multiplication or 3-AP Detection. In contrast, 4-AP Detection is inherently a 4-linear problem, and to the best of our knowledge Strassen-like techniques have so far never been extended to 4-linear problems in a nontrivial way. See [DFG+26, Section 5] for a more detailed discussion of the $k$-AP Hypothesis.

Geometric Problems. Let us finally return to the geometric problems. Gajentaan and Overmars [21] routed most of their reductions through an intermediate problem called GeomBase: Given $n$ points with integer coordinates on the three horizontal lines $y=0$, $y=1$ and $y=2$, is there a non-horizontal line that contains three of the points? GeomBase is merely 3SUM in disguise (the points $(a,0)$, $(c,1)$ and $(b,2)$ are collinear if and only if $a+b=2c$ [21 Theorem 3.2]), but its geometric formulation makes it a convenient starting point for further reductions. In the same spirit, we consider the following natural generalization from three to $k$ lines.

See Figure 1 for an example. Just as GeomBase is a reformulation of 3SUM, $k$-GeomBase is a reformulation of $k$-AP Detection: $k$ points $(a_1,1),\ldots,(a_k,k)$ lie on a common line if and only if $a_1,\ldots,a_k$ form a $k$-AP. In particular, the following lemma is immediate.

Image not extracted

Proof. Let $A$ be the given $k$-AP instance. We randomly partition $A$ into sets $A_1,\ldots,A_k$ (we apply “color coding”). Then construct the $k$-GeomBase instance

Whenever there are $k$ points $(a_1,1),\ldots,(a_k,k) \in P$ that lie on a shared line, the integers $a_1,\ldots,a_k$ are equispaced and thus form a $k$-AP in $A$. Since $a_1,\ldots,a_k$ are pairwise distinct (by color coding), the $k$-AP is nontrivial. Conversely, suppose that there is a nontrivial $k$-AP $a_1,\ldots,a_k \in A$. With constant probability we color it correctly, $(a_1,\ldots,a_k) \in A_1 \times\cdots\times A_k$, and in that event $P$ has the solution $(a_1,1),\ldots,(a_k,k)$. The color coding technique can be derandomized using standard tools [7].

The simple observation of this note is that all reductions via GeomBase that we are aware of work just as well when starting from $k$-GeomBase. Intuitively, the number of lines never plays any role in these reductions. The typical construction turns each of the horizontal lines into a wall of horizontal segments that leaves small holes precisely at the given points [21 Theorem 5.1]. The object in question (a separating line, a line of sight, a rod moving from one side to the other, and so on) must then pass through a hole in every wall, and this is possible if and only if some non-horizontal line hits a point on each of the original lines. Whether there are three walls or four or $k$ is irrelevant for this argument. Collecting the problems that were shown to be 3SUM-hard via GeomBase in [21, 15, 11, 3 BFK+26], we thus obtain the following Theorem 1.4.

• Triangles Cover a Triangle: Given $n$ triangles and a designated triangle $t$ in the plane, decide whether the $n$ triangles cover $t$ [21 Theorem 6.2].

• Hole in a Union of Triangles: Given $n$ triangles in the plane, decide whether their union has a hole [21 Theorem 6.3].

• Area of a Union of Triangles: Given $n$ triangles in the plane, compute the area of their union [21 Theorem 6.5].

• Maximum Depth of Halfplanes: Given $n$ halfplanes and an integer $t$, decide whether some point lies in at least $t$ of them [21 Theorem 6.6].

• Visibility Between Two Segments: Given $n$ horizontal segments and two further horizontal segments $s$, $s'$ in the plane, decide whether some point on $s$ sees some point on $s'$ [21 Theorem 7.1].

• Visibility of a Segment from Infinity: Given $n$ axis-parallel segments and a horizontal segment $s$ in the plane, decide whether some ray starting on $s$ avoids all other segments [21 Theorem 7.2].

• Visibility of a Triangle from a Point in 3D: Given $n$ horizontal triangles, a horizontal triangle $t$ and a point $p$ in $\mathbb{R}^3$, decide whether $p$ sees some point of $t$ [21 Theorem 7.3].

• Planar Motion Planning for a Rod: Given $n$ disjoint axis-parallel segments in the plane, decide whether a rod can be moved (by translations and rotations) between two given placements while avoiding the segments [21 Theorem 8.1].

• Translational Motion Planning for a Vertical Rod in 3D: Given $n$ disjoint horizontal triangles in $\mathbb{R}^3$, decide whether a vertical rod can be translated between two given positions while avoiding the triangles [21 Theorem 8.2].

• Perfect BSP for Disjoint Planar Segments: Given $n$ pairwise disjoint line segments in the plane, decide whether a binary space partition can recursively split cells by lines, without cutting any input segment, until each leaf cell contains at most one segment [15].

• One-Fillability of a Polyhedral Mold: Given a polyhedron of complexity $n$, decide whether there is an orientation in which it can be filled through a single opening without trapping air [11].

• Narrowest Color-Spanning Strip: Given $n$ colored points in the plane, compute the narrowest strip that contains a point of every color [4].

• Cardinality of the Distant-Horizon Edge Set: Given a piecewise-linear terrain with $n$ edges, count the edges that appear on its distant horizon (its upper silhouette under horizontal parallel projection) for some viewing direction [3].

• Stabbing and Avoiding Segments: Given $n$ segments in the plane, partitioned into sets $S$ and $A$, decide whether some line intersects all segments in $S$ and avoids all segments in $A$ [BFK+26].

• Double-Wedge Intersection: Given $n$ double-wedges in the plane, decide whether they have a common point [BFK+26].

We omit the proofs, as each item follows trivially by inspecting the reduction in the respective reference and starting from $k$-GeomBase instead of GeomBase. In § 2 we work out one example in detail.

Beyond GeomBase. Not all 3SUM-based hardness proofs for geometric problems go through GeomBase, e.g. [21 AHH+98, Erı̈99, 9 SEQ03, 17 CHEP07, 5, 13, 10, 23, 19, 20, 1], and those that do are not covered by this note. An important example with a direct reduction from 3SUM is the problem of detecting three collinear points among $n$ points in the plane [21 Theorem 4.1].

Example: Planar Motion Planning

To illustrate how the lower bounds in Theorem 1.4 are obtained, let us work out one example in detail: planar motion planning. Imagine a robot that is supposed to navigate through an environment of obstacles. In a classical geometric model, the robot is a convex polygon of constant complexity in the plane, and the $n$ obstacles are line segments. Given a start placement and a goal placement of the robot, the task is to decide whether the robot can move from the start to the goal, by translations and rotations, without ever colliding with an obstacle.

This classical problem can be solved in near-quadratic time $\widetilde{O}(n^2)$ [27, 14, 22]. Gajentaan and Overmars [21] showed that any polynomial improvement would refute the 3SUM Hypothesis, even if the robot is a rod and the obstacles are disjoint axis-parallel segments. Their reduction works equally well when starting from $k$-GeomBase, which yields the following special case of Theorem 1.4.

Proof. Fix a constant $k \ge4$, and let $P \subseteq\mathbb{Z} \times\{1,\ldots,k\}$ be a $k$-GeomBase instance consisting of $n$ points. By shifting, we may assume that all $x$-coordinates lie in $\{1,\ldots,X\}$ for some integer $X$. We construct the following environment of obstacles; see Figure 2.

Image not extracted

The core of the construction consists of $k$ horizontal walls, where the $i$-th wall lies at height $y=i$. Into each wall we cut a small hole $(a-\frac{1}{4},a+\frac{1}{4}) \times\{i\}$ for every point $(a,i) \in P$. The inner walls $2,\ldots,k-1$ span a narrow chamber $[0,X+1] \times[1,k]$ whose left and right sides are closed by vertical segments. The first and the $k$-th wall extend beyond the chamber and form the ceiling of a large bottom room and the floor of a large top room, respectively. The robot is a rod whose length $L$ exceeds the diagonal of the chamber, and both rooms have width and height at least $3L$, say, so that the rod can move and rotate freely within each room. The task is to move the rod from a start placement in the middle of the top room to a goal placement in the middle of the bottom room.⁴ In total, the environment consists of $O(n)$ segments and can be constructed in time $O(n \log n)$.

If some non-horizontal line $\ell$ hits $k$ points of $P$, then $\ell$ passes through a hole in every wall. Hence, we can move the rod onto $\ell$ within the top room, slide it along $\ell$ through all $k$ holes into the bottom room, and finally move it to its goal placement. Conversely, since the rod is longer than the diagonal of the chamber, at every moment of a collision-free motion it reaches into the top room or into the bottom room. By continuity, at some moment it reaches into both rooms, and thus passes through one hole in every wall. As the holes are narrow and centered at integer coordinates, this is only possible if the corresponding $k$ points of $P$ are collinear (as in [21 Theorem 5.1]). This proves that the reduction is correct.

All in all, an $O(n^{2-\varepsilon})$-time algorithm for planar motion planning would solve $k$-GeomBase in time $O(n^{2-\varepsilon})$ and thereby refute the $k$-AP Hypothesis by Lemma 1.3.

AI Disclosure

I used Claude Opus 5.5 and ChatGPT Astra 6 to assist with the write-up, the generation of figures, and the search for references, but not for any of the mathematical ideas.