Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918131937574912 |
|---|---|
| author | Eppstein, David Goodrich, Michael T. Illickan, Abraham M. To, Claire A. |
| author_facet | Eppstein, David Goodrich, Michael T. Illickan, Abraham M. To, Claire A. |
| contents | We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a measure that we call range-partition entropy, which unifies and subsumes previous definitions of entropy used for sorting problems and structural entropy used in computational geometry. We provide simple algorithms for several problems, including 2D maxima, 2D and 3D convex hulls, and some visibility problems, and we show that they have running times depending on the range-partition entropy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20489 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness Eppstein, David Goodrich, Michael T. Illickan, Abraham M. To, Claire A. Computational Geometry We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a measure that we call range-partition entropy, which unifies and subsumes previous definitions of entropy used for sorting problems and structural entropy used in computational geometry. We provide simple algorithms for several problems, including 2D maxima, 2D and 3D convex hulls, and some visibility problems, and we show that they have running times depending on the range-partition entropy. |
| title | Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2508.20489 |