2025/05/05 by Phillips, Jeff M., Schou, Jens Kristian Refsgaard
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2505.02472
We present algorithms to find the minimum radius sphere that intersects every trajectory in a set of n trajectories composed of at most k line segments each. When k=1, we can reduce the problem to the LP-type framework to achieve a linear time complexity. For k ≥ 4 we provide a trajectory configuration with unbounded LP-type complexity, but also present an almost O((nk)2log n) algorithm through the farthest line segment Voronoi diagrams. If we tolerate a relative approximation, we can reduce to time near-linear in n.