REVIEW 5 minor 13 references
Computing Non-Obtuse Triangulations with Few Steiner Points
T0 review · 0 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A local-search method on constrained Delaunay triangulations produces the winner of the CG:SHOP 2025 non-obtuse triangulation challenge, with best solutions on 116 of 150 instances.
desk verdict A credible competition-winning solver with released code; the empirical claim holds up, and the unproven termination step is a minor gap, not a flaw. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the maintained constrained Delaunay triangulation together with three geometric primitives: altitudeDrop, the point on the longest side of an obtuse triangle that splits it into two right triangles; polygonCenter, a point that connects to all vertices of a polygon in a non-obtuse triangulation whenever one exists; and the visibility-constrained Voronoi diagram of the CDT. The action-generation step builds the circleArrangement of all clipped circumcircles, and for each cell checks whether the polygonCenter of the corresponding polygon lies inside it. The evaluation function weights non-superseded obtuse triangles at 3.1 and superseded ones at 1.1, where a triangle is superseded if the longest side of another obtuse triangle is one of its shorter sides; a depth-k probabilistic search over the action graph approximates the best sequence of moves. This combination keeps every intermediate triangulation Delaunay while greedily steering toward a state with zero obtuse triangles.
What would settle it
Run the released solver on the 150 benchmark instances while logging, for every candidate polygonCenter insertion, the obtuse-triangle count of the CDT immediately before and after that insertion. A single candidate action whose insertion leaves the count unchanged or larger is a counterexample to the claimed strict-decrease property and breaks the termination argument.
Extended reading notes
Core claim
The central claim is practical: a solver that keeps a constrained Delaunay triangulation (CDT) and repeatedly applies local moves — inserting a new Steiner point, relocating an existing one, or replacing two adjacent Steiner points by one — can find non-obtuse triangulations with few Steiner points. The insertion moves are of three kinds: dropping a perpendicular onto the longest constrained side of an obtuse triangle, placing a point on a visibility-constrained Voronoi edge inside the triangle's clipped circumcircle so as to maximize distance to nearby vertices, or placing the polygonCenter of the polygon formed by the triangles whose clipped circumcircles contain a given arrangement cell. The relocation and deletion moves move a Steiner point (or a pair of points) to the polygonCenter of the polygon formed by its incident triangles, whenever such a center exists. Every candidate move is scored by the cost function eval(D) = #Steiner + 1.1 times (#superseded obtuse triangles) + 3.1 times (#non-superseded obtuse triangles), and a depth-k probabilistic variant approximates a minimax choice over the action graph. The authors report that this process terminated on all 150 challenge instances, produced the best solutions on 116 of them, matched the runner-up on 30, and was worse on the remaining 4.
Load-bearing premise
The load-bearing premise is that inserting the polygonCenter of a circleArrangement cell, whenever that center lies inside the cell, strictly decreases the number of obtuse triangles in the CDT; the paper states this in Section 2.2 without proof.
Editorial extensions
If this is right
- The method yields non-obtuse triangulations for all four challenge instance classes (rectilinear polygons, simple polygons, point sets, and exterior-of-polygon regions) without per-class tuning, so it transfers directly to new instances of those types.
- Reported Steiner-point counts grow roughly linearly with input size (fitted slopes between 0.25 and 0.81 across classes), suggesting the approach remains usable as instance size grows.
- Merging several independent solutions by swapping Steiner points inside sampled circles and re-solving can cut the Steiner count by up to 30%, so solution merging is a cheap route to better outputs.
- Because a large fraction of the triangles produced are right triangles, the solver is effectively leaning on the altitude-drop construction to keep all angles within the 90-degree bound.
Reading between the lines
- If the unproved strict-decrease property is true in general, the local search is terminating with a correctness proof; if a counterexample exists, the algorithm would still be a strong heuristic but would lack a termination guarantee.
- The same CDT-plus-local-moves architecture could be retargeted to acute triangulations or arbitrary angle bounds by swapping the polygonCenter primitive for the corresponding center that satisfies the desired bound.
- The cost constants 1.1 and 3.1 were not optimized by the authors, so tuning them per instance class, or making the depth-k sampling bias adaptive, may yield further Steiner-point reductions.
- The large gains from merging suggest that a portfolio of short searches with diverse random seeds could outperform a single long search, especially on the hardest instances.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper describes the winning entry for the CG:SHOP 2025 challenge on minimizing Steiner points in non-obtuse triangulations of planar straight-line graphs. The solver maintains a constrained Delaunay triangulation of the input PSLG and iteratively applies local-search moves (insert, relocate, or delete Steiner points) until no obtuse triangle remains; candidate moves are scored with a weighted cost function and a depth-limited probabilistic minimax-like evaluation, and final solutions are post-processed by merging and re-solving. On the 150 official instances, the authors report achieving the best Steiner-point count in 116 cases, tying the runner-up team 'Gwamegi' in 30 cases, and being beaten by Gwamegi in 4 cases. Source code is released.
Significance. If the reported benchmark numbers are correct, the paper documents the state of the art for a competitive practical problem, and the released code makes the result reproducible. The main strengths are the clean engineering design, the honest and specific reporting of the competition outcome, and the decision to publish source code. The theoretical novelty is modest\u2014there is no new lower bound or approximation guarantee, and the termination argument is heuristic\u2014but this is consistent with the CG Challenge format. The claim that the algorithm produces a non-obtuse triangulation whenever it terminates is weak but true, and the competition result is an empirical claim independent of the unproven monotonicity statement discussed below.
minor comments (5)
- [Section 2.2, 'Insertion'] The statement that adding the polygonCenter of PC, when it lies in the circleArrangement cell C, 'ensures that the number of obtuse triangles in the CDT strictly decreases' is asserted without proof. This property is not needed for the reported 116/4/30 competition outcome, but it is the only stated rationale for monotone progress of the local search; please add a proof sketch using the star-shapedness of the conflict cavity and the defining property of polygonCenter, or explicitly mark the statement as an empirical observation rather than a guarantee.
- [Section 2.1, 'polygonCenter'] The slab/disk characterization gives a necessary and sufficient condition for each boundary triangle to be non-obtuse, but for a general simple polygon it does not by itself guarantee that the chosen point lies inside the polygon or sees every boundary vertex. Please clarify that the primitive is applied only to star-shaped polygons such as the cavities PC, or that the implementation additionally verifies point-in-polygon and visibility.
- [Section 2.3, Eq. (1)] The term 'supersedes' is easy to misread; a one-sentence rephrasing, for instance 'T' is superseded by T if the longest side of T is one of the shorter sides of T\'', would remove the ambiguity about which triangle is prioritized.
- [Section 3] The paper reports roughly 300,000 CPU hours but does not specify the wall-clock time per instance, the number of independent runs, or the random seeds used for the final solutions; please provide this protocol information so that the empirical comparison is reproducible.
- [References] Reference [3] contains a placeholder title 'x.' and an incomplete bibliographic entry; please correct it.
Circularity Check
No significant circularity: the paper's claims are external benchmark outcomes, and no derivation step reduces to its own inputs.
full rationale
No circular dependency found. The paper's central claim is an empirical competition result: its solutions were best for 116 of 150 instances, tied on 30, and Gwamegi was best on 4, as benchmarked against the official CG:SHOP 2025 challenge and its scoreboard [9]. The evaluation function in Eq. (1) uses constants 1.1 and 3.1, but the authors explicitly state in Section 2.3 that they did not optimize the constants; moreover, that function only ranks internal candidate moves of a local-search heuristic, not the paper's target quantity, which is the number of Steiner points in the final triangulation. The unproven strict-decrease property in Section 2.2 (adding the polygonCenter of PC when it lies in cell C strictly decreases the number of obtuse triangles) is a geometric lemma, not an input assumption: it would matter for proving guaranteed termination, but the paper only claims non-obtuse triangulations whenever the process terminates, and the reported termination on all 150 instances is an observed empirical fact. The property is not used to define the output or the evaluation metric, and no fitted parameter is renamed as a prediction. All cited prior work (Bishop's algorithm, Erten-Ungor, the visibility-constrained Voronoi diagram, and the challenge overview) is external to the authors and is not invoked as a self-citation chain to force the algorithm's choices. No definitional equivalence between inputs and outputs appears anywhere in the manuscript. Therefore the circularity score is 0.
Assumptions & free parameters
free parameters (5)
- eval weight for superseded obtuse triangles =
1.1
- eval weight for non-superseded obtuse triangles =
3.1
- minimax depth k =
k=3 (and 0 for some runs)
- random action sample size S =
unspecified
- merging circle radius =
unspecified
assumptions (4)
- standard math A non-obtuse triangulation is a Delaunay triangulation (local Delaunay condition via inscribed angle theorem).
- standard math For two points p and q, x forms a non-obtuse triangle pqx iff x lies in the slab between the hyperplanes through p and q normal to q-p and outside the disk with diameter pq.
- domain assumption The union of triangles whose clipped circumcircle contains a cell C forms a polygon PC, and adding a point v in C replaces the edges of D in PC with segments from v to vertices of PC.
- ad hoc to paper Adding the polygonCenter of PC when it lies in C strictly decreases the number of obtuse triangles.
Cite this review
Pith. "Pith review of Computing Non-Obtuse Triangulations with Few Steiner Points." pith.science (2026). https://pith.science/paper/RTGC7FE4
@misc{pith2026250523375,
author = {Pith},
title = {Pith review of: Computing Non-Obtuse Triangulations with Few Steiner Points},
year = {2026},
howpublished = {\url{https://pith.science/paper/RTGC7FE4}},
note = {Machine review of arXiv:2505.23375}
}
read the original abstract
We present the winning implementation of the Seventh Computational Geometry Challenge (CG:SHOP 2025). The task in this challenge was to find non-obtuse triangulations for given planar regions, respecting a given set of constraints consisting of extra vertices and edges that must be part of the triangulation. The goal was to minimize the number of introduced Steiner points. Our approach is to maintain a constrained Delaunay triangulation, for which we repeatedly remove, relocate, or add Steiner points. We use local search to choose the action that improves the triangulation the most, until the resulting triangulation is non-obtuse.
Reference graph
Works this paper leans on
-
[1]
Incremental algorithm and local search for minimum non-obtuse triangulations (CG challenge)
Taehoon Ahn, Jaegun Lee, Byeonguk Kang, and Hwi Kim. Incremental algorithm and local search for minimum non-obtuse triangulations (CG challenge). 2025. These proceedings
work page 2025
-
[2]
Baker, Eric Grosse, and Conor S
Brenda S. Baker, Eric Grosse, and Conor S. Rafferty. Nonobtuse triangulation of polygons. Discret. Comput. Geom. , 3:147--168, 1988. https://doi.org/10.1007/BF02187904 doi:10.1007/BF02187904
-
[3]
Marshall W. Bern, Scott A. Mitchell, and Jim Ruppert. x. volume 14, pages 411--428, 1995. https://doi.org/10.1007/BF02570715 doi:10.1007/BF02570715
-
[4]
On nonobtuse simplicial partitions
Jan Brandts, Sergey Korotov, Michal Kr \' zek, and Jakub Solc. On nonobtuse simplicial partitions. SIAM Rev. , 51(2):317--335, 2009. https://doi.org/10.1137/060669073 doi:10.1137/060669073
-
[5]
Y. Burago and V. Zalgaller. Polyhedral embedding of a net. Vestnik Leningrad. Univ , 15(7):66--80, 1960
work page 1960
-
[6]
Computing acute and non-obtuse triangulations
Hale Erten and Alper \" U ng \" o r. Computing acute and non-obtuse triangulations. In Prosenjit Bose, editor, Proceedings of the 19th Annual Canadian Conference on Computational Geometry, CCCG 2007, August 20-22, 2007, Carleton University, Ottawa, Canada , pages 205--208. Carleton University, Ottawa, Canada, 2007. URL: http://cccg.ca/proceedings/2007/09a2.pdf
work page 2007
-
[7]
Computing triangulations without small and large angles
Hale Erten and Alper \" U ng \" o r. Computing triangulations without small and large angles. In Francois Anton, editor, Sixth International Symposium on Voronoi Diagrams, ISVD 2009, Copenhagen, Denmark, June 23-26, 2009 , pages 192--201. IEEE Computer Society, 2009. https://doi.org/10.1109/ISVD.2009.32 doi:10.1109/ISVD.2009.32
-
[8]
Quality triangulations with locally optimal steiner points
Hale Erten and Alper \" U ng \" o r. Quality triangulations with locally optimal steiner points. SIAM J. Sci. Comput. , 31(3):2103--2130, 2009. https://doi.org/10.1137/080716748 doi:10.1137/080716748
Show all 13 references
-
[9]
Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra. Minimum non-obtuse triangulations: The CG:SHOP Challenge 2025 , 2025. URL: https://arxiv.org/abs/2504.04412
2025 arXiv
-
[10]
Acute triangulations of polygons
Hiroshi Maehara. Acute triangulations of polygons. European Journal of Combinatorics , 23(1):45--55, 2002
2002
-
[11]
Maschler, S
M. Maschler, S. Zamir, and E. Solan. Game Theory . Cambridge University Press, 2013. URL: https://books.google.de/books?id=lqwzqgvhwXsC
2013
-
[12]
S. Saraf. Acute and nonobtuse triangulations of polyhedral surfaces. European Journal of Combinatorics , 30(4):833--840, 2009
2009
-
[13]
Interleaving delaunay refinement and optimization for 2d triangle mesh generation
Jane Tournois, Pierre Alliez, and Olivier Devillers. Interleaving delaunay refinement and optimization for 2d triangle mesh generation. In Michael L. Brewer and David L. Marcum, editors, Proceedings of the 16th International Meshing Roundtable, October 14-17, 2007, Seattle, Wa...
2007 doi
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.