Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| 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$.