pith. sign in

arxiv: 2602.08843 · v1 · pith:NSCBO27Rnew · submitted 2026-02-09 · 💻 cs.CG · cs.DS

The Presort Hierarchy for Geometric Problems

Ivor van der Hoog , Eva Rotenberg , Jack Spalding-Jamieson , Lasse Wulf This is my paper

Pith reviewed 2026-05-21 14:32 UTC · model grok-4.3

classification 💻 cs.CG cs.DS
keywords presort hierarchyquadtreesvoronoi diagramsdelaunay triangulationseuclidean minimum spanning treescomputational geometryo(n log n) algorithmsrandomized algorithms
0
0 comments X

The pith

Given sortings along both axes, quadtrees and Voronoi diagrams can be built in expected O(n sqrt(log n)) time.

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

The paper introduces the Presort Hierarchy to classify geometric problems according to whether one or two presorted axes suffice for an o(n log n) algorithm. It proves that quadtrees are 2-Presortable by exhibiting a randomized algorithm that runs in expected O(n sqrt(log n)) time when both coordinate sortings are supplied in advance, and shows that Delaunay triangulations, Voronoi diagrams, and Euclidean minimum spanning trees inherit this property. This directly addresses the 1989 question of Aggarwal, Guibas, Saxe, and Shor on whether two presorts can break the classical n log n barrier for these structures. A sympathetic reader cares because many geometric primitives were previously known only to require Omega(n log n) time via sorting reductions, and the new bound demonstrates that presorting information can remove a logarithmic factor.

Core claim

We introduce the Presort Hierarchy: a problem is 1-Presortable if a sorting along one axis permits a possibly randomized o(n log n)-time algorithm, 2-Presortable if sortings along both axes suffice, and Presort-Hard otherwise. Our main result is that quadtrees are 2-Presortable via an algorithm with expected running time O(n sqrt(log n)); the same bound holds for Delaunay triangulations, Voronoi diagrams, and Euclidean minimum spanning trees. We also classify several of the other listed geometric problems as either 2-Presortable or Presort-Hard.

What carries the argument

The Presort Hierarchy, which classifies problems by the number of presorted axes needed for o(n log n) algorithms; it organizes the computational power of presorting for constructing quadtrees and derived structures.

If this is right

  • Quadtrees admit an expected O(n sqrt(log n)) construction time once both axis sortings are supplied.
  • Delaunay triangulations, Voronoi diagrams, and Euclidean minimum spanning trees inherit the same expected time bound.
  • Several other listed geometric problems are shown to be either 2-Presortable or Presort-Hard under the new classification.
  • The longstanding open question on o(n log n) algorithms for Voronoi diagrams given two presorts is resolved in the randomized setting.

Where Pith is reading between the lines

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

  • The hierarchy suggests a systematic way to measure the value of presorting for other spatial data structures beyond the ones explicitly treated.
  • Similar classification could be applied to dynamic or online versions of these geometric problems.
  • A deterministic algorithm achieving the same O(n sqrt(log n)) bound would strengthen the result for practical implementations.

Load-bearing premise

The input consists of n planar points for which exact sortings along both coordinate axes are provided in advance, and the algorithm may use randomization to achieve the expected time bound.

What would settle it

An Omega(n log n) lower bound for quadtree construction that holds even when exact sortings along both axes are given in advance would show that quadtrees are not 2-Presortable.

read the original abstract

Many fundamental problems in computational geometry admit no algorithm running in $o(n \log n)$ time for $n$ planar input points, via classical reductions from sorting. Prominent examples include the computation of convex hulls, quadtrees, onion layer decompositions, Euclidean minimum spanning trees, KD-trees, Voronoi diagrams, and decremental closest-pair. A classical result shows that, given $n$ points sorted along a single direction, the convex hull can be constructed in linear time. Subsequent works established that for all of the other above problems, this information does not suffice. In 1989, Aggarwal, Guibas, Saxe, and Shor asked: Under which conditions can a Voronoi diagram be computed in $o(n \log n)$ time? Since then, the question of whether sorting along TWO directions enables a $o(n \log n)$-time algorithm for such problems has remained open and has been repeatedly mentioned in the literature. In this paper, we introduce the Presort Hierarchy: A problem is 1-Presortable if, given a sorting along one axis, it permits a (possibly randomised) $o(n \log n)$-time algorithm. It is 2-Presortable if sortings along both axes suffice. It is Presort-Hard otherwise. Our main result is that quadtrees, and by extension Delaunay triangulations, Voronoi diagrams, and Euclidean minimum spanning trees, are 2-Presortable: we present an algorithm with expected running time $O(n \sqrt{\log n})$. This addresses the longstanding open problem posed by Aggarwal, Guibas, Saxe, and Shor (albeit randomised). We complement this result by showing that some of the other above geometric problems are also 2-Presortable or Presort-Hard.

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

