arxiv: 2605.09464 · v1 · submitted 2026-05-10 · 💻 cs.DS · cs.CG

Recognition: no theorem link

The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems

Gerth St{\o}lting Brodal, Nodari Sitchinava, Peyman Afshani

Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:35 UTC · model grok-4.3

classification 💻 cs.DS cs.CG

keywords planar convex hullplanar maximaexternal memoryI/O complexityoutput-sensitive algorithmslower boundsdeterministic algorithmsrandomized algorithms

0 comments

The pith

No deterministic output-sensitive algorithm achieves both optimal time and optimal I/O for planar convex hull and maxima.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for the planar convex hull and maxima problems, no deterministic algorithm sensitive to the output size can simultaneously match the best possible running time and the best possible number of I/O operations to external memory. This holds when both measures are considered optimal relative to the input size n and output size h. The result accounts for the behavior of earlier algorithms that reached optimal I/O performance only by accepting slower running times. It further shows that no deterministic cache-oblivious algorithm can be optimal in both respects. The authors supply deterministic algorithms that realize the best possible trade-offs and a randomized algorithm that attains optimal time together with optimal expected I/O cost.

Core claim

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.

What carries the argument

A lower-bound argument in the external-memory model that separates the requirements for optimal computation time from optimal I/O transfers when performance must depend on output size h.

If this is right

Any deterministic algorithm must sacrifice either time or I/O optimality.
Deterministic algorithms exist that achieve the best possible trade-off between the two measures.
No optimal deterministic cache-oblivious algorithm exists for these problems.
A randomized algorithm can achieve optimal worst-case time together with optimal expected I/O cost.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This extends the known impossibility of simultaneous optimality, previously shown only for the permutation problem, to two fundamental geometric problems.
For large-scale instances, designers may need to accept randomization if they want to avoid any trade-off between time and memory transfers.

Load-bearing premise

The lower bound holds under the standard external-memory model in which time and I/O costs are measured separately and optimality for deterministic algorithms is defined with respect to both input size and output size.

What would settle it

A deterministic output-sensitive algorithm for planar maxima or convex hull that simultaneously meets the optimal time bound and the optimal I/O bound for inputs where both n and h are large.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves no deterministic output-sensitive algorithm can hit both optimal time and optimal I/O for planar maxima and convex hull in the external-memory model, with matching trade-off algorithms and a randomized version that gets optimal time plus expected optimal I/O.

read the letter

The one thing to take away is that no deterministic output-sensitive algorithm can hit both optimal time and optimal I/O for the planar maxima and convex hull problems. The paper proves this in the external-memory model and shows why past work fell short on one or the other. What is new is the application of this kind of impossibility to these geometric problems. Before, it was only known for permutation. The authors also deliver simple deterministic algorithms that match the lower bound via a time-I/O trade-off. They then modify one to get a randomized algorithm with optimal worst-case time and optimal expected I/O. This gives concrete ways to balance the costs. The lower bound seems to follow standard techniques in the EM model, with no free parameters or circular definitions. It references prior results cleanly. The cache-oblivious consequence is noted as a straightforward outcome. Soft spots are limited. The randomized result uses expectation for I/O, which is common but not as strong as worst-case guarantees. The proof details would need checking for any model-specific assumptions, but nothing in the abstract suggests a problem. The work stays focused on deterministic vs randomized distinction without overclaiming. This paper is for people in the external-memory algorithms community, especially those interested in geometric problems or lower bounds. A reader who wants to understand the limits on simultaneous optimality or who designs algorithms in I/O models would find it directly useful. It has enough substance and novelty to warrant a serious referee. I would recommend sending this to peer review.

Referee Report

0 major / 3 minor

Summary. The paper proves that no deterministic output-sensitive algorithm for the planar maxima and convex hull problems can simultaneously achieve both optimal time and optimal I/O complexity in the external-memory model (optimality w.r.t. input size n and output size h). It supplies a matching lower-bound argument, deterministic trade-off algorithms that achieve the lower bounds, and a simple randomized variant that attains optimal worst-case time together with optimal expected I/O. The result is also used to conclude that no optimal deterministic cache-oblivious algorithm exists for either problem.

