2026-09-08T01:22:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26394 2026-09-05T19:41:58Z ddc:004 open_access

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 External Memory model cache-oblivious algorithms lower bounds 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peyman Afshani and Gerth Stølting Brodal and Nodari Sitchinava 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.5 urn:nbn:de:0030-drops-263943 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.5 eng https://creativecommons.org/licenses/by/4.0/legalcode