pith. machine review for the scientific record. sign in

arxiv: 2605.03904 · v1 · submitted 2026-05-05 · 💻 cs.CG

Recognition: unknown

Computing Planar Convex Hulls with a Promise

Sepideh Aghamolaei , Kevin Buchin , Timothy M. Chan , Jacobus Conradi , Ivor van der Hoog , Vahideh Keikha , Jeff M. Phillips , Benjamin Raichel
Authors on Pith no claims yet

Pith reviewed 2026-05-09 15:33 UTC · model grok-4.3

classification 💻 cs.CG
keywords convex hullsubsequence promisecomputational geometrylower boundsrandomized algorithmsalgebraic computation tree
0
0 comments X

The pith

If convex hull vertices appear in cyclic order as a subsequence, the hull can be computed in O(n sqrt(log n)) deterministic time.

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

The paper establishes that a promise about the input sequence suffices to break the classic Omega(n log n) lower bound for planar convex hulls. When the hull vertices occur in their boundary order as a subsequence, a deterministic algorithm finishes in O(n sqrt(log n)) time and a randomized one in expected O(n log to any positive power epsilon) time. The interior points may arrive in arbitrary, even adversarial, positions yet do not prevent the speedup. Breaking the promise by moving even one hull vertex out of order immediately restores the full Omega(n log n) lower bound, so the promise itself cannot be verified faster.

Core claim

Under the promise that the input sequence contains the convex hull as a subsequence, we give a deterministic O(n sqrt(log n))-time algorithm to compute the convex hull of P. With randomisation, we achieve expected running time O(n log^epsilon n) for any constant epsilon > 0. We also prove that if it is even slightly broken, i.e., allowing just one hull point to appear out of order, an adversarial Omega(n log n)-time lower bound holds.

What carries the argument

The subsequence promise that hull vertices appear in cyclic boundary order, which permits algorithms to exploit partial ordering without full verification or sorting.

If this is right

  • Sub-O(n log n) convex hull algorithms exist whenever the hull points form an ordered subsequence.
  • The promise cannot be checked in fewer than Omega(n log n) comparisons.
  • Allowing even one hull point to appear out of order forces the full Omega(n log n) lower bound.
  • Interior points may be placed adversarially without destroying the asymptotic improvement under the promise.
  • The conjecture that hull computation on any supersequence can be faster is false.

Where Pith is reading between the lines

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

  • The logarithmic factor in convex hull time is driven primarily by the need to order the extreme points rather than all points.
  • The same subsequence promise may extend to other problems whose difficulty also stems from ordering the boundary or extremes.
  • In streaming or partially ordered data settings, exploiting such a promise could yield practical speedups even when full verification is impossible.

Load-bearing premise

The input is a sequence of points such that the convex hull vertices appear in their cyclic boundary order as a subsequence.

What would settle it

Take any sequence in which one hull vertex is placed out of cyclic order and test whether the algorithm still returns the correct hull in o(n log n) time.

read the original abstract

Computing the convex hull of a planar $n$-point set $P$ is one of the most fundamental problems in computational geometry. It has an $\Omega(n \log n)$ lower bound in the algebraic computation tree model, and many convex hull algorithms match this bound. Classical results show that, under special input assumptions, sub-$O(n \log n)$ algorithms are possible. For instance, when the points are given in lexicographic or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist. This naturally raises the question: can the convex hull of a point set be computed in sub-$O(n \log n)$ time under weaker input assumptions? We answer this positively. Under the promise that the input sequence contains the convex hull as a subsequence, we give a deterministic $O(n \sqrt{\log n})$-time algorithm to compute the convex hull of $P$. With randomisation, we achieve expected running time $O(n \log^{\varepsilon} n)$ for any constant $\varepsilon > 0$. We find this surprising, as points not on the convex hull may behave adversarially toward our convex hull construction algorithm. Yet the promise that \emph{only} the hull points are sorted suffices for $o(n \log n)$-time algorithms. Finally, we show that this promise is tight: if it is even slightly broken, i.e., allowing just one hull point to appear out of order, we prove an adversarial $\Omega(n \log n)$-time lower bound. Consequently, the promise cannot be verified with fewer than $\Omega(n \log n)$ comparisons. This also negatively resolves an open problem of L\"{o}ffler and Raichel, who conjectured sub-$O(n \log n)$-time algorithms for computing the convex hull of a supersequence containing the hull as a subsequence.

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.