2 major / 2 minor

Summary. The paper introduces the Presort Hierarchy, classifying geometric problems as 1-Presortable (o(n log n) time given one presorted axis), 2-Presortable (given both axes), or Presort-Hard. The main claim is that quadtrees (and by extension Delaunay triangulations, Voronoi diagrams, and Euclidean MSTs) are 2-Presortable via a randomized algorithm with expected O(n sqrt(log n)) time when n planar points are provided with exact x- and y-sorted orders. The work also classifies additional problems such as convex hulls and closest-pair queries within the hierarchy, addressing the 1989 open question of Aggarwal et al.

Significance. If the algorithm and its analysis hold, the result resolves a longstanding open problem by showing that two presortings suffice for a sub-logarithmic improvement on several core geometric structures. The hierarchy framework itself provides a useful lens for analyzing the role of partial sorting information in computational geometry. The randomized expected-time bound and the explicit construction for quadtrees are notable strengths.

major comments (2)
  1. [Section 3] Section 3 (Quadtree Construction Algorithm): The recursive partitioning uses medians from the two global sorted lists to divide into quadrants, but the total cost of producing x- and y-sorted sublists for each child must be analyzed. If each internal node performs explicit linear-time filtering or copying to materialize the four child lists, the aggregate work across the recursion tree (even with O(sqrt(log n)) effective depth under randomization) is not obviously O(n sqrt(log n)) in expectation; an implicit or lazy representation must be specified and its overhead bounded.
  2. [Section 4] Section 4 (Extension to Delaunay/Voronoi/EMST): The reductions from quadtrees to these structures are invoked to transfer the 2-Presortable property, but the additional overhead (e.g., post-processing steps or auxiliary data structures) is not quantified. It is necessary to verify that these steps preserve the overall expected O(n sqrt(log n)) bound rather than introducing an extra log n factor.
minor comments (2)
  1. [Introduction] The formal definition of 'Presort-Hard' would benefit from an explicit mathematical statement (e.g., a lower-bound reduction) rather than a descriptive paragraph in the introduction.
  2. [Section 3] Figure 2 (recursion tree illustration) would be clearer if it annotated the expected depth and the per-level work distribution under the randomization.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments raise valid points about the clarity of the running-time analysis and the overhead of reductions. We address each major comment below and will revise the manuscript accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: [Section 3] Section 3 (Quadtree Construction Algorithm): The recursive partitioning uses medians from the two global sorted lists to divide into quadrants, but the total cost of producing x- and y-sorted sublists for each child must be analyzed. If each internal node performs explicit linear-time filtering or copying to materialize the four child lists, the aggregate work across the recursion tree (even with O(sqrt(log n)) effective depth under randomization) is not obviously O(n sqrt(log n)) in expectation; an implicit or lazy representation must be specified and its overhead bounded.

    Authors: We appreciate this observation on the potential cost of list maintenance. The algorithm in Section 3 represents each subproblem implicitly via index ranges into the two global presorted arrays, rather than copying or filtering lists explicitly at each node. Median selection and quadrant assignment are performed in constant time per recursive call by computing split positions in the original arrays; point-to-quadrant assignment occurs only when a point is examined during traversal. The expected total work is charged to points according to the probability they reach a given recursion depth, which yields the O(n sqrt(log n)) bound under the randomized median selection. We will add a new lemma and expanded paragraph in the revised Section 3 that formally bounds the overhead of the implicit representation. revision: yes

  2. Referee: [Section 4] Section 4 (Extension to Delaunay/Voronoi/EMST): The reductions from quadtrees to these structures are invoked to transfer the 2-Presortable property, but the additional overhead (e.g., post-processing steps or auxiliary data structures) is not quantified. It is necessary to verify that these steps preserve the overall expected O(n sqrt(log n)) bound rather than introducing an extra log n factor.

    Authors: The referee is correct that the overhead of the reductions should be quantified explicitly. Section 4 invokes standard linear-time reductions: once the quadtree is available, the Delaunay triangulation (and hence Voronoi diagram) can be constructed from the quadtree in O(n) time by connecting neighboring leaves, and the Euclidean MST follows from the Delaunay triangulation via a linear-time graph MST algorithm on the resulting O(n)-edge graph. These steps introduce no additional logarithmic factor. We will revise Section 4 to include a short paragraph that cites the relevant linear-time results and confirms the overall expected time remains O(n sqrt(log n)). revision: yes

Circularity Check

0 steps flagged

No significant circularity; new algorithmic construction is self-contained

