arxiv: 2604.14468 · v1 · submitted 2026-04-15 · 💻 cs.GR

Recognition: unknown

Progressive Convex Hull Simplification

Alec Jacobson

Authors on Pith no claims yet

Pith reviewed 2026-05-10 11:13 UTC · model grok-4.3

classification 💻 cs.GR

keywords convex hullsimplificationdual representationgreedy optimizationhalf-spacesbounding volumeconservative approximationO(n log n)

0 comments

The pith

Representing a convex hull in dual space lets a greedy algorithm simplify it to any number of half-spaces in O(n log n) time while minimizing added volume or area.

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

Convex hulls grow linearly with input size, which slows down repeated queries such as collision detection or ray tracing. The paper shows how to reduce any hull to a user-chosen number of bounding planes while adding as little extra volume or surface area as possible. Moving the problem into dual space turns plane selection into a fast greedy choice that runs in O(n log n) time. The resulting simplified hull always contains the original shape, so it stays safe for conservative applications. Comparisons with prior techniques indicate they are either slower, looser, or risk cutting into the input geometry.

Core claim

By shifting to the dual representation, each candidate half-space becomes a point and the simplification task reduces to selecting a small subset of these points. A greedy ordering of the dual points yields a sequence of progressively simpler outer approximations whose added volume or area grows slowly. The algorithm therefore produces a safe, tight proxy of any desired complexity without enumerating combinations.

What carries the argument

The dual representation of the convex hull, where each half-space maps to a point and greedy selection of dual points directly controls the increase in enclosed volume or area.

If this is right

A single preprocessing pass produces a family of nested outer approximations that can be swapped in at runtime to trade accuracy for speed.
The O(n log n) bound makes the method practical for hulls containing thousands of faces in interactive graphics pipelines.
Because the output is guaranteed to contain the input, the simplified hull can replace the full hull in any conservative query without introducing false negatives.
The same dual greedy ordering can be stopped early to obtain a hierarchy of bounding volumes for level-of-detail collision or distance routines.

Where Pith is reading between the lines

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

The dual greedy pattern may extend to simplifying other convex sets, such as intersections of balls or cylinders, where a similar point-plane duality exists.
For extremely large inputs the preprocessing cost could be further reduced by first computing an approximate convex hull and then simplifying it.
If the greedy choice property can be proved to yield a bounded approximation ratio, the method would become a drop-in replacement for slower exact optimization routines.

Load-bearing premise

That the greedy ordering of dual points will always produce a simplification whose added volume or area stays close to the best possible choice and never violates the outer-approximation guarantee on any input shape.

What would settle it

A small input hull for which an exhaustive search over all subsets of k half-spaces finds an outer approximation whose added volume is substantially smaller than the volume returned by the dual greedy method.

Figures

Figures reproduced from arXiv: 2604.14468 by Alec Jacobson.

**Figure 1.** Figure 1: Our convex hull simplification iteratively removes the next halfspace that would add the least amount of volume. This results in very tight fitting hulls (under 5% increase) down to a small number of faces (18). Even for an extreme simplification (6 faces), the simplified hull is a modestly tighter fit than an oriented bounding box (1.61× vs. 1.72×). Abstract Convex hulls are useful as tight bounding proxi… view at source ↗

**Figure 2.** Figure 2: Our simplification is a natural drop-in to approximate convex decomposition methods, e.g., CoACD [WLLS22]. Their software optionally allows decimation (vertex dropping) as a postprocess, but results in gaps between hulls, which permit false negatives during collision handling. Our simplification is tight and safe. arXiv:2604.14468v1 [cs.GR] 15 Apr 2026 [PITH_FULL_IMAGE:figures/full_fig_p001_2.png] view at source ↗

**Figure 3.** Figure 3: Our simplification selects output halfspaces from the input exact convex hull, aiming to minimize volume. Some alternatives do not limit their output to existing faces planes, but nevertheless perform inferiorly. 3.1. Theory and Bounds Lopez & Reisner [LR00] began in 2D proving bounds on inner (and outer) approximations produced by greedily removing vertices (or halfspaces) according to area change. In 2… view at source ↗

**Figure 5.** Figure 5: We simplify each of the 133 models from threedscans.com to 18 faces. We show a histogram collecting each output as factor of the corresponding input hull volume. Our method was always smallest and often by a significant margin. linear performance matching the O(nlogn) expectation. The median time to simplify was 32% of the time to compute the corresponding input hull. All simplifications took less than a… view at source ↗

**Figure 6.** Figure 6: We compare the family of convex hull simplification techniques that are variants of mesh simplification [GH97]. Our method achives the smallest volume change. Runner up is running naive appearance preserving mesh simplification on the dual hull [GH97] (dual). Input point cloud Convex hull 1× Hausdor Our simpli ed convex hull 2.09× Hausdor [MCK13] 3.53× Hausdor [GH97] (dual) 7.42× Hausdor [STL*2025] 3.41× H… view at source ↗

