Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.19840 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911971055501312 |
|---|---|
| author | Flemming, Jens |
| author_facet | Flemming, Jens |
| contents | Based on Welzl's algorithm for smallest circles and spheres we develop a simple linear time algorithm for finding the smallest circle enclosing a point cloud on a sphere. The algorithm yields correct results as long as the point cloud is contained in a hemisphere, but the hemisphere does not have to be known in advance and the algorithm automatically detects whether the hemisphere assumption is met.
For the full-sphere case, that is, if the point cloud is not contained in a hemisphere, we provide hints on how to adapt existing linearithmic time algorithms for spherical Voronoi diagrams to find the smallest enclosing circle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_19840 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A simple linear time algorithm for smallest enclosing circles on the (hemi)sphere Flemming, Jens Computational Geometry Metric Geometry Optimization and Control Based on Welzl's algorithm for smallest circles and spheres we develop a simple linear time algorithm for finding the smallest circle enclosing a point cloud on a sphere. The algorithm yields correct results as long as the point cloud is contained in a hemisphere, but the hemisphere does not have to be known in advance and the algorithm automatically detects whether the hemisphere assumption is met. For the full-sphere case, that is, if the point cloud is not contained in a hemisphere, we provide hints on how to adapt existing linearithmic time algorithms for spherical Voronoi diagrams to find the smallest enclosing circle. |
| title | A simple linear time algorithm for smallest enclosing circles on the (hemi)sphere |
| topic | Computational Geometry Metric Geometry Optimization and Control |
| url | https://arxiv.org/abs/2407.19840 |