Referee Report

0 major / 3 minor

Summary. The paper claims that under the promise that the vertices of the convex hull of an n-point set P appear in cyclic boundary order as a subsequence of the input sequence, the convex hull can be computed deterministically in O(n √log n) time and in expected O(n log^ε n) time for any constant ε>0 with randomization. It further claims an adversarial Ω(n log n) lower bound in the algebraic computation tree model if the promise is violated by even a single hull vertex appearing out of order, which also negatively resolves the Löffler-Raichel conjecture on supersequences.

Significance. If the upper and lower bounds hold, this is a notable contribution to computational geometry. It demonstrates that a weak cyclic-order subsequence promise on hull vertices alone suffices for o(n log n) algorithms despite adversarial interior points, while the promise is information-theoretically tight. The explicit adversarial construction for the lower bound and the negative resolution of the open conjecture are strengths; the results clarify the precise threshold at which ordering assumptions yield sub-logarithmic speedups.

minor comments (3)
  1. The abstract and introduction should explicitly state the precise model (algebraic computation tree with or without floor functions) and clarify whether the randomized algorithm uses Las Vegas or Monte Carlo guarantees, as this affects the interpretation of the expected-time bound.
  2. Section describing the deterministic algorithm should include a high-level pseudocode or diagram illustrating how the promise is exploited to achieve the √log n factor, to aid readability for readers unfamiliar with ordering-relaxation techniques.
  3. The lower-bound proof should explicitly address whether the Ω(n log n) bound holds even when the single out-of-order hull point is adversarially placed among interior points, to strengthen the tightness claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, recognition of its contribution to computational geometry, and recommendation for minor revision. We appreciate the acknowledgment that the subsequence promise yields o(n log n) algorithms while being information-theoretically tight, along with the negative resolution of the Löffler-Raichel conjecture.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central results consist of explicit constructive algorithms (deterministic O(n √log n) and randomized O(n log^ε n)) that operate directly on the promised subsequence property of the input sequence, together with a lower-bound argument established by an explicit adversarial construction that forces Ω(n log n) time once the promise is violated by even one out-of-order hull vertex. These steps rely on standard algebraic computation tree techniques and ordering relaxations; no equation or claim reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation. The negative resolution of the Löffler-Raichel conjecture is obtained by the same adversarial argument and does not depend on any internal fitting or renaming of prior results. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper operates in the standard algebraic computation tree model for geometric algorithms and introduces no new free parameters, axioms beyond standard model assumptions, or invented entities.

axioms (1)
  • standard math Algebraic computation tree model with constant-time primitive operations on real numbers
    Invoked implicitly for the Omega(n log n) lower bound and all running-time claims.

