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

arxiv: 2605.09464 · v2 · pith:TKHVJR2Lnew · submitted 2026-05-10 · 💻 cs.DS · cs.CG

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

Peyman Afshani , Gerth St{\o}lting Brodal , Nodari Sitchinava This is my paper

Pith reviewed 2026-05-21 08:49 UTC · model grok-4.3

classification 💻 cs.DS cs.CG

keywords convex hullmaximaexternal memoryI/O complexitylower boundsoutput-sensitivedeterministic algorithms

0 comments

The pith

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

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

The paper proves that no deterministic output-sensitive algorithm for the planar convex hull and maxima problems can obtain both optimal time and I/O complexity simultaneously. Optimality here is with respect to both input and output sizes in the external-memory model. This explains the trade-offs seen in earlier algorithms. The authors also give deterministic algorithms with time-I/O trade-offs and a randomized one that achieves optimal time and expected optimal I/Os.

Core claim

What carries the argument

Lower bound construction in the external-memory model forcing a necessary trade-off between time and I/Os for deterministic algorithms.

If this is right

This implies no optimal deterministic output-sensitive cache-oblivious algorithm exists for these problems.
Simple deterministic algorithms exist that match the lower bounds with a trade-off between time and I/Os.
A randomized version achieves optimal worst-case time and optimal expected I/O bounds.

Where Pith is reading between the lines

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

Randomization allows bypassing the impossibility for expected I/O performance.
The trade-off may be relevant for designing practical algorithms in memory-constrained environments.
Similar impossibilities could hold for other geometric problems under external memory constraints.

Load-bearing premise

Algorithms are required to be deterministic and output-sensitive under the standard external-memory model with block size B and internal memory M.

What would settle it

Discovery of a deterministic output-sensitive algorithm achieving both the optimal time bound and the optimal I/O bound for these problems would falsify the result.

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

This paper shows that deterministic output-sensitive algorithms for planar maxima and convex hull cannot achieve both optimal time and optimal I/O in the external-memory model, extending the permutation lower bound with matching upper bounds.

read the letter

The main thing to know is that no deterministic output-sensitive algorithm for planar convex hull or maxima can hit both optimal time and optimal I/O at once in the standard external-memory model with parameters M and B. This directly explains the time penalty in earlier I/O-optimal work and rules out optimal deterministic cache-oblivious solutions for these problems. The result is new because the impossibility was previously limited to the permutation problem; extending the Brodal-Fagerberg construction while keeping output sensitivity with respect to both n and h is a clear step forward in the external-memory lower-bound literature. The paper does well by supplying simple deterministic algorithms that achieve the implied time-I/O trade-off and by showing a randomized variant that gets optimal worst-case time together with optimal expected I/O. The stress-test confirms the lower-bound argument is internally consistent, with no hidden assumptions about comparison models or specific output-size regimes that would break the claim. One minor soft spot is that the randomized result only guarantees expected I/O rather than worst-case, though this is stated plainly and still useful. The citation pattern looks appropriate, building directly on the relevant prior lower-bound work without unnecessary self-reference. This paper is for researchers working on external-memory algorithms, geometric problems, or cache-oblivious data structures. A reader focused on lower bounds or trade-offs in I/O models would find the limits and matching constructions valuable. I would send it for peer review because the core impossibility is precise and the supporting algorithms make the contribution concrete.

Referee Report

1 major / 3 minor

Summary. The paper proves that no deterministic output-sensitive algorithm for the planar convex hull and maxima problems can simultaneously achieve both optimal time and optimal I/O complexity in the external-memory model (with parameters M and B), where optimality is defined with respect to input size n and output size h. It extends the permutation lower bound of Brodal and Fagerberg, provides deterministic algorithms achieving explicit time-I/O trade-offs that match the lower bound, and gives a simple randomized algorithm achieving optimal worst-case time and optimal expected I/O. The result also implies the non-existence of optimal deterministic cache-oblivious algorithms for these problems.

Significance. If the lower-bound argument holds, this is a significant contribution to external-memory geometric algorithms. It explains the sub-optimal time in prior I/O-optimal algorithms (e.g., Goodrich et al.) and provides the first impossibility result of this form beyond permutations. The matching deterministic trade-off algorithms and the randomized solution that achieves both optima are concrete strengths. The work supplies falsifiable predictions via the explicit trade-off curves and is grounded in the standard external-memory model without hidden assumptions on comparison-based computation or specific h regimes.

major comments (1)

