Provably Good Sampling and Meshing of Surfaces
Graphical Models, 2005 · paper · Computer science
Introduces loose ε-samples, which are easier to check and construct than ε-samples, and a simple algorithm producing sparse samples and meshes of smooth surfaces. The meshes match the surface's topology and approximate it closely, with the surface known only through an intersection oracle.
Checked: PDF from geometrica.saclay.inria.fr, fetched 4 Oct 2026. Page numbers are those of that PDF.
6 findings
Substance Proof of Lemma 7.2 (p.25): "the radius of Bx′ is at most 2rx, which is less than 1/3σ(x), thus (ux, vx, wx) is a persistent facet". Persistence (p.24) requires ri ≤ 1/3σ(ci) at the ball's centre ci = x′, not at x.
- p. 25 Proof of Lemma 7.2, last paragraph
the radius of Bx′ is at most 2rx, which is less than 1/3σ(x), thus (ux, vx, wx) is a persistent facet
- p. 24 Section 7, definition of persistent facet
such that ri ≤1/3σ(ci). Such a facet will be called a persistent facet
- p. 25 Construction of Ei
of radius less than min { 1/6dist(x, E′i \ {x}), dM(x), 1/6σ(x)}
Only the authors can say what is right here.
Judge's note: The p.24 definition is ri ≤ σ(ci)/3, and the proof of Lemma 7.1 uses σ at ci. The construction on p.25 gives only rx < σ(x)/6 and ‖x′−x‖ ≤ rx, so σ(x′) ≥ σ(x) − rx > (5/6)σ(x) and σ(x′)/3 > (5/18)σ(x) ≈ 0.278σ(x), while 2rx can approach σ(x)/3. I checked the counterexample. Take near-flat S, rx = 0.16σ(x), and x′ ∈ S at distance 0.99rx from x. Three points on the circle of radius 1.9rx about x′ fall inside Bx (since 0.91rx ≤ rx ≤ 2.89rx), and the axis of that circle passes through x′, so the construction rule is met. Take σ(y) = max(σ(x) − ⟨y−x, d⟩, σ(x)/2), which is positive and 1-Lipschitz. Then the radius 0.304σ(x) exceeds σ(x′)/3 = 0.2805σ(x), so the facet is not persistent as defined. Lemma 7.2 as stated is therefore not established by this proof. A smaller constant (e.g. 1/7σ(x)) would repair it.
Second check: another model agreed
Report a problem with this finding
Substance Table 1, Torus row, bipolar oracle: the printed 'Engine 0.31 | 88.7% | 63K | Oracle 0.39 | 11.3% | Total 0.7' does not hold together; the times give shares of about 44%/56%, not 88.7%/11.3%.
- p. 37 Table 1, Torus row, Bipolar oracle columns
0.31 88.7 63K 0.39 11.3 0.7
- p. 37 Table 1, Torus row, bipolar oracle columns
0.31 | 88.7 | 63K | 0.39 | 11.3 | 0.7
Only the authors can say what is right here.
Judge's note: I read the row on the upright page image. In the other rows engine+oracle equals the total and each % is that part's share of the total (e.g. Chair 2.7/3.02=89.4, printed 89.4). For the torus, 0.31+0.39=0.70 matches the total, but the shares do not match the printed percentages. The percentages would fit an oracle time of about 0.04. Only the authors can say which cell is wrong.
Second check: another model agreed
Report a problem with this finding
Substance Table 1, Tanglecube row, intersection oracle: 'Engine 2.77 | 2.9% | Oracle 118 | 97.1% | Total 121': 2.77/121 is 2.3% and 118/121 is 97.5%, not 2.9%/97.1%.
- p. 37 Table 1, Tanglecube row, Intersection oracle columns
2.77 2.9 168K 118 97.1 121
- p. 37 Table 1, Tanglecube row, intersection oracle
2.77 | 2.9 | 168K | 118 | 97.1 | 121
Only the authors can say what is right here.
Judge's note: Checked on the upright page image. The times add up to the total (120.77≈121), but the printed percentages do not match them. Other intersection rows agree to rounding (Intricate knot 2.56/113=2.3, printed 2.3). Rounding of the printed times cannot produce 2.9%.
Second check: another model agreed
Report a problem with this finding
Substance Table 1, Klein's bottle row, intersection oracle: 'Engine 0.15 | 3.5% | Oracle 41.2 | 96.5% | Total 41.5': 0.15/41.5 is 0.36%, not 3.5%, and 0.15+41.2=41.35.
- p. 37 Table 1, Klein's bottle row, Intersection oracle columns
0.15 3.5 101K 41.2 96.5 41.5
- p. 37 Table 1, Klein's bottle row, intersection oracle
0.15 | 3.5 | 101K | 41.2 | 96.5 | 41.5
Only the authors can say what is right here.
Judge's note: Checked on the upright page image. The engine time, the percentages and the total are mutually inconsistent. The percentages would fit an engine time of about 1.5, which is close to the bipolar engine time of 1.58 for the same surface. Only the authors can say which cell is wrong.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Proposition 4.2 (p.14): "consider the facet f′′ = (a, u′, w′′) of F1(u) that is incident to f′ through edge [a, u′]". The vertex a is undefined, and the umbrella in play is F1(v); presumably (v, u′, w′′) of F1(v) with edge [v, u′] is meant.
- p. 14 Proof of Proposition 4.2, last paragraph
consider the facet f′′ = (a, u′, w′′) of F1(u) that is incident to f′ through edge [a, u′]
Only the authors can say what is right here.
Judge's note: The p.14 image confirms the text. f′ = (v, u′, w′) is a facet of F1(v), so a facet adjacent to it within the umbrella shares edge [v, u′]. No vertex 'a' is introduced in this proof, and u is the vertex of f outside F1(v), so F1(u) is not the umbrella under consideration. The intended argument is clear and the proposition is unaffected.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Lemma 5.3 (p.21): "S does not intersect the open balls B(y, κ/2 dM(x)) and B(z, κ/2 dM(x))", where y, z lie on the bounding sphere of Bx (radius κ/2 φ(x)). This is false whenever φ(x) < dM(x).
- p. 21 Proof of Lemma 5.3
S does not intersect the open balls B(y, κ/2 dM(x)) and B(z, κ/2 dM(x))
- p. 21 Proof of Lemma 5.3
S does not intersect the open balls B(y, κ/2 dM(x)) and B(z, κ/2 dM(x)), where y and z are the intersection points of the normal of S in x with the bounding sphere of Bx
Only the authors can say what is right here.
Judge's note: From the p.21 image: y and z lie on ∂Bx, so ‖x−y‖ = (κ/2)φ(x). If φ(x) < dM(x), which is allowed because only φ ≤ dM is assumed, then x is inside the open ball B(y, (κ/2)dM(x)), and x ∈ E ⊂ S. Counterexample: κ = 1, φ = dM/2 gives ‖x−y‖ = dM/4 < dM/2. The figure draws the balls tangent at x, which fits only the case φ = dM. Repair: the balls B(y, (κ/2)φ(x)) and B(z, (κ/2)φ(x)) are tangent to S at x and have radius below dM(x), so they lie in the tangent medial balls and miss S. The rest of the proof uses only these balls, so Lemma 5.3 and Theorem 5.4 stand.
Second check: another model agreed
Report a problem with this finding
23 minor (typos and the like; most checked by the judge only)
Reference or label p.41: 'used with the interpolating surface of [7]', but the P3 discussion (pp.40-41) lists the surface-approximation strategies as [1, 8, 25] and describes [8] (Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions), not [7].
- p. 41 Section 11.3, experimental results
interpolating surface of [7]
- p. 40 Section 11.3, P3
In [8],
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: which Boissonnat–Cazals paper defines the interpolating surface used. Inside the paper, P3 introduces [8] and [1] as the S̃ constructions, and the experiment pairs [7] with [1]. Reference [7] is 'Natural Neighbour Coordinates of Points on a Surface'. [7] could be a mis-citation of [8], but only the authors can confirm.
Second check: another model agreed
Report a problem with this finding
Wording Abstract (p.1) and Introduction (p.2) say "the algorithm generates a sparse ε-sample E", but Lemma 8.2/8.4 guarantee only that "E is a loose ε-sample of S" (an ε(1+8.5ε)-sample by Corollary 4.10).
- p. 1 Abstract
the algorithm generates a sparse ε-sample E
- p. 2 Introduction, paragraph 6
the algorithm generates a sparse ε-sample E
- p. 26 Lemma 8.2
upon termination of the algorithm, E is a loose ε-sample of S
Only the authors can say what is right here.
Judge's note: Page images p.1 and p.2 show 'sparse ε-sample E'. On p.26, Lemma 8.2 concludes only 'loose ε-sample'. On p.17 the paper says 'The converse is not true' (loose ε-samples are not necessarily ε-samples), and Corollary 4.10 gives ε(1+8.5ε). Section 10 (text line 1779) uses the accurate wording 'sparse loose ε-sample'. The headline wording therefore overstates what is proved. This is minor because the two notions are asymptotically equivalent.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Lemma 3.4 (p.7): the dihedral angle is said to be at least π − 2(2ε3/(1−4ε3) + arcsin(ε3√3/(1−ε3))), "which is greater than π/2"; by the definition of ε3 (p.6) this expression equals π/2 exactly.
- p. 7 Proof of Lemma 3.4
which is greater than π/2
- p. 6 Section 2.3, definition of ε3
ε3 ≈0.12 is the smallest positive value of ε such that
Only the authors can say what is right here.
Judge's note: p.6 defines ε3 as the smallest ε with 2ε/(1−4ε) + arcsin(ε√3/(1−ε)) ≥ π/4. The left side is continuous and increasing, so at ε3 it equals π/4 (my own check gives ε3 ≈ 0.128). Hence π − 2(π/4) = π/2: the bound evaluated at ε3 is not strictly greater than π/2. The strict conclusion needs the bound evaluated at the actual ratios r/dM(c) < ε3, which the hypothesis provides. The step is faulty as printed, but Lemma 3.4 stands.
Second check: another model agreed
Report a problem with this finding
Wording Section 9.1 (p.27) assumes "θ < π/6", yet p.42 reports "As predicted in Section 9.1, the procedure terminated and removed all triangles with angles less than π/6", i.e. θ = π/6.
- p. 27 Section 9.1, end
From now on, we assume that θ < π/6
- p. 42 Text below Figure 8, about Figure 9
As predicted in Section 9.1, the procedure terminated and removed all triangles with angles less than π/6
- p. 27 Section 9.1
From now on, we assume that θ < π/6.
Only the authors can say what is right here.
Judge's note: The p.27 image shows 'we assume that θ < π/6'. On p.28, Lemma 9.1 requires β = 1/(2 sin θ) > 1, and Eq. (13) has 1/(β−1)². At θ = π/6, β = 1, so the Section 9.1 guarantee does not cover the threshold reported in the experiment on p.42. The authors may have used a slightly smaller θ; only they can say.
Second check: another model agreed
Report a problem with this finding
Wording Eq. (13), p.28: "|Ēε| = O(1/(β−1)² ∫∫S dx/lfs²(x))". Corollary 9.2 (κ = (β−1)/(2β−1)) with Theorem 5.4 gives the factor (2β−1)²/(β−1)², and the factor (2β−1)² is not bounded for all θ < π/6.
- p. 28 Eq. (13) and following paragraph, Section 9.1
|¯Eε| = O( 1/(β −1)2 ∫∫S dx/lfs2(x) )
- p. 28 Corollary 9.2
¯Eε is ( β−1/2β−1, lfs)-sparse.
Only the authors can say what is right here.
Judge's note: From the p.28 image: Theorem 5.4 gives |E| ≤ (64/3π)(1/κ²)∫∫, and 1/κ² = (2β−1)²/(β−1)². For β near 1 (θ near π/6) the factor (2β−1)² is bounded and the printed O(1/(β−1)²) holds. As θ → 0, β → ∞ and C/(β−1)²∫∫ → 0, while |Ēε| ≥ |Eε| ≥ 1 with lfs fixed by Eε. So the bound cannot hold uniformly over the stated range θ < π/6 unless the O(·) is read as β → 1. The same applies to the closing 'factor of O(1/(β−1)²)'. Termination and size-optimality for fixed θ are unaffected. The authors should state the regime of the O(·) or keep the factor (2β−1)².
Second check: another model agreed
Report a problem with this finding
Wording p.38 says the ratio between the timings of the two oracle versions is about '4 for the sphere', but Table 1 gives 4.4/0.76≈5.8 (total time) or 3.8/0.1=38 (oracle time) for the sphere.
- p. 38 Experimental results, discussion of Table 1
(e.g. 4 for the sphere), to several dozens for huge models (e.g. 40 for the intricate knot)
- p. 37 Table 1, Oracle Time/Del. columns
3.8
- p. 38 Section 11.1, discussion of Table 1
e.g. 4 for the sphere
- p. 37 Table 1, Sphere row
4.4
Only the authors can say what is right here.
Judge's note: I compared the p.38 text with the Table 1 image. The knot example ('40') roughly matches the total-time ratio of 113/2.57≈44, but the sphere's '4' matches neither the total-time ratio nor the oracle-time ratio. The text does not say which columns the ratio is taken from, so the authors should clarify.
Second check: another model agreed
Report a problem with this finding
Wording p.38 says the oracle-version timing ratio 'ranges from several units for small models ... to several dozens for huge models', but Table 1 gives about 226 for the small torus (158/0.7) and about 187 for the chair (565/3.02).
- p. 38 Section 11.1, first observation on Table 1
it ranges from several units for small models (e.g. 4 for the sphere), to several dozens for huge models
- p. 37 Table 1, Torus and Chair rows
158
Only the authors can say what is right here.
Judge's note: This is a different defect from C020: here the claimed range and its link to model size disagree with the table. The torus bipolar total may itself be affected by the C017 inconsistency, but the chair row alone already exceeds 'several dozens'.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Lemma A.3 (p.50): the quotient is called 'negative since f′(xa)−g′(xa) ≥ 0 and f′(xb)−g′(xb) ≤ 0', but these inequalities only make it non-positive; the next sentence correctly concludes '≤ 0'.
- p. 50 Proof of Lemma A.3
which is negative since f′(xa) −g′(xa) ≥0 and f′(xb) −g′(xb) ≤0
Only the authors can say what is right here.
Judge's note: My reworking: the numerator (f′−g′)(xb)−(f′−g′)(xa) is ≤0−0, i.e. ≤0, and the denominator xb−xa>0, so the quotient is ≤0. It can equal 0, so 'negative' in the strict sense is false as printed. The stated conclusion f″(xc)−g″(xc) ≤ 0, and hence the lemma, still stands, so this is a wording slip in one step.
Second check: another model agreed
Report a problem with this finding
Typo Introduction, p.2: "(non necessarily uniform)" should read "(not necessarily uniform)".
- p. 2 Introduction, paragraph 2
(non necessarily
Judge's note: The p.2 page image shows '(non necessarily uniform)'.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Claim 3.12.2 (p.12): the curvature "is more than 1/ρ according to Claim 3.12.1", but Claim 3.12.1 (p.11) gives "at least 1/ρ".
- p. 12 Proof of Claim 3.12.2
which is more than 1/ρ according to Claim 3.12.1
Judge's note: The p.11 image shows Claim 3.12.1: 'curvature of ξ is at least 1/ρ'. The p.12 image shows 'which is more than 1/ρ'. Inequality (8) is non-strict, so nothing downstream is affected.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.1, p.13: "We denote by Bf = (cf, rf) the only surface Delaunay ball" should read Bf = B(cf, rf).
- p. 13 Section 4.1, paragraph before Proposition 4.1
We denote by Bf = (cf, rf) the only surface Delaunay ball
Judge's note: The p.13 image shows 'B_f = (c_f, r_f)' with the 'B' missing on the right-hand side. Elsewhere the paper writes balls as B(c, r).
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Lemma 5.3 (p.21): "the radius of Bx is κ/2 phi(x)": the symbol φ is typeset as the word 'phi'.
- p. 21 Proof of Lemma 5.3, first line
the radius of Bx is κ/2 phi(x)
- p. 21
the radius of Bx is κ 2 phi(x), which is less than dM(x)
Judge's note: The p.21 image shows the italic word 'phi(x)' rather than φ(x).
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Theorem 5.4 (p.22): the middle sum is indexed "v∈E" while its summand is in x; it should be x∈E.
- p. 22 Proof of Theorem 5.4, last displayed inequality
Σ v∈E
Judge's note: The p.22 image shows Σ_{v∈E} with the summand in φ²(x), between two sums indexed x∈E.
Second check: none (judge only)
Report a problem with this finding
Typo Section 7 (p.25): "Aff(ux, vx, wx) (affine hull of ux, vx, wx))" has one closing parenthesis too many.
- p. 25 Section 7, construction of Ei
(affine hull of ux, vx, wx))
Judge's note: The p.25 image shows the double closing parenthesis. The parenthetical opens only once.
Second check: none (judge only)
Report a problem with this finding
Typo 'explicitely' is misspelled twice: 'whose expression is given explicitely' (p.33, §11.1) and 'is not given explicitely' (p.39, §11.2); it should be 'explicitly'.
- p. 33 Section 11.1, first paragraph
whose expression is given explicitely
- p. 39 Section 11.2, first paragraph
is not given explicitely
- p. 33 Section 11.1
given explicitely
- p. 39 Section 11.2
not given explicitely
Judge's note: Both misspellings appear in the page crops. Elsewhere (line 1747) the paper spells 'explicit' correctly.
Second check: none (judge only)
Report a problem with this finding
Typo p.41, §11.4: 'some code developped by M. Samozino' — 'developped' should be 'developed'.
- p. 41 Section 11.4
some code developped by M. Samozino
Judge's note: Seen in the page crop.
Second check: none (judge only)
Report a problem with this finding
Typo p.41 footnote 2: 'Ondulations are clearly visible' — the usual English form is 'Undulations'.
- p. 41 Footnote 2
Ondulations are clearly visible
Judge's note: Seen in the page crop. 'Ondulation' is the French form and only a rare variant in English, so this is cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [6]: 'Indian Institute of Technology, Kampur, 2001' — the place name should be 'Kanpur'.
- p. 45 Reference [6]
Indian Institute of Technology, Kampur, 2001
- p. 45 Reference [6]
Indian Institute of Technology, Kampur
- p. 45
Indian Institute of Technology, Kampur, 2001.
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the institute is IIT Kanpur. The page image reads 'Kampur'.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [11]: publisher printed as 'Birkhaüser'; it should be 'Birkhäuser'.
- p. 46 Reference [11]
Birkhaüser
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the publisher's name is spelled Birkhäuser. The page crop shows the umlaut on the u.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [11] ends '... Basel Boston Stuttgart, 1986' with no final period, unlike the neighbouring entries.
- p. 46 References [11]
Birkha¨user, Basel Boston Stuttgart, 1986
Judge's note: Seen in the page crop: [10] and [12] end with periods and [11] does not. Purely cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [29]: 'S. PLantinga and G. Vegter' — the author name should be 'Plantinga'.
- p. 47 Reference [29]
S. PLantinga and G. Vegter
- p. 47 Reference [29]
S. PLantinga
- p. 47
S. PLantinga and G. Vegter.
Judge's note: The page crop shows a capital L. The body text (p.44) spells the name 'Plantinga'.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Lemma A.3 (p.49): 'a neigbourhood Va of xa' — should be 'neighbourhood'.
- p. 49 Proof of Lemma A.3
a neigbourhood Va of xa
- p. 49 Proof of Lemma A.3
neigbourhood Va of xa
Judge's note: Seen in the page crop.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Lemma A.5 reads "the meridian m of ∂B than passes through p1, c′1, c′2 and p2"; "than" should be "that".
- p. 51 Proof of Lemma A.5, case 2
the meridian m of ∂B than passes through p1
- p. 51 Lemma A.5 proof, case 2
meridian m of ∂B than passes through
Judge's note: Checked crop C032-a (page 51). The printed text is "We consider the meridian m of ∂B than passes through p1, c′1, c′2 and p2." The relative pronoun "that" is clearly intended. Both reviewer notes describe this same typo.
Second check: none (judge only)