Significance. If the lower-bound argument holds, the result is significant: it supplies a clean explanation for the time-I/O trade-off observed in the best prior EM algorithms (Goodrich et al., FOCS 1993) and extends the only previously known simultaneous-optimality impossibility (permutation, Brodal-Fagerberg STOC 2003) to two fundamental geometric problems. The matching deterministic trade-offs and the randomized algorithm that meets both bounds in expectation are concrete contributions, and the cache-oblivious corollary is directly useful for memory-hierarchy algorithm design. The work is grounded in the standard EM model with no ad-hoc parameters or invented entities.

minor comments (3)

[Lower-bound section] The lower-bound section would benefit from an explicit statement of the precise comparison model (e.g., whether algebraic decision-tree operations are permitted) immediately before the main theorem, to make the scope of the impossibility unambiguous.
[Randomized algorithm section] The randomized algorithm's expected-I/O analysis relies on a random-sampling step whose failure probability is stated only asymptotically; adding a concrete high-probability bound (e.g., 1-1/n^c) would make the claim easier to verify.
[Introduction] A short table comparing the new trade-off bounds (time vs. I/Os for different parameter regimes) with the Goodrich et al. bounds would improve readability of the introduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our paper, the accurate summary of its contributions, and the recommendation of minor revision. The referee's comments confirm that the lower-bound argument, the matching trade-off algorithms, the randomized variant, and the cache-oblivious corollary are all viewed as significant and well-grounded in the standard external-memory model.

Circularity Check

0 steps flagged

No significant circularity in lower-bound proof

full rationale

The paper establishes an impossibility result via a direct lower-bound argument in the standard external-memory model, showing that no deterministic output-sensitive algorithm for planar maxima and convex hull can simultaneously achieve optimal time and I/O with respect to both n and h. This proof does not rely on self-definitional reductions, fitted parameters renamed as predictions, or load-bearing self-citations; the reference to Brodal and Fagerberg (STOC 2003) is only for historical context on a distinct permutation problem. The matching trade-off algorithms and randomized variant are constructed separately and do not feed back into the lower bound. The derivation is self-contained against the external-memory model without circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions of time and I/O complexity from the external-memory model; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Optimality for time and I/O is defined separately with respect to input size n and output size h in the external-memory model.
This separation is the basis for claiming that simultaneous optimality is impossible for deterministic algorithms.

pith-pipeline@v0.9.0 · 5485 in / 1206 out tokens · 45016 ms · 2026-05-12T04:35:02.142354+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Zum Hilbertschen Aufbau der reellen Zahlen.Mathematische Annalen, 99:118–133, February 1928.doi:10.1007/BF01459088

1 Wilhelm Ackermann. Zum Hilbertschen Aufbau der reellen Zahlen.Mathematische Annalen, 99:118–133, February 1928.doi:10.1007/BF01459088. 2 Peyman Afshani, Gerth Stølting Brodal, and Nodari Sitchinava. The impossibility of simul- taneous time and I/O optimality for the planar maxima and convex hull problems. In Sayan Bhattacharya, Danupon Nanongkai, Michae...

work page doi:10.1007/bf01459088 1928
[2]

3 Peyman Afshani and Pingan Cheng

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 3 Peyman Afshani and Pingan Cheng. Lower bounds for intersection reporting among flat objects. In Erin W. Chambers and Joachim Gudmundsson, editors,39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 ofLIPIcs, pages 3:1–3:16. Schloss Dagstuhl...

work page 2023
[3]

4 Peyman Afshani and Pingan Cheng

doi:10.4230/LIPICS.SOCG.2023.3. 4 Peyman Afshani and Pingan Cheng. On semialgebraic range reporting.Discretete Computa- tional Geometry, 71(1):4–39, 2024.doi:10.1007/S00454-023-00574-1. 5 Peyman Afshani and Arash Farzan. Cache-oblivious output-sensitive two-dimensional convex hull. In Prosenjit Bose, editor,Proceedings of the 19th Annual Canadian Conferen...