full rationale

The paper defines the Presort Hierarchy and presents an explicit randomized recursive algorithm that partitions using medians from the two given global sorted lists to build quadtrees (and extensions) in expected O(n sqrt(log n)) time. No equations reduce a claimed output to a fitted parameter or prior result by construction, no self-citations are load-bearing for the central bound, and the time analysis is presented as a direct counting argument over the recursion tree rather than a renaming or re-derivation of input quantities. The result is therefore a genuine algorithmic advance on the Aggarwal et al. open question and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on standard assumptions of the real RAM model for planar point sets and the availability of exact presorted sequences; the Presort Hierarchy itself is a new definitional construct introduced to organize the results.

axioms (2)
  • domain assumption Input is a set of n points in the Euclidean plane with real coordinates.
    Invoked throughout the abstract when discussing geometric primitives and lower bounds from sorting.
  • domain assumption Presort sequences along each axis are provided exactly and can be used as input.
    Central to the definition of 1-Presortable and 2-Presortable problems.
invented entities (1)
  • Presort Hierarchy (1-Presortable, 2-Presortable, Presort-Hard) no independent evidence
    purpose: Classification framework for geometric problems based on presort utility.
    New taxonomy defined in the paper to capture the algorithmic results.

pith-pipeline@v0.9.0 · 5878 in / 1461 out tokens · 73561 ms · 2026-05-21T14:32:52.074358+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

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

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

20 extracted references · 20 canonical work pages

  1. [1]

    1 Peyman Afshani, Jérémy Barbay, and Timothy M. Chan. Instance-Optimal Geometric Algorithms.Journal of the ACM, 64(1), March 2017.doi:10.1145/3046673. Ivor van der Hoog, Eva Rotenberg, Jack Spalding-Jamieson, Lasse Wulf 19 2 Alok Aggarwal, Leonidas J. Guibas, James Saxe, and Peter W. Shor. A linear-time algorithm for computing the Voronoi diagram of a con...

    work page doi:10.1145/3046673 2017

  2. [2]

    URL:https://dl.acm.org/doi/10.5555/578775

    ACM Digital Library ID: 10.5555/578775. URL:https://dl.acm.org/doi/10.5555/578775. 4 Alex 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)90072-3. 5 Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau. On the Worst-Case Complexity of TimSort.Eur...

    work page doi:10.5555/578775 1979

  3. [3]

    6 Xingjian Bai and Christian Coester

    doi:10.4230/LIPIcs.ESA.2018.4. 6 Xingjian Bai and Christian Coester. Sorting with predictions.International Conference on Neural Information Processing Systems (NIPS),

    work page doi:10.4230/lipics.esa.2018.4 2018

  4. [4]

    A Geometric Heuristic for Rectilinear Crossing Minimization

    URL: https://dl.acm.org/doi/10. 5555/3666122.3667277. 7 Djamal Belazzougui and Simon J Puglisi. Range predecessor and Lempel-Ziv parsing.ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 2053–2071, 2016.doi:10.1137/1. 9781611974331.ch143. 8 Michael Ben-Or. Lower Bounds for Algebraic Computation Trees.ACM Symposium on Theory of Computing (STOC), pag...

    work page doi:10.1137/1 2053

  5. [5]

    Nöllenburg, M

    doi:10.20382/jocg. v2i1a3ff.ffinria-00595823. 17 Hristo Djidjev and Andrzej Lingas. On computing Voronoi Diagrams for Sorted Planar Point Sets.International Journal of Computational Geometry & Applications, 05(03):327–337,

    work page doi:10.20382/jocg

  6. [6]

    18 David Eppstein, Michael T

    doi:10.1142/S0218195995000192. 18 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

    work page doi:10.1142/s0218195995000192 2025

  7. [7]

    org/abs/2508.20489,doi:10.48550/arXiv.2508.20489

    URL: https://arxiv. org/abs/2508.20489,doi:10.48550/arXiv.2508.20489. 19 Vladmir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithms.ACM Comput. Surv., 24(4):441–476, December 1992.doi:10.1145/146370.146381. 20 William Evans and Jeff Sember. The Possible Hull of Imprecise Points.Canadian Conference on Computational Geometry (CCCG),

    work page doi:10.48550/arxiv.2508.20489 1992

  8. [8]

    20 The Presort Hierarchy for Geometric Problems 21 Esther Ezra and Wolfgang Mulzer

    URL: https://www.cs.ubc.ca/~will/papers/ possiblehull.pdf. 20 The Presort Hierarchy for Geometric Problems 21 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. 22 Michael L. Fredman. How good is the information theory bound in sorting?The...

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

  9. [9]

    23 Michael L

    URL:https://www.sciencedirect.com/science/ article/pii/0304397576900785,doi:10.1016/0304-3975(76)90078-5. 23 Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees.Journal of Computer and System Sciences, 47(3):424–436, December

    work page doi:10.1016/0304-3975(76)90078-5

  10. [10]

    doi:10.1016/0022-0000(93)90040-4. 24 R.L. Graham. An efficient algorith for determining the convex hull of a finite planar set. Information Processing Letters, 1(4):132–133,

    work page doi:10.1016/0022-0000(93)90040-4

  11. [11]

    25 Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, Robert E

    URL:https://www.sciencedirect.com/ science/article/pii/0020019072900452,doi:10.1016/0020-0190(72)90045-2. 25 Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, Robert E. Tarjan, and Jakub Tětek. Fast and Simple Sorting Using Partial Information.ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3953–3973, 2025.doi:10.1137/1.9781611978322....

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

  12. [12]

    28 Drago Krznaric and Christos Levcopoulos

    Addison-Wesley Professional, 2014.doi:10.1137/1012065. 28 Drago Krznaric and Christos Levcopoulos. Computing a threaded quadtree from the Delaunay triangulation in linear time.Nordic Journal of Computing, 5(1):1–18, March

    work page doi:10.1137/1012065 2014

  13. [13]

    Lee and Ying-Fung Wu

    29 D. Lee and Ying-Fung Wu. Geometric complexity of some location problems.Algorithmica, 1:193–211, 11 1986.doi:10.1007/BF01840442. 30 Maarten Löffler and Wolfgang Mulzer. Triangulating the Square and Squaring the Tri- angle: Quadtrees and Delaunay Triangulations are Equivalent.SIAM Journal on Computing, 41(4):941–974, 2012.doi:10.1137/110825698. 31 Maart...

    work page doi:10.1007/bf01840442 1986

  14. [14]

    32 Maarten Löffler and Benjamin Raichel

    doi: 10.1007/978-3-642-40104-6_42. 32 Maarten Löffler and Benjamin Raichel. Preprocessing Disks for Convex Hulls, Revisited.arXiv preprint arXiv:2502.03633,

    work page doi:10.1007/978-3-642-40104-6_42

  15. [15]

    Delaunay Triangulation of Imprecise Points in Linear Time after Preprocessing.Computational Geometry, 2010.doi:10.1016/j.comgeo.2008.12.007

    33 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. 34 Kurt Mehlhorn, Stefan Näher, Thomas Schilz, Stefan Schirra, Michael Seel, Raimund Seidel, and Christian Uhrig. Checking geometric programs or verification of geometric structu...

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

  16. [16]

    38 Michael Ian Shamos and Dan Hoey

    URL:https://www.sciencedirect.com/science/ article/pii/B9780444878069500177,doi:10.1016/B978-0-444-87806-9.50017-7. 38 Michael Ian Shamos and Dan Hoey. Geometric intersection problems.Symposium on Founda- tions of Computer Science (FOCS), pages 208–215, 1976.doi:10.1109/SFCS.1976.16. 39 Godfried T. Toussaint. Computing Largest Empty Circles with Location ...

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

  17. [17]

    40 Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann

    doi: 10.1007/BF01008046. 40 Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann. Preprocessing Ambiguous Imprecise Points.International Symposium on Computational Geometry (SoCG), 2019.doi:10.4230/LIPIcs.SoCG.2019.42. Ivor van der Hoog, Eva Rotenberg, Jack Spalding-Jamieson, Lasse Wulf 21 41 Ivor van der Hoog, Irina Kostitsyna, Maa...

    work page doi:10.1007/bf01008046 2019

  18. [18]

    44 Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann

    doi:10.1137/1.9781611978315.26. 44 Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann. Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull.arXiv:2512.06559 [cs.DS],

    work page doi:10.1137/1.9781611978315.26

  19. [19]

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

    preprint. URL:https://arxiv.org/abs/2512.06559. 45 Van Der Hoog, Ivor and Rutschmann, Daniel. Tight bounds for sorting under par- tial information.Symposium on Foundations of Computer Science (FOCS),

    work page arXiv

  20. [20]

    Minor containment and disjoint paths in almost-linear time

    doi: 10.1109/FOCS61266.2024.00131. 46 Peter van Emde Boas. Preserving order in a forest in less than logarithmic time.Symposium on Foundations of Computer Science (FOCS), pages 75–84, 1975.doi:10.1109/SFCS.1975.26. 47 Marc van Kreveld, Maarten Löffler, and Joseph Mitchell. Preprocessing Imprecise Points and Splitting Triangulations.SIAM Journal on Computi...

    work page doi:10.1109/focs61266.2024.00131 2024