The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918512763600896 |
|---|---|
| author | Afshani, Peyman Brodal, Gerth Stølting Sitchinava, Nodari |
| author_facet | Afshani, Peyman Brodal, Gerth Stølting Sitchinava, Nodari |
| contents | We prove that no deterministic output-sensitive algorithm for the planar convex hull and maxima problems can obtain both optimal time and I/O complexity, where the optimality is defined with respect to both the input and output sizes. This explains why the best previous algorithms achieved an optimal I/O bound at the cost of sub-optimal running time (Goodrich et al. [FOCS, 1993]). To the best of our knowledge, the impossibility of simultaneous optimality was only shown previously for the permutation problem by Brodal and Fagerberg [STOC, 2003]. Our results imply that no optimal deterministic output-sensitive cache-oblivious algorithm exists for either problem. In addition, we present simple deterministic algorithms that match our lower bounds and that provide a trade-off between time and I/Os. On the other hand, a simple modification of our deterministic algorithm results in a randomized algorithm that simultaneously achieves optimal (worst-case) time and optimal expected I/O bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09464 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems Afshani, Peyman Brodal, Gerth Stølting Sitchinava, Nodari Data Structures and Algorithms Computational Geometry We prove that no deterministic output-sensitive algorithm for the planar convex hull and maxima problems can obtain both optimal time and I/O complexity, where the optimality is defined with respect to both the input and output sizes. This explains why the best previous algorithms achieved an optimal I/O bound at the cost of sub-optimal running time (Goodrich et al. [FOCS, 1993]). To the best of our knowledge, the impossibility of simultaneous optimality was only shown previously for the permutation problem by Brodal and Fagerberg [STOC, 2003]. Our results imply that no optimal deterministic output-sensitive cache-oblivious algorithm exists for either problem. In addition, we present simple deterministic algorithms that match our lower bounds and that provide a trade-off between time and I/Os. On the other hand, a simple modification of our deterministic algorithm results in a randomized algorithm that simultaneously achieves optimal (worst-case) time and optimal expected I/O bounds. |
| title | The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2605.09464 |