work page doi:10.4230/lipics.socg.2023.3 2023
[4]

6 Peyman Afshani, Chris H

URL:http://cccg.ca/ proceedings/2007/07a3.pdf. 6 Peyman Afshani, Chris H. Hamilton, and Norbert Zeh. Cache-oblivious range reporting with optimal queries requires superlinear space. In John Hershberger and Efi Fogel, editors, Proceedings of the 25th ACM Symposium on Computational Geometry, Aarhus, Denmark, June 8-10, 2009, pages 277–286. ACM, 2009.doi:10....

work page doi:10.1145/1542362.1542412 2007
[5]

8 Alok Aggarwal and S

doi:10.1007/S00454-011-9347-7. 8 Alok Aggarwal and S. Vitter, Jeffrey. The input/output complexity of sorting and related problems.Commun. ACM, 31(9):1116–1127, September 1988.doi:10.1145/48529.48535. 9 A.M. Andrew. Another efficient algorithm for convex hulls in two dimensions.Information Processing Letters, 9(5):216–219, 1979.doi:10.1016/0020-0190(79)90...

work page doi:10.1007/s00454-011-9347-7 1988
[6]

16 Gerth Stølting Brodal and Rolf Fagerberg

doi: 10.1016/0020-0190(81)90005-3. 16 Gerth Stølting Brodal and Rolf Fagerberg. On the limits of cache-obliviousness. In Lawrence L. Larmore and Michel X. Goemans, editors,Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 307–315. ACM, 2003.doi:10.1145/780542.780589. 17 R. C. Buck. Mathematical induction and recursive definitions....

work page doi:10.1016/0020-0190(81)90005-3 2003
[7]

19 Bernard Chazelle

Association for Computing Machinery.doi:10.1145/237218.237397. 19 Bernard Chazelle. A minimum spanning tree algorithm with inverse-Ackermann type com- plexity.J. ACM, 47(6):1028–1047, 2000.doi:10.1145/355541.355562. 20 Bernard Chazelle and Burton Rosenberg. The complexity of computing partial sums off- line.International Journal of Computational Geometry ...

work page doi:10.1145/237218.237397 2000
[8]

21 Thomas H

doi:10.1142/S0218195991000049. 21 Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson.Introduction to Algorithms. The MIT Press, 4nd edition,

work page doi:10.1142/s0218195991000049
[9]

22 Rex A. Dwyer. On the convex hull of random points in a polytope.Journal of Applied Probability, 25(4):688–699, 1988.doi:10.2307/3214289. 23 Arash Farzan. Cache-oblivious searching and sorting in multisets. Master’s thesis, University of Waterloo,

work page doi:10.2307/3214289 1988
[10]

Association for Computing Machinery.doi: 10.1145/73007.73040. P. Afshani, G. S. Brodal, N. Sitchinava 27 25 Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. Cache- oblivious algorithms. In40th Annual Symposium on Foundations of Computer Science, FOCS ’99, pages 285–298. IEEE Computer Society, 1999.doi:10.1109/SFFCS.1999.814600....

work page doi:10.1145/73007.73040 1999
[11]

doi:10.1145/2071379. 2071383. 27 Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, and Jeffrey Scott Vitter. External- memory computational geometry. In34th Annual Symposium on Foundations of Computer Science, pages 714–723. IEEE Computer Society, 1993.doi:10.1109/SFCS.1993.366816. 28 R.L. Graham. An efficient algorithm for determining the convex ...

work page doi:10.1145/2071379 1993
[12]

41 Jeffrey Scott Vitter

doi:10.1016/ 0020-0190(80)90064-2. 41 Jeffrey Scott Vitter. External memory algorithms and data structures: Dealing with massive data.ACM Computing surveys (CSUR), 33(2):209–271, 2001.doi:10.1145/384192.384193. 42 Jeffrey Scott Vitter. Algorithms and data structures for external memory.Found. Trends Theor. Comput. Sci., 2(4):305–474, January 2008.doi:10.1...

work page doi:10.1145/384192.384193 2001