Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.02472 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910928135520256 |
|---|---|
| author | Phillips, Jeff M. Schou, Jens Kristian Refsgaard |
| author_facet | Phillips, Jeff M. Schou, Jens Kristian Refsgaard |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02472 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Trajectory Minimum Touching Ball Phillips, Jeff M. Schou, Jens Kristian Refsgaard Computational Geometry 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$. |
| title | Trajectory Minimum Touching Ball |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2505.02472 |