Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator

Describes Triangle, a C program for two-dimensional mesh generation and Delaunay triangulation. It discusses implementation choices: triangulation algorithms, data structures, mesh refinement using Ruppert's algorithm, and economical use of exact arithmetic for robustness.

Checked: PDF from people.eecs.berkeley.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.

0 findings

3 minor (typos and the like; most checked by the judge only)

Wording p.1: "Alternating cuts speed the algorithm and, when exact arithmetic is disabled, reduce its likelihood of failure." Yet in Table 1 the non-robust vertical-cut version is faster than alternating cuts on Boundary of Circle (0.17 vs 0.27, 2.1 vs 4.0, 26 vs 56 s).

p. 1 Section 2, right column
Alternating cuts speed the algorithm and, when exact arithmetic is disabled, reduce its likelihood of failure.
p. 2 Table 1, Div&Conq non-robust rows, Boundary of Circle columns
0.17

Judge's note: Checked the p.1 crop and the Table 1 image on p.2. Non-robust Div&Conq, Boundary of Circle: alternating 0.27 / 4.0 / 56 s against vertical 0.17 / 2.1 / 26 s. In every other comparable cell alternating cuts are faster (all robust cells, and the non-robust Uniform cells), and the non-robust vertical-cut runs fail on Tilted Grid. So the general claim has one exception in the paper's own table that the text does not mention. Either reading of the sentence is defensible, so I treat this as a minor wording point.

Second check: another model agreed

Report a problem with this finding

Wording Table 1 caption: "a tilted 1000 × 1000 square grid", but the table also reports Tilted Grid timings for 10,000 and 100,000 points, and the caption does not give the grid size for those runs.

p. 2 Table 1 caption
and a tilted 1000 × 1000 square grid.
p. 2 Table 1 header
Number of points 10,000 100,000 1,000,000
p. 2 Table 1 header
Tilted Grid

Only the authors can say what is right here.

Judge's note: Checked the p.2 image. The caption gives a single grid size, 1000 × 1000, which is 1,000,000 points. The table has Tilted Grid columns at 10,000, 100,000 and 1,000,000 points. Presumably smaller grids were used for the smaller columns, but this is not stated anywhere.

Second check: another model agreed

Report a problem with this finding

Typo p.8, Section 4: "more time may be needed for points sets with many near-degeneracies" should read "point sets".

p. 8 Section 4, right column, paragraph on Table 1 overhead
for points sets with many near-degeneracies
p. 8 Section 4, right column, paragraph on robust-test overhead
though more time may be needed for points sets with many near-degeneracies

Judge's note: The p.8 image (right column, first paragraph) shows "points sets" as printed. Elsewhere the paper writes "point sets".

Second check: none (judge only)

Report a problem with this finding