pith-pipeline@v0.9.0 · 5697 in / 1337 out tokens · 50082 ms · 2026-05-09T15:33:07.369336+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 16 canonical work pages

  1. [1]

    1 Peyman Afshani, Jérémy Barbay, and Timothy M. Chan. Instance-optimal geometric al- gorithms.Journal of the ACM, 64(1), March 2017.doi:10.1145/3046673. Aghamolaei, Buchin, Chan, Conradi, van der Hoog, Keikha, Phillips, and Raichel XX:15 2 Alex M. Andrew. Another efficient algorithm for convex hulls in two dimensions.Information Processing Letters, 9(5):2...

    work page doi:10.1145/3046673 2017

  2. [2]

    5 Hervé Brönnimann and Timothy M

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.SoCG.2024.24. 5 Hervé Brönnimann and Timothy M. Chan. Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time.Computational Geometry, 34(2):75–82,

    work page doi:10.4230/lipics.socg.2024.24 2024

  3. [3]

    6 Kevin Buchin, Maarten Löffler, Pat Morin, and Wolfgang Mulzer

    doi:10.1016/J.COMGEO.2005.11.005. 6 Kevin Buchin, Maarten Löffler, Pat Morin, and Wolfgang Mulzer. Preprocessing imprecise points for Delaunay triangulation: Simplified and extended.Algorithmica, 2011.doi:10.1007/ s00453-010-9430-0. 7 Timothy M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. InInternational Symposium...

    work page doi:10.1016/j.comgeo.2005.11.005 2005

  4. [4]

    8 TimothyM.Chan

    Association for Computing Machinery.doi:10.1145/220279.220281. 8 TimothyM.Chan. Optimaloutput-sensitiveconvexhullalgorithmsintwoandthreedimensions. Discrete & Computational Geometry, 16(4):361–368, 1996.doi:10.1007/BF02712873. 9 Timothy M. Chan. Deterministic algorithms for 2-d convex programming and 3-d online linear programming.Journal of Algorithms, 27...

    work page doi:10.1145/220279.220281 1996

  5. [5]

    com/science/article/pii/S0196677497909147,doi:10.1006/jagm.1997.0914

    URL:https://www.sciencedirect. com/science/article/pii/S0196677497909147,doi:10.1006/jagm.1997.0914. 10 Timothy M. Chan. Three problems about dynamic convex hulls.Int. J. Comput. Geom. Appl., 22(4):341–364, 2012.doi:10.1142/S0218195912600096. 11 Timothy M. Chan and Mihai Pătraşcu. Voronoi diagrams inn·2O( √ lg lgn) time. InProceedings of the 39th Annual A...

    work page doi:10.1006/jagm.1997.0914 1997

  6. [6]

    12 Timothy M

    doi:10.1145/1250790.1250796. 12 Timothy M. Chan, Jack Snoeyink, and Chee-Keng Yap. Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams.Discret. Comput. Geom., 18(4):433–454, 1997.doi:10.1007/PL00009327. 13 Donald R. Chand and Sham S. Kapur. An algorithm for convex polytopes.J...

    work page doi:10.1145/1250790.1250796 1997

  7. [7]

    4 Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL:https://drops.dagstuhl. de/entities/document/10.4230/LIPIcs.ESA.2025.25,doi:10.4230/LIPIcs.ESA.2025.25. 18 Olivier Devillers. Delaunay triangulation of imprecise points: Preprocess and actually get a fast query time.Journal of Computational Geometry (JoCG), 2011.doi:10.20382/jocg. v2i1a3ff.ffinria-005...

    work page doi:10.4230/lipics.esa.2025.25 2025

  8. [8]

    CVIT 2016 XX:16 Computing Planar Convex Hulls with a Promise 20 David Eppstein, Michael T

    doi:10.1137/ 0220016. CVIT 2016 XX:16 Computing Planar Convex Hulls with a Promise 20 David Eppstein, Michael T. Goodrich, Abraham M. Illickan, and Claire A. To. Entropy- bounded computational geometry made easier and sensitive to sortedness.Canadian Conference on Computational Geometry (CCCG 2025), August

    2016

  9. [9]

    21 Jeff Erickson

    URL:https://arxiv.org/abs/ 2508.20489,doi:10.48550/arXiv.2508.20489. 21 Jeff Erickson. Lower bounds for linear satisfiability problems. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 388–395, 1995.doi:10.1145/313651.313772. 22 Jeff Erickson. New lower bounds for convex hull problems in odd dimensions.SIAM Journal on Computing, 28(4):1198–1214, ...

    work page doi:10.48550/arxiv.2508.20489 1995

  10. [10]

    16 Esther Ezra and Wolfgang Mulzer

    URL:https://www.cs.ubc.ca/~will/papers/ possiblehull.pdf. 25 Esther Ezra and Wolfgang Mulzer. Convex hull of points lying on lines ino(nlogn )time after preprocessing.Computational Geometry, 2013.doi:10.1016/j.comgeo.2012.03.004. 26 Xavier Goaoc and Emo Welzl. Convex hulls of random order types.Journal of the ACM, 70(1), January 2023.doi:10.1145/3570636. ...

    work page doi:10.1016/j.comgeo.2012.03.004 2013

  11. [11]

    18 Ronald L

    URL:https://www.sciencedirect.com/ science/article/pii/0020019072900452,doi:10.1016/0020-0190(72)90045-2. 28 Ronald L. Graham and F. Frances Yao. Finding the convex hull of a simple polygon.Journal of Algorithms, 4(4):324–331, 1983.doi:10.1016/0196-6774(83)90013-5. 29 Emil Toftegaard Gæde, Inge Li Gørtz, Ivor van der Hoog, Christoffer Krogh, and Eva Roten...

    work page doi:10.1016/0020-0190(72)90045-2 1983

  12. [12]

    To obtain an optimal algorithm, one needs to apply the footnote by McQueen.doi:10.1137/0215021. 32 D. T. Lee. On finding the convex hull of a simple polygon.International Journal of Parallel Programming, 12(2):87–98, 1983.doi:10.1007/BF00993195. 33 Maarten Löffler and Benjamin Raichel. Preprocessing disks for convex hulls, revisited.arXiv preprint arXiv:2...

    work page doi:10.1137/0215021 1983

  13. [13]

    37 Maarten Löffler and Jack Snoeyink

    34 Maarten Löffler and Jack Snoeyink. Delaunay triangulation of imprecise points in linear time after preprocessing.Computational Geometry, 2010.doi:10.1016/j.comgeo.2008.12.007. 35 Maarten Löffler and Benjamin Raichel. Preprocessing disks for convex hulls, revisited,

    work page doi:10.1016/j.comgeo.2008.12.007 2010

  14. [14]

    Melkman , title =

    URL:https://arxiv.org/abs/2502.03633,arXiv:2502.03633. 36 Duncan McCallum and David Avis. A linear algorithm for finding the convex hull of a simple polygon.Information Processing Letters (IPL), 9(5):201–206, 1979.doi:10.1016/ 0020-0190(79)90069-3. 37 Avraham A. Melkman. On-line construction of the convex hull of a simple polyline.Information Processing L...

    work page doi:10.1016/0020-0190(87)90086-x 1979

  15. [15]

    40Ivor van der Hoog, Henrik Reinstädtler, and Eva Rotenberg

    URL:https://www.sciencedirect.com/science/ article/pii/B9780444878069500177,doi:10.1016/B978-0-444-87806-9.50017-7. 40Ivor van der Hoog, Henrik Reinstädtler, and Eva Rotenberg. Practical insertion-only convex hull. InSIAM Symposium on Algorithm Engineering and Experiments (ALENEX), pages 71–84, 2026.doi:10.1137/1.9781611978957.6. Aghamolaei, Buchin, Chan,...

    work page doi:10.1016/b978-0-444-87806-9.50017-7 2026

  16. [16]

    URL:https://arxiv.org/abs/2512.06559

    preprint. URL:https://arxiv.org/abs/2512.06559. 43 Marc van Kreveld, Maarten Löffler, and Joseph Mitchell. Preprocessing imprecise points and splitting triangulations.SIAM Journal on Computing (SICOMP), 2010.doi:10.1137/ 090753620. 44 Haitao Wang. Dynamic convex hulls under window-sliding updates. InAlgorithms and Data Structures (WADS), page 689–703, Ber...

    work page arXiv 2010

  17. [17]

    45 Haitao Wang

    Springer-Verlag.doi: 10.1007/978-3-031-38906-1_46. 45 Haitao Wang. Algorithms for subpath convex hull queries and ray-shooting among segments. SIAM Journal on Computing, 53(4):1132–1161, 2024.doi:10.1137/21M145118X. 46 Günter M. Ziegler.Lectures on Polytopes, volume 152 ofGraduate Texts in Mathematics. Springer-Verlag,

    work page doi:10.1007/978-3-031-38906-1_46 2024

  18. [18]

    in its neighbouring slabs, it suffices to maintain only the first and last point of the Pareto front of each group. (In fact, we could even avoid dividing into groups altogether, so many of the steps could be simplified for the Pareto front problem.) This recovers a similar bound onT (n,µ,O(1))in the proof of Lemma 8, resulting CVIT 2016 XX:18 Computing P...

    2016

  19. [19]

    B Additional Details for Lower Bounds B.1 Model of Computation Formally, we assume that our input is a setP of n points given as sequence

    ▶Corollary14.Algorithm 3 can be modified to compute the Pareto front of a sequence of points fulfilling the Pareto-front promise in expected timeO(n·2O( √ log logn) )(or n·2O( √ log logh) wherehis the number of points on the front). B Additional Details for Lower Bounds B.1 Model of Computation Formally, we assume that our input is a setP of n points give...

    2016