Shortest paths in line arrangements

Definitions and mathematical statement

Let $\mathcal L=\{\ell_1,\ldots,\ell_n\}$ be a finite family of lines in $\mathbb R^2$. Its arrangement has as vertices the intersection points of distinct nonparallel lines; along each line, consecutive vertices are joined by an arrangement edge. Unbounded rays do not help a finite path between two vertices. Let $s,t$ be designated arrangement vertices. An admissible path follows arrangement edges, changing lines only at arrangement vertices.

Under the usual geometric-length interpretation, give an edge $uv$ weight $|u-v|$, its Euclidean length. The output is an $s$-to-$t$ path minimizing the sum of these edge weights. The source asks for an algorithm whose worst-case running time is subquadratic in the number $n$ of input lines, or a quadratic worst-case lower bound for this task. On the reading "subquadratic" means $o(n^2)$, the alternatives are an exact algorithm with time $T(n)=o(n^2)$, or a proof that every algorithm in a specified computational model has worst-case time $\Omega(n^2)$.

The input is the lines and designated vertices, not an already explicitly constructed graph with potentially quadratic size; charging for an explicit full arrangement would change the question. No general-position assumption appears in the source: parallel lines and multiple lines through one vertex are not silently excluded. Coincident-line representations and degeneracies need an input convention.

The source does not expressly specify Euclidean edge length versus number of edges, the computational model or coordinate representation, whether the output is the distance or a full path, or whether "subquadratic" requires a bound $O(n^{2-\varepsilon})$ for some fixed $\varepsilon>0$. These choices matter for a precise algorithmic or lower-bound theorem; the formulation above is explicitly conditional on the natural geometric reading. The supplied research summary reports no verified subquadratic algorithm or quadratic lower bound in the general case. That is a registry assessment, while the original pages warn that they have not been systematically updated since 2001.

Short English statement

Given $n$ planar lines and two arrangement vertices, compute a shortest path using only arrangement edges in subquadratic time, or prove a quadratic lower bound. The usual Euclidean-length reading is stated explicitly; a precise complexity claim still needs a computational model and input/output conventions.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $3800015$, source code catalogue entry; supplied statement, background, and research summary, updated 2026-08-06. Attribution: Jeff Erickson and cited proposers.
• Jeff Erickson, Open Problems in Computational Geometry, "Shortest paths in line arrangements": https://jeffe.cs.illinois.edu/open/. HTML extraction accessed 2026-07-29. The source explicitly warns that its pages have not been systematically updated since 2001.
• The research summary mentions related arrangement-graph work, but supplies no identifiable paper or original lower-bound reference.