**Figure 7.** Figure 7: We take as input a point cloud, build its exact convex hull and then compare extreme simplifications with a variety of methods. Our method finds the tightest simplification measured not just in terms of volume and area (which we can target to minimize directly), but also in terms of Hausdorff distance measured post facto. Input hull Ours [STL*25] more faces too few faces too many faces dense [PITH_FULL_IM… view at source ↗

**Figure 9.** Figure 9: The zero-level set of (quasi) signed distance field from Inigo Quilez can be enclosed in a tighest-fitting but still loose capsule. Similar to [STL∗ 25] we extract points conservatively bounding the true convex hull of the implicit surface and simplify it. surface is smooth, its discrete approximation could be arbitrarily dense (5000+ faces shown here). We simplify to only 18 faces while only increasing … view at source ↗

**Figure 10.** Figure 10: Both are really tight, but we can choose to minimize volume or area. Differences are a bit more pronounced at extreme simplifications, like this example down to 16 faces 18 faces each [PITH_FULL_IMAGE:figures/full_fig_p007_10.png] view at source ↗

**Figure 11.** Figure 11: Simplified convex hulls can be used for broadphase collision detection or directly as rigid body collision proxies. safe, leaving gaps between decomposition cells. A similar problem happens with the default simplification in VHACD [Mam16] in [PITH_FULL_IMAGE:figures/full_fig_p007_11.png] view at source ↗

**Figure 13.** Figure 13: V-representations are good for inner approximations: we run our volume-minimizing simplification on this football’s primal hull directly, producing a tighter inner approximation than standard mesh simplification [GH97]. Input mesh Convex hull 1× volume Ours (default) 1.01005× Ours constrained 1.01042× 3188 faces xed face xed face [PITH_FULL_IMAGE:figures/full_fig_p008_13.png] view at source ↗

**Figure 14.** Figure 14: optimal tetrahedron optimal rhombohedron our typical 4-face output [PITH_FULL_IMAGE:figures/full_fig_p008_14.png] view at source ↗

**Figure 15.** Figure 15: The globally optimal 4-faces simplification of an icosahedron is a regular tetrahedron (left). This is unreachable if our greedy path first finds the globally optimal rhombohedron (middle). Due to early indistinguishable symmetric breaking choices, we usually find a globally suboptimal tetrahedron for this extreme simplification example. orate elimination algorithms (e.g., beam search) or explore nonse… view at source ↗

read the original abstract

Convex hulls are useful as tight bounding proxies for a variety of tasks including collision detection, ray intersection, and distance computation. Unfortunately, the complexity of polyhedral convex hulls grows linearly with their input. We consider the problem of conservatively simplifying a convex hull to a specified number of half-spaces while minimizing added volume or surface area. By working in the dual representation, we propose an efficient $O(n \log n)$ greedy optimization. In comparisons, we show that existing methods either exhibit poor efficiency, tightness or safety. We demonstrate the success of our method on a variety of input shapes and downstream application domains.

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

Jacobson's dual greedy convex hull simplification is a useful practical algorithm with clear efficiency claims, but the added volume may not be close to optimal without guarantees or broad validation.

read the letter

Jacobson has a new greedy algorithm that simplifies convex hulls to fewer half-spaces while staying conservative, meaning the simplified hull always contains the original. It runs in O(n log n) by operating in dual space to pick the best planes to keep or remove. The paper does well at laying out the method clearly and running comparisons against prior simplification techniques. Those comparisons show advantages in speed, how little extra volume is added, and safety on the test cases. The demonstrations across different input shapes and uses in collision detection and such give a sense of where it applies in practice. One soft spot is the lack of any approximation guarantee. The greedy choice in dual space minimizes local volume increase at each step, but there is no proof or bound showing it stays close to the global minimum added volume for a given number of planes. The stress-test note about potential issues on long thin polyhedra is fair; without worst-case validation or more diverse failure-case testing, users have to trust the experiments. The citation pattern looks standard for the area, pulling in relevant prior work on convex hulls and simplification without obvious gaps. This paper is for computational geometry and computer graphics researchers who deal with bounding volumes for meshes. A reader who needs to reduce the complexity of hulls for faster queries would get concrete value from the algorithm and its implementation. It deserves peer review because the core idea is fresh, the efficiency is stated precisely, and the empirical results allow referees to assess the practical performance.

Referee Report

3 major / 2 minor

Summary. The paper addresses conservative simplification of convex hulls to a user-specified number of half-spaces while minimizing added volume or surface area. It introduces a dual-space representation that enables a greedy optimization algorithm claimed to run in O(n log n) time, and reports that this approach outperforms prior methods in efficiency, tightness, and safety. The method is demonstrated on diverse input shapes and applied to tasks including collision detection, ray intersection, and distance computation.

Significance. If the greedy dual-space selection reliably produces near-optimal conservative simplifications, the result would be useful for graphics and geometry applications that rely on tight bounding proxies, as it could reduce computational cost without introducing false negatives in intersection or distance queries. The O(n log n) scaling and explicit safety guarantee would be practical strengths if supported by analysis or extensive validation.

major comments (3)

[Abstract] Abstract and method description: the central O(n log n) greedy claim rests on dual-space half-space selection minimizing added volume, yet no approximation ratio, local-optimality proof, or worst-case bound on the deviation from the global minimum k-subset is provided. This directly affects the claim that the method is both efficient and reliably tight.
[Method] The safety argument (H' ⊇ H for all inputs) is asserted but not accompanied by a proof or exhaustive failure-case analysis; the dual mapping from primal volume increments to dual operations must be shown to preserve conservativeness on degenerate, high-curvature, or long-thin polyhedra, as a single bad removal order could violate the inclusion.
[Experiments] Comparison section: the reported superiority in tightness and safety is presented without quantitative tables showing added-volume ratios or failure rates across a controlled benchmark set (e.g., varying aspect ratios or vertex counts), making it impossible to assess whether the greedy choice systematically outperforms alternatives.

minor comments (2)

[Method] Notation for dual variables and the precise definition of the greedy selection criterion (volume vs. area) should be introduced with a small worked example early in the method section to improve readability.
[Preliminaries] The manuscript would benefit from an explicit statement of the input assumptions (e.g., general position, manifold boundary) and a short discussion of how the algorithm behaves when these are violated.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments, which highlight important aspects of our claims on efficiency, safety, and evaluation. We address each major comment below and will incorporate revisions to strengthen the manuscript.

read point-by-point responses

Referee: [Abstract] Abstract and method description: the central O(n log n) greedy claim rests on dual-space half-space selection minimizing added volume, yet no approximation ratio, local-optimality proof, or worst-case bound on the deviation from the global minimum k-subset is provided. This directly affects the claim that the method is both efficient and reliably tight.

Authors: The O(n log n) bound describes the running time of the greedy algorithm, which uses a dual-space priority queue to select the half-space removal that minimizes the immediate added volume (or area) at each step. We do not claim global optimality or provide an approximation ratio, as selecting the exact minimum-volume k-subset appears combinatorially hard. In the revision we will explicitly distinguish the complexity claim from any optimality guarantee, add a brief discussion of the heuristic nature of greedy selection, and note that empirical results (rather than worst-case bounds) support its practical tightness. revision: partial
Referee: [Method] The safety argument (H' ⊇ H for all inputs) is asserted but not accompanied by a proof or exhaustive failure-case analysis; the dual mapping from primal volume increments to dual operations must be shown to preserve conservativeness on degenerate, high-curvature, or long-thin polyhedra, as a single bad removal order could violate the inclusion.

Authors: Conservativeness follows from the dual-space construction: a half-space is removed only when its supporting plane lies strictly outside the current hull, so the intersection of the remaining half-spaces cannot shrink. We acknowledge that a formal inductive proof and explicit handling of degeneracies are missing. In the revised manuscript we will supply a concise proof that the inclusion H' ⊇ H is invariant under the greedy removal order, together with a short analysis (and accompanying figures) for degenerate, high-curvature, and thin polyhedra. revision: yes
Referee: [Experiments] Comparison section: the reported superiority in tightness and safety is presented without quantitative tables showing added-volume ratios or failure rates across a controlled benchmark set (e.g., varying aspect ratios or vertex counts), making it impossible to assess whether the greedy choice systematically outperforms alternatives.

Authors: We agree that the current comparison lacks the quantitative detail needed for rigorous assessment. The revised manuscript will include tables that report added-volume ratios, surface-area increases, and safety indicators (including any observed violations of conservativeness) on a controlled benchmark suite that systematically varies vertex count and aspect ratio. These tables will be placed in the experimental section and will directly compare our method against the baselines mentioned in the paper. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic construction is self-contained

full rationale

The paper proposes a direct algorithmic method for conservative convex hull simplification via dual-space greedy selection, claimed to run in O(n log n). No equations, parameters, or results are shown to reduce by construction to fitted inputs, self-definitions, or prior self-citations; the central claim is the construction and efficiency of the procedure itself, which stands independently of the target outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard convex geometry and dual-space equivalence; no new entities are postulated and no numerical parameters are fitted to data.

axioms (1)

domain assumption Convex hulls admit an equivalent dual representation in which half-spaces become points and simplification becomes a covering problem.
Invoked in the abstract when the authors state they work in the dual representation.

pith-pipeline@v0.9.0 · 5380 in / 1234 out tokens · 23415 ms · 2026-05-10T11:13:39.865237+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references

[1]

InIEEE/CVF Conference on Computer Vision and Pat- tern Recognition, CVPR 2022, New Orleans, LA, USA, June 18-24, 2022 (2022), IEEE, pp

[Ale22] ALEXAM.: Super-fibonacci spirals: Fast, low-discrepancy sam- pling of SO(3). InIEEE/CVF Conference on Computer Vision and Pat- tern Recognition, CVPR 2022, New Orleans, LA, USA, June 18-24, 2022 (2022), IEEE, pp. 8281–8290. 3 [BDH96] BARBERC. B., DOBKIND. P., HUHDANPAAH.: The quick- hull algorithm for convex hulls.ACM Trans. Math. Softw. 22, 4 (19...

2022
[2]

3, 5 [CGM11] CHANGC., GORISSENB., MELCHIORS.: Fast oriented bounding box optimization on the rotation groupSO(3,∖).ACM Trans

Blog post. 3, 5 [CGM11] CHANGC., GORISSENB., MELCHIORS.: Fast oriented bounding box optimization on the rotation groupSO(3,∖).ACM Trans. Graph. 30, 5 (2011), 122:1–122:16. 3 [CS89] CLARKSONK. L., SHORP. W.: Application of random sampling in computational geometry, II.Discret. Comput. Geom. 4(1989), 387–

2011
[3]

2 [GGM∗05] GANOVELLIP. C. F., GOBBETTIE., MARTONF., PONCHIO F., SCOPIGNOR.: Batched multi triangulation. In16th IEEE Visualiza- tion Conference, IEEE Vis 2005, Minneapolis, MN, USA, October 23-28, 2005, Proceedings(2005), IEEE Computer Society, pp. 207–214. 8 [GH97] GARLANDM., HECKBERTP. S.: Surface simplification using quadric error metrics. InProceeding...

2005
[4]

J., STOLFIJ.: Primitives for the manipulation of general subdivisions and computation of voronoi diagrams.ACM Trans

2 [GS85] GUIBASL. J., STOLFIJ.: Primitives for the manipulation of general subdivisions and computation of voronoi diagrams.ACM Trans. Graph. 4, 2 (1985), 74–123. 2 [Hop96] HOPPEH.: Progressive meshes. InProceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1996, New Orleans, LA, USA, August 4-9, 1996(1996), F...

1985
[5]

Visualization and Mathematics

https://libigl.github.io/. 5 [KRB21] KLIMENKOG., RAICHELB., BUSKIRKG. V.: Sparse convex hull coverage.Comput. Geom. 98(2021), 101787. 3 [LR00] LÓPEZM. A., REISNERS.: Efficient approximation of convex polygons.Int. J. Comput. Geom. Appl. 10, 5 (2000), 445–452. 1, 3, 7 [LR02] LÓPEZM. A., REISNERS.: Linear time approximation of 3d convex polytopes.Comput. Ge...

2021
[6]

1, 3, 7 [S∗19] SHARPN.,ET AL.: Polyscope,

7 [RSW01] REISNERS., SCHUETTC., WERNERE.: Dropping a vertex or a facet from a convex polytope.Forum Mathematicum 13(01 2001), 359–378. 1, 3, 7 [S∗19] SHARPN.,ET AL.: Polyscope,

2001
[7]

5 [Sei91] SEIDELR.: Small-dimensional linear programming and convex hulls made easy.Discret

www.polyscope.run. 5 [Sei91] SEIDELR.: Small-dimensional linear programming and convex hulls made easy.Discret. Comput. Geom. 6(1991), 423–434. 2 [SGG∗00] SANDERP. V., GUX., GORTLERS. J., HOPPEH., SNYDER J. M.: Silhouette clipping. InProceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2000, New Orleans, LA, ...

1991
[8]

I.: Decomposing images into layers via rgb-space geometry.ACM Trans

3, 5, 6 [TLG17] TANJ., LIENJ., GINGOLDY. I.: Decomposing images into layers via rgb-space geometry.ACM Trans. Graph. 36, 1 (2017), 7:1– 7:14. 3, 5 [Wan22] WANGZ.: Sdlp,

2017
[9]

Actaeon”, “Hermanubis-Broken

https://github.com/ZJU-FAST- Lab/SDLP. 5 [WLLS22] WEIX., LIUM., LINGZ., SUH.: Approximate convex decomposition for 3d meshes with collision-aware concavity and tree search.ACM Transactions on Graphics (TOG) 41, 4 (2022), 1–18. 1, 3, 6, 7 [ZGZJ16] ZHOUQ., GRINSPUNE., ZORIND., JACOBSONA.: Mesh arrangements for solid geometry.ACM Transactions on Graphics (TO...

2022