Lower-bound construction (Section 3): the extension of the Brodal-Fagerberg permutation argument to output-sensitive maxima/convex-hull instances must explicitly verify that the adversary can force Ω((n/B) log_{M/B} (n/h)) I/Os even when the algorithm's running time is allowed to depend on the (unknown) output size h; if the construction permits the algorithm to discover h too early, the I/O lower bound may become trivial for small h.

minor comments (3)

Abstract: the statement that the deterministic algorithms 'match our lower bounds' would be clearer if it briefly indicated the precise form of the achieved trade-off (e.g., the functional dependence of I/Os on h).
Introduction: a one-sentence recap of the I/O and time bounds achieved by Goodrich et al. (FOCS 1993) would help readers place the new impossibility result.
Randomized algorithm section: the analysis of expected I/O optimality should include a short remark on whether the high-probability bound or only expectation is obtained, to avoid ambiguity with the deterministic worst-case time claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive evaluation, and recommendation for minor revision. We address the single major comment below.

read point-by-point responses

Referee: Lower-bound construction (Section 3): the extension of the Brodal-Fagerberg permutation argument to output-sensitive maxima/convex-hull instances must explicitly verify that the adversary can force Ω((n/B) log_{M/B} (n/h)) I/Os even when the algorithm's running time is allowed to depend on the (unknown) output size h; if the construction permits the algorithm to discover h too early, the I/O lower bound may become trivial for small h.

Authors: We appreciate this observation. Our adversary argument in Section 3 is constructed so that, for any deterministic algorithm whose running time may depend on the final (unknown) h, the adversary maintains a family of consistent input configurations with different possible output sizes. Resolving which configuration is the true one—and thereby determining the exact h—requires the algorithm to perform Ω((n/B) log_{M/B} (n/h)) I/Os in the worst case before it can safely output a correct maxima set of size h. The construction ensures that any early termination or early inference of h would violate output-sensitivity on at least one of the adversary’s remaining configurations. Consequently the I/O lower bound remains non-trivial even for small h. We will add a short clarifying paragraph after the main adversary lemma to make this verification explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in lower-bound proof

full rationale

The manuscript presents an independent lower-bound construction for deterministic output-sensitive algorithms in the standard external-memory model (parameters M and B) for the planar maxima and convex hull problems. It extends the permutation lower bound of Brodal and Fagerberg (STOC 2003) by preserving output sensitivity with respect to both n and h, but the extension itself is developed from first principles within this paper rather than reducing to the prior result by definition or fit. Matching deterministic upper bounds and a randomized variant are supplied separately. No self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations that collapse the central impossibility claim were identified. The derivation remains self-contained against the explicitly stated model and determinism assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on the standard external-memory model and the output-sensitive complexity framework; no free parameters or new entities are introduced.

axioms (1)

domain assumption Standard external-memory model with parameters M (internal memory size) and B (block size)
I/O complexity is defined with respect to this model throughout the abstract.

pith-pipeline@v0.9.0 · 5716 in / 1047 out tokens · 45097 ms · 2026-05-21T08:49:38.641166+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that no deterministic output-sensitive algorithm ... can obtain both optimal time ... and optimal I/O complexity ... lower bound ... N·A_s(H) comparisons ... Ω(n(α_1(min{H,√(N/M)})−s)) I/Os
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat induction / embed_strictMono unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

adversarial strategy ... potential sequence ... Φ(h; (t,κ),S) ... top nodes ... A_s+2ζ−1(1)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

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. 26 The Planar Maxima and Convex Hull Problems 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...

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]

doi: 10.1016/0020-0190(81)90005-3. P. Afshani, G. S. Brodal, N. Sitchinava 27 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. Mathem...

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]

25 Matteo Frigo, Charles E

Association for Computing Machinery.doi: 10.1145/73007.73040. 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. 26 Matteo Frigo, Charles E. Leiserson, Har...

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]

40 Jeffrey Scott Vitter

doi:10.1016/ 0020-0190(80)90064-2. 40 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. 41 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

[1] [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. 26 The Planar Maxima and Convex Hull Problems 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...

work page doi:10.1007/bf01459088 1928

[2] [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] [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] [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] [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] [6]

doi: 10.1016/0020-0190(81)90005-3. P. Afshani, G. S. Brodal, N. Sitchinava 27 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. Mathem...

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

[7] [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] [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] [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] [10]

25 Matteo Frigo, Charles E

Association for Computing Machinery.doi: 10.1145/73007.73040. 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. 26 Matteo Frigo, Charles E. Leiserson, Har...

work page doi:10.1145/73007.73040 1999

[11] [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] [12]

40 Jeffrey Scott Vitter

doi:10.1016/ 0020-0190(80)90064-2. 40 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. 41 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