Papers › Stabbing balls with line segments and polygonal paths
Stabbing balls with line segments and polygonal paths
Alexander Neuhaus, Dennis Rohde
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We study the problem of ordered stabbing of n balls (of arbitrary and possibly different radii, no ball contained in another) in ℝᵈ, d ≥3, with either a directed line segment or a (directed) polygonal curve. Here, the line segment, respectively polygonal curve, shall visit (intersect) the given sequence of balls in the order of the sequence. We present a deterministic algorithm that decides whether there exists a line segment stabbing the given sequence of balls in order, in time O(n⁴ᵈ⁻² logn). Due to the descriptional complexity of the region containing these line segments, we can not extend this algorithm to actually compute one. We circumvent this hurdle by devising a randomized algorithm for a relaxed variant of the ordered line segment stabbing problem, which is built upon the central insights from the aforementioned decision algorithm. We further show that this algorithm can be plugged into an algorithmic scheme by Guibas et al., yielding an algorithm for a relaxed variant of the minimum-link ordered stabbing path problem that achieves approximation factor 2 with respect to the number of links. We conclude with experimental evaluations of the latter two algorithms, showing practical applicability.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections