pith. machine review for the scientific record. sign in

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

Recognition: 2 theorem links

· Lean Theorem

Nearly-Tight Bounds for Vertical Decomposition in Three and Four Dimensions

Pankaj K. Agarwal , Esther Ezra , Micha Sharir
Authors on Pith no claims yet

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

classification 💻 cs.CG
keywords vertical decompositionsemi-algebraic setsarrangementsminimization diagramscuttingspoint-enclosure queriescomputational geometry
0
0 comments X

The pith

Vertical decompositions of the complement of semi-algebraic unions in R^3 and of trivariate minimization diagrams have nearly tight complexity bounds.

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

The paper settles several long-standing open questions by proving sharp upper and lower bounds on the complexity of vertical decompositions for two important substructures of arrangements. For the complement of the union of n constant-complexity semi-algebraic regions in three dimensions, and for the minimization diagram of n trivariate functions, the vertical decomposition has size that is nearly linear in the worst-case size of the underlying arrangement itself. These bounds are obtained by a combinatorial analysis that avoids extra factors from algebraic degrees. If correct, the results immediately yield faster algorithms for building the decompositions, for producing (1/r)-cuttings of the same substructures, and for preprocessing semi-algebraic sets to answer point-enclosure queries in R^3 and R^4.

Core claim

We obtain sharp bounds on the complexity of the vertical decomposition of the complement of the union of a set of semi-algebraic regions of constant complexity in R^3, and of the minimization diagram of a set of trivariate functions. These results lead to efficient algorithms for a variety of problems involving vertical decompositions, including algorithms for constructing the decompositions themselves and for constructing (1/r)-cuttings of substructures of arrangements. They also lead to a data structure for answering point-enclosure queries amid semi-algebraic sets in R^3 and R^4.

What carries the argument

Vertical decomposition, which partitions each cell of an arrangement of semi-algebraic sets into a collection of constant-complexity subcells by drawing vertical walls from each edge.

If this is right

  • Algorithms for constructing the vertical decompositions of the union complement and minimization diagrams become more efficient.
  • Construction of (1/r)-cuttings for the same substructures of arrangements improves in both time and size.
  • Data structures supporting point-enclosure queries amid semi-algebraic sets in three and four dimensions can be built with better preprocessing and query time.

Where Pith is reading between the lines

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

  • The same analysis may yield improved running times for 3D motion-planning problems whose free space is defined by semi-algebraic obstacles.
  • The technique could be adapted to obtain nearly-tight bounds for vertical decompositions of other low-dimensional substructures such as lower envelopes or Voronoi diagrams.

Load-bearing premise

The semi-algebraic regions and functions have constant descriptive complexity, so that the vertical decomposition can be bounded by a purely combinatorial argument without extra superlinear factors coming from algebraic degrees or degeneracies.

What would settle it

An explicit family of constant-complexity semi-algebraic regions in R^3 whose vertical decomposition of the union complement has size asymptotically larger than the stated nearly-tight bound.

Figures

Figures reproduced from arXiv: 2605.09234 by Esther Ezra, Micha Sharir, Pankaj K. Agarwal.

Figure 1
Figure 1. Figure 1: (a) The coordinate system of the underlying vertical decomposition. (b) A subcell of the first decom￾position stage. (c) Its xy-projection and its 2D vertical decomposition. (d) The resulting vertical decomposition of the subcell. (e) An example of a final cell. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A vertical crossing χv = (e,e ′ , g) with σ(χ) = σ3. Fix a (split) edge e of C(S) and assume that e is a lower edge, so C(S) lies above e, locally near e, and e is contained in the intersection of two top region boundaries. Consider the upward curtain Ve . A vertex v ∈ A(Σe) corresponds to a vertical crossing χv = (e,e ′ , g), where v is the top endpoint of g and lies on the edge e ′ that crosses Ve at v, … view at source ↗
Figure 3
Figure 3. Figure 3: (a) The setup in the construction of Φe; (b) illustration of property (R4). Now consider a set σ ∈ Sγ, and let p ∈ ∂σ− ∩ Vγ be a point (not a vertex) on the lower envelope of Σγ. Then p ∈ ∂C(S). Suppose p lies above eL for some edge e ∈ Eγ. We collect a set of at least k − 1 vertices of A(Σγ) of V-level at most k, as described below. We apply this step starting from only one point p on ∂σ− ∩ Vγ, for each σ… view at source ↗
Figure 4
Figure 4. Figure 4: A covered edge crossing g. In this figure the relevant e-incident surface is ∂σ+ 1 . (a) ∂σ+ 2 crosses ∂σ+ 1 once before w (at e). (b) ∂σ+ 2 crosses ∂σ+ 1 twice before w. Uncovered vertical crossings. The analysis of uncovered edge-crossings is performed separately for each (split) edge e ′ . Let e ′ be a split edge of A(S) at depth at most k with Φe ′ ̸= ∅. Let t = te ′ be the number of sets of S whose to… view at source ↗
Figure 5
Figure 5. Figure 5: The setup at an uncovered edge crossing. The arcs of Σ e ′ can be partitioned and clipped into O(tβ(t)) subarcs, so that they cover the first k V-levels of A(Σ e ′ ), and each subarc contains at most k vertices of A(Σ e ′ ). To achieve this, we observe that there is a value k ∗ ∈ [k, 2k] such that the k ∗ -V-level in A(Σ e ′ ) has O(tβ(t)) vertices. This follows by the pigeonhole principle, since the overa… view at source ↗
Figure 6
Figure 6. Figure 6: The vertices (a) along ∂σ(χ) − ∩ Ve between the top endpoint of g and the intersection ∂ζ− ∩ ∂σ(χ) −, and (b) along ∂σ+ 1 ∩ V e ′ between χ = (e,e ′ , g) and the intersection w of ∂ζ− and ∂σ+ 1 . (P1) For every subset A ⊂ S of size at most 4, there is at most one vertical crossing χ in Φc with D(χ) = A (recall that D(χ) is the defining set of χ), i.e., if there are multiple such crossings, we keep one and … view at source ↗
Figure 7
Figure 7. Figure 7: The two highlighted points represent vertical crossings, but we keep only the right one. Let χ = (e,e ′ , g) be a covered crossing in the pruned Φc , and let △(χ) (resp., △′ (χ)) be the trapezoid within Ve (resp., V e ′ ) introduced in property (R4) (resp., in the definition of covered crossings). By (R4) and this definition, there are at most k + 2k = 3k regions in S whose boundaries intersect △(χ) ∪ △′ (… view at source ↗
Figure 8
Figure 8. Figure 8: An illustration of a covered edge-crossing (e,e ′ , g) and its associated path π = π1 ◦ π2 ◦ π3 shown in bold. The two possible scenarios are depicted. (i) π1(χ) is the subarc of ∂ζ− ∩ Ve connecting v to u. (ii) π2(χ) is the subarc of ∂ζ− ∩ V e ′ extending from u towards w, stopping as soon as it hits either ∂σ+ 1 or ∂σ+ 2 at a point w ′ (w ′ may or may not be equal to w, depending on which of the two surf… view at source ↗
Figure 9
Figure 9. Figure 9: Scenarios that arise in the analysis of the first two cases of path intersections. In (a) π1(χ1) and π1(χ2) are drawn on the same curve, and we separate them to aid the reader’s visibility. Proof. Let χ1 = (e1,e ′ 1 , g1) and χ2 = (e2,e ′ 2 , g2) be two distinct vertical crossings in Φc R (after the pruning), such that π(χ1) ∩ π(χ2) ̸= ∅. Let q be such an intersection point. Let ζ1 = cr(χ1) and ζ2 = cr(χ2)… view at source ↗
Figure 10
Figure 10. Figure 10: Path intersections of types (c) and (d). surfaces that are incident on the bottom endpoint of g2. However, as argued in case (b), that bottom surface cannot cross π2(χ2), or pass above it, implying that e ′ 1 = e ′ 2 . See [PITH_FULL_IMAGE:figures/full_fig_p024_10.png] view at source ↗
read the original abstract

Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in ${{\mathbb R}}^d$ into constant-complexity subcells. In this paper, we settle in the affirmative a few long-standing open problems involving the vertical decomposition of substructures of arrangements for $d = 3, 4$. For example, we obtain sharp bounds on the complexity of the vertical decomposition of the complement of the union of a set of semi-algebraic regions of constant complexity in ${{\mathbb R}}^3$, and of the minimization diagram of a set of trivariate functions. These results lead to efficient algorithms for a variety of problems involving vertical decompositions, including algorithms for constructing the decompositions themselves and for constructing $(1/r)$-cuttings of substructures of arrangements. They also lead to a data structure for answering point-enclosure queries amid semi-algebraic sets in ${{\mathbb R}}^3$ and ${{\mathbb R}}^4$.

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 / 2 minor

Summary. The paper claims to settle several long-standing open problems by deriving nearly-tight upper bounds on the complexity of the vertical decomposition of the complement of the union of a set of semi-algebraic regions of constant complexity in R^3, and of the minimization diagram of a set of trivariate functions. These results are used to obtain efficient algorithms for constructing the decompositions, (1/r)-cuttings, and a data structure for point-enclosure queries in R^3 and R^4.

Significance. If the bounds hold as claimed, this work significantly advances the understanding of arrangement complexities in low dimensions. The combinatorial analysis via random sampling and cuttings, with constants depending only on the fixed descriptive complexity, is a key strength, providing clean derivations without additional factors from algebraic degrees or degeneracies. This has direct implications for practical algorithms in computational geometry.

minor comments (2)
  1. [Introduction] The distinction between 'sharp bounds' in the abstract and 'Nearly-Tight Bounds' in the title should be clarified to avoid confusion.
  2. [Algorithmic applications] Explicit time complexities for the new algorithms should be stated more prominently to highlight the improvements.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. The referee's summary accurately captures the main results on nearly-tight complexity bounds for vertical decompositions in 3D and 4D semi-algebraic arrangements, along with the algorithmic applications.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper derives nearly-tight bounds on vertical decomposition complexity for semi-algebraic regions in R^3 and minimization diagrams of trivariate functions via standard combinatorial arguments on arrangements, employing random sampling and cuttings whose constants depend solely on the fixed descriptive complexity. No steps reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the analysis proceeds independently from arrangement complexity bounds without renaming known results or smuggling ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; full text would be needed to audit algebraic assumptions or combinatorial lemmas.

pith-pipeline@v0.9.0 · 5469 in / 1153 out tokens · 53837 ms · 2026-05-12T04:35:24.618003+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

43 extracted references · 43 canonical work pages

  1. [1]

    P . K. Agarwal, Simplex range searching and its variants: A review, inJourney through Discrete Mathematics: A Tribute to Jiˇ r´ ı Matouˇ sek, M. Loebl, J. Ne ˇsetˇril, and R. Thomas (editors), Springer Verlag, Berlin-Heidelberg, 2017, pp. 1–30

    work page 2017

  2. [2]

    P . K. Agarwal, B. Aronov, E. Ezra, M. J. Katz, and M. Sharir, Intersection queries for flat semi-algebraic objects in three dimensions and related problems. ACM Trans. Algorithms 21 (2025), 25:1–25:59

    work page 2025

  3. [3]

    P . K. Agarwal, B. Aronov, E. Ezra, and J. Zahl, An efficient algorithm for generalized polynomial partitioning and its applications, SIAM J. Comput. 50 (2021), 760–787

    work page 2021

  4. [4]

    P . K. Agarwal, B. Aronov, and M. Sharir, Computing envelopes in four dimensions with applications, SIAM J. Comput. 26(6) (1997), 1714–1732

    work page 1997

  5. [5]

    P . K. Agarwal, A. Efrat, and M. Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, SIAM J. Comput. 29(3) (1999), 912–953. 40

    work page 1999

  6. [6]

    P . K. Agarwal, E. Ezra and M. Sharir, Vertical decomposition in 3D and 4D with applica- tions to line nearest-neighbor searching in 3D, Proc. 35th ACM-SIAM Sympos. on Discrete Algorithms (2024), 150–170. Also in arXiv:2311.01597

    work page arXiv 2024

  7. [7]

    P . K. Agarwal and J. Matouˇsek, On range searching with semialgebraic sets, Discrete Comput. Geom. 11 (1994), 393–418

    work page 1994

  8. [8]

    P . K. Agarwal, J. Matouˇsek, O. Schwarzkopf, Computing many faces in arrangements of lines and segments, SIAM J. Comput. 27(2) (1998), 491–505

    work page 1998

  9. [9]

    P . K. Agarwal, J. Matouˇsek, and M. Sharir, On range searching with semialgebraic sets II, SIAM J. Comput. 42 (2013), 2039–2062

    work page 2013

  10. [10]

    P . K. Agarwal, J. Pach, and M. Sharir, State of the union (of geometric objects): A review, in Computational Geometry: Twenty Years Later(J. Goodman, J.Pach, and R. Pollack, eds.), American Mathematical Society, Providence, 2008, pp. 9–48

    work page 2008

  11. [11]

    P . K. Agarwal, O. Schwarzkopf, and M. Sharir, The overlay of lower envelopes and its applications, Discrete Comput. Geom. 15 (1996), 1–13

    work page 1996

  12. [12]

    P . K. Agarwal and M. Sharir, Efficient randomized algorithms for some geometric optimization problems, Discrete Comput. Geom. 16 (1996), 317–337

    work page 1996

  13. [13]

    P . K. Agarwal and M. Sharir, Arrangements of surfaces in higher dimensions, in Handbook of Computational Geometry (eds. J.R. Sack and J. Urrutia), pp. 49–119, North- Holland, Amsterdam, 2000

    work page 2000

  14. [14]

    P . K. Agarwal and M. Sharir, Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions, Discrete Comput. Geom. 24 (2000), 645–685

    work page 2000

  15. [15]

    P . K. Agarwal, M. Sharir and A. Steiger, Decomposing the complement of the union of cubes in three dimensions, Discrete Comput. Geom. 72 (2024), 407–450

    work page 2024

  16. [16]

    Aronov, A

    B. Aronov, A. Efrat, V . Koltun, and M. Sharir, On the union ofκ-round objects in three and four dimensions, Discrete Comput. Geom. 36(4) (2006), 511–526

    work page 2006

  17. [17]

    Aronov and M

    B. Aronov and M. Sharir, Triangles in space or building (and analyzing) castles in the air, Combinatorica 10(2) (1990), 137–173

    work page 1990

  18. [18]

    S. Basu, R. Pollack, and M.-F. Roy,Algorithms in Real Algebraic Geometry, 2nd Edition, Springer Verlag, Berlin, 2006

    work page 2006

  19. [19]

    de Berg, K

    M. de Berg, K. Dobrindt, and O. Schwarzkopf, On lazy randomized incremental construction, Discrete Comput. Geom. 14 (1995), 261–286

    work page 1995

  20. [20]

    de Berg, L

    M. de Berg, L. J. Guibas and D. Halperin, Vertical decomposition for triangles in 3-space, Discrete Comput. Geom. 15 (1996), 35–61

    work page 1996

  21. [21]

    de Berg and O

    M. de Berg and O. Schwarzkopf, Cuttings and applications, Int. J. Comput. Geom. Appl. 5 (1995), 343–355. 41

    work page 1995

  22. [22]

    T. M. Chan, Random sampling, halfspace range reporting, and construction of (≤ k)- levels in three dimensions, SIAM J. Comput. 30 (2000), 561–575

    work page 2000

  23. [23]

    Chazelle, H

    B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir, A singly exponential stratifi- cation scheme for real semi-algebraic varieties and its applications, Theoret. Comput. Sci. 84 (1991), 77–105. Also in Proc. 16th Int. Colloq. on Automata, Languages and Programming, 1989, pp. 179–193

    work page 1991

  24. [24]

    Chazelle and J

    B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), 229–249

    work page 1990

  25. [25]

    Chazelle and J

    B. Chazelle and J. Incerpi, Triangulation and shape-complexity,ACM Trans. Graphics 3 (1984), 135–152

    work page 1984

  26. [26]

    K. L. Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geom., 2 (1987), 195–222

    work page 1987

  27. [27]

    K. L. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangement of curves and spheres, Discrete Comput. Geom. 5 (1990), 99–160

    work page 1990

  28. [28]

    K. L. Clarkson and P . W. Shor, Application of random sampling in computational geometry, II. Discrete Comput. Geom. 4 (1989), 387–421

    work page 1989

  29. [29]

    G. E. Collins, Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition, Proc. 2nd GI Conf. Automata Theory and Formal Languages, volume 33. Springer LNCS, 1975

    work page 1975

  30. [30]

    Ezra, On the union of cylinders in three dimensions, Discrete Comput

    E. Ezra, On the union of cylinders in three dimensions, Discrete Comput. Geom. 45(1) (2011), 45–64

    work page 2011

  31. [31]

    Ezra and M

    E. Ezra and M. Sharir, On the union of fat tetrahedra in three dimensions, J. ACM 57(1) (2009), 2:1–2:23

    work page 2009

  32. [32]

    L. Guth. Polynomial partitioning for a set of varieties, Math. Proc. Camb. Phil. Soc., 159 (2015), 459–469

    work page 2015

  33. [33]

    Guth and N

    L. Guth and N. H. Katz, On the Erd˝os distinct distances problem in the plane, Annals Math. 181 (2015), 155–190

    work page 2015

  34. [34]

    Halperin and M

    D. Halperin and M. Sharir, A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment, Discrete Comput. Geom. 16(2) (1996), 121–134

    work page 1996

  35. [35]

    Haussler and E

    D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2 (1987), 127–151

    work page 1987

  36. [36]

    Koltun, Almost tight upper bounds for vertical decompositions in four dimensions, J

    V . Koltun, Almost tight upper bounds for vertical decompositions in four dimensions, J. ACM 51(5) (2004), 699–730

    work page 2004

  37. [37]

    Matou ˇsek, Efficient partition trees, Discrete Comput

    J. Matou ˇsek, Efficient partition trees, Discrete Comput. Geom. 8 (1992), 315–334. 42

    work page 1992

  38. [38]

    Matou ˇsek, Reporting points in halfspaces, Comput

    J. Matou ˇsek, Reporting points in halfspaces, Comput. Geom. Theory Appl. 2 (1992), 169–186

    work page 1992

  39. [39]

    Matouˇsek and Z

    J. Matouˇsek and Z. Pat´akov´a, Multilevel polynomial partitioning and simplified range searching, Discrete Comput. Geom. 54 (2015), 22–41

    work page 2015

  40. [40]

    J. T. Schwartz and M. Sharir, On the Piano Movers’ problem: II. General techniques for computing topological properties of real algebraic manifolds, Advances in Appl. Math., 4 (1983), 298–351

    work page 1983

  41. [41]

    Schwarzkopf and M

    O. Schwarzkopf and M. Sharir, Vertical decomposition of a single cell in a three- dimensional arrangement of surfaces, Discrete Comput. Geom., 18(3) (1997), 269–288

    work page 1997

  42. [42]

    Sharir and P

    M. Sharir and P . K. Agarwal,Davenport-Schinzel Sequences and Their Geometric Applica- tions, Cambridge University Press, Cambridge-New York-Melbourne, 1995

    work page 1995

  43. [43]

    Tagansky, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Discrete Comput

    B. Tagansky, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Discrete Comput. Geom. 16(4) (1996), 455–479. 43

    work page 1996