discretization procedure, if points x, y ∈ Rd at distance ε are assigned different integer points by the algorithm, then N, the number of times segment crosses the boundary between color regions, must be at least 1. The probability of this event is at most E[N]. Combining Theorems 1 and 3, this probability is at most 2pε (up to an error of ε2, but this error can be eliminated) as claimed.

Next we outline the proofs of Theorems 1, 2, and 3.

We begin with the main result, Theorem 1. Let D~ = closure
({x : f ~Z (x) > H}) be a random “droplet pattern” as would be
chosen in a single stage of Algorithm 1; that is, D~, is a ran-
dom droplet along with all of its integer translations. Let I
denote the event that D~ intersects the segment , and let
M denote the number of intersection points between the
boundary of D and the segment . Since is very short,
the first color region that touches the segment is very likely
to completely enclose it. Thus, even conditioned on event I
occurring, M is quite likely to be 0. More precisely, our main
goal is to show that
and hence up to order ε.
As for the numerator of Equation ( 2), the inner integral
equals the vertical distance traveled by a particle moving
along the curve gz; this can be seen by partitioning the
curve into small, nearly straight arcs, and considering
their contribution to the integral. Hence, the inner integral
equals . Since up to order ε on [0, ε],

up to order ε2 as claimed in Equation ( 1).

To prove Theorem 2, we need a method for computing surface area. We use the following (see Santalo25)

( 1)

Theorem 4 (Buffon’s Needle Theorem): Let S be a d-periodic piecewise smooth surface. “Drop a needle” of length 0 < ε < 1; i.e., let x be a random point in [0, 1)d, let u be a random vector of length 1, and let y = x + ε ⋅ u. If N denotes the number of intersections of the needle with the surface S, then

Using Equation ( 1), it is not hard to prove Theorem 1. To see
this, consider the first stage of the algorithm’s execution in
which a droplet pattern touching is chosen. Let M1 be the
number of intersections between and the boundary of
this droplet pattern. Equation ( 1) tells us that E[M1] ≈ ε ⋅ b.
Recalling that N denotes the number of times crosses the
boundary between differently colored regions at the termi-
nation of the algorithm, we certainly have N ≥ M1. However,
it is unlikely that N will exceed M1. Indeed, consider the
second stage of the algorithm’s execution in which a drop-
let pattern touching is chosen, and define M2 to be the
number of intersections between the boundary of this drop-
let pattern and . Again, by Equation ( 1) we have E [M2] ≈
ε ⋅ b. But furthermore, these M2 intersections can only con-
tribute to N if the first droplet pattern to touch failed to
completely enclose it. The probability of this is precisely
Pr[M1 > 0] ≤ E [M1] ≈ ε ⋅ b. Hence, the expected contribution
to N from this second stage is at most (ε ⋅ b) 2. Continuing the
argument, we are able to upper-bound E [N] by
( 4)

where cd is the dimension-dependent–constant E [ u1].

Note that the value of cd is not important, as it gets
cancelled out in our analysis. Given the execution of
Algorithm 1, we can apply Buffon’s Needle Theorem to
compute the quantity A from Theorem 2. We obtain that
E [A] = E [N]/(cd ⋅ ε), where in E [N] the probabilistic experi-
ment is both the execution of Algorithm 1 and the random
choice of the “needle.” Applying Theorem 1 for each choice
of the needle, we obtain
( 5)

We now describe the proof of Equation ( 1). Since the proba-
bilistic choice of D~ is invariant under any translation of Rd, we
may assume x = 0 and hence y = ε ⋅ u. For a given z ∈ [0, 1)d, let
gz : [0, ε] → R≥0 denote the restriction of f z to the line segment
from 0 to ε ⋅ u and write G(z) =  gz∞. The event I occurs
when the randomly chosen Z and H satisfy H < G(Z), and the
quantity M is equal to #{s ∈ [0, ε] : gz (s) = H}. (Here, we have
discounted events with probability 0.) Hence,
up to an additive error of order ε. Since ε can be arbitrarily
small, Equation ( 5) is in fact an exact equality. And further,
for each fixed vector ∇f (z), the quantity Eu [|⟨∇f (z), u⟩|]
equals  f (z) ⋅ cd. Substituting this into Equation ( 5) proves
Theorem 2.

where we also used that ∫ f = ∫ g2 = 1. Since f is a proper den-
sity function, g’s periodic extension is smooth and 0 on the
boundary of [0, 1]d. We may therefore rewrite g using the
multidimensional sine series:
( 2)

( 7)

Regarding the denominator of this expression, G(Z) = gz(0) =
f (Z) up to an additive error of order ε by Taylor’s theorem,
Differentiating Equation ( 7) and applying Parseval’s theo-
rem, we get