Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Phillips, Jeff M., Schou, Jens Kristian Refsgaard
Format: Preprint
Veröffentlicht: 2025
Schlagworte:
Online-Zugang:https://arxiv.org/abs/2505.02472
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Inhaltsangabe:
  • 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 \geq 4$ we provide a trajectory configuration with unbounded LP-type complexity, but also present an almost $O\left((nk)^2\log n\right)$ algorithm through the farthest line segment Voronoi diagrams. If we tolerate a relative approximation, we can reduce to time near-linear in $n$.