Minimum-Link Path in 2D

Definitions and mathematical statement

Let $\mathcal O$ be pairwise interior-disjoint polygonal obstacles in $\mathbb R^2$ with $n$ vertices in total, and let $s,t$ belong to the same component of the free space $F=\mathbb R^2\setminus\bigcup_{O\in\mathcal O}\operatorname{int}(O)$. A feasible polygonal path consists of consecutive straight segments joining $s$ to $t$, with its whole image in $F$. Boundary contact is allowed. Merge consecutive collinear segments with no change of direction before counting links.

The link distance is \[ \ell_F(s,t)=\min\{k: \text{a feasible }s\text{--}t\text{ path has }k \text{ straight links}\}. \] Can this value and an attaining path be computed in subquadratic time in $n$ in the standard real-arithmetic geometric model? Here subquadratic means $o(n^2)$; a bound $O(n^{2-\delta})$ for some fixed $\delta>0$ is a stronger target.

Link minimization counts changes of direction, not Euclidean path length. The link directions are unrestricted, and obstacles may create holes in the free-space domain. Results for simple polygons without holes, rectilinear links, or approximate link counts do not by themselves answer this formulation.

Short English statement

Can an exact path using the fewest straight segments around planar polygonal obstacles be found in less than quadratic time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500022 (AMR-054-0022), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 22. Original source indexed by AMR-054-0022. https://topp.openproblem.net/p22.