Spherical Cap Discrepancy of Perturbed Lattices Under the Lambert Projection

Abstract

For any given full rank lattice $\Lambda$ and natural number K, we consider the point set $P(K)=\Lambda /K\cap (0,1)^2$, with $N=\#P(K)\approx K^2$, and bound the spherical cap discrepancy of the projection of these points under the Lambert map to the unit sphere. The bound is of order $1/\sqrt{N}$, with leading coefficient given explicitly and depending on $\Lambda$ only. The proof is established using a lemma that bounds the number of intersections of certain curves with fundamental domains that tile $\mathbb {R}^2$, and even allows for local perturbations of $\Lambda$ without affecting the bound, proving to be suitable for numerical applications. A special case yields the smallest constant for the leading term of the cap discrepancy for deterministic algorithms up to date.

1 Introduction and Main Result

The problem of distributing N-many points $P_N=\{p_1,\dots ,p_N\}$ uniformly on a sphere is well known and has applications in numerical integration, approximation, cartography and the applied sciences, see [13, 25, 27] for some reviews surveying over a century of development.

There are several different notions of uniformity of distribution for a finite point set $P_N$: one example is the energy, which is the sum of all pairwise interactions of points under a given lower semi-continuous potential F. When $F(x,y)=\Vert x-y\Vert ^{-s}$ one refers to the corresponding energy as “Riesz s-energy” and minimizers of this potential have been intensively investigated, see for instance the comprehensive monograph by Borodachov et al. [12]. Another notion of uniformity is that of separation distance, i.e., the minimum of the pairwise distances of distinct elements among $P_N$. Our main result uses the notion of spherical cap discrepancy.

Definition 1.1

Let $P_N=\{p_1,\dots ,p_N\}\subset \mathbb {S}^2$. The spherical cap discrepancy is

$$\begin{aligned} \mathcal {D}(P_N)=\sup _{w\in \mathbb {S}^2}\sup _{-1\le t\le 1}\hspace{0.83328pt}\left| \hspace{0.66666pt}\frac{1}{N}\sum _{j=1}^N\chi _{C(w,t)}(p_j)-\sigma (C(w,t))\right| . \end{aligned}$$

Here $\mathbb {S}^2\subset \mathbb {R}^3$ is the unit two-sphere, i.e., the set of all unit vectors with norm induced by the standard dot product $\langle \,{\cdot },\,{\cdot }\,\rangle$. A spherical cap with center $w\in \mathbb {S}^2$ and height $t\in (-1,1)$ is the set

$$\begin{aligned} C(w,t)=\{x\in \mathbb {S}^2\mid \langle w,x\rangle \ge t\}. \end{aligned}$$

The boundary of a set S is denoted by $\partial S$, thus

$$\begin{aligned} \partial C(w,t)=\{x\in \mathbb {S}^2\mid \langle w,x\rangle =t\}, \end{aligned}$$

and $\sigma$ is the normalized surface measure of $\mathbb {S}^2$, such that $\sigma \hspace{0.33325pt}(C(w,t))=(1-t)/2$. The characteristic function of a set A is $\chi _A$, i.e., $\chi _A(x)=1$ iff $x\in A$, and 0 otherwise. An application of discrepancy to high-dimensional integration problems is the so-called “Koksma–Hlawka” inequality:

$$\begin{aligned} \left| \hspace{0.77774pt}\frac{1}{N}\sum _{j=1}^Nf(p_j)-\int _{\mathbb {S}^2} f\,\textrm{d}\sigma \right| \le \hat{\mathcal {D}}(P_N)\hspace{0.49988pt}\mathcal V(f), \end{aligned}$$

where $\hat{\mathcal {D}}$ is a notion of discrepancy (not restricted to the spherical cap discrepancy) and $\mathcal V(f)$ is a constant depending on the function f, see [15, 20].

This paper deals with point sets on the two-sphere which are derived from perturbations of any full rank lattice under a specific equal area map. This adds to the list of known constructions with good distribution properties. For the reader’s convenience, we give below a list of other well-known point sets on $\mathbb {S}^2$, including their reference of origin and other works investigating them.

	Origin	Invstigtd.
Probabilistic algorithms
Uniformly at random	[16]	[1, 14]
Ensembles based on determinantal point processes	[22]	[2, 9]
Roots of random polynomials in $\mathbb {R}^2\rightarrow \mathbb {S}^2$	[11]	[3]
The diamond ensemble (can also be made deterministic)	[8]	[8, 18]
Point sets based on jittered sampling	[5, 7]	[6]
Deterministic algorithms
Spiral points	[4, 24]	[21]
Hierarchical, equal area and iso-latitude pixelation	[19]	[21]
Point sets using group action	[23]	[23]
Spherical Fibonacci lattice	[1]	[1]
Spherical Fibonacci grid	[26]	[21]

We will prove a bound on the spherical cap discrepancy of our point constructions which is of the same order as the best results obtained so far for deterministic point sets found in the literature. An open (and hard) problem is to improve these bounds to the order obtained in a fundamental result due to Beck in [5, 6], where we find the existence of points $P_N^{\star }$ and constants independent of N, such that

$$\begin{aligned} cN^{-3/4} \le \mathcal {D}(P_N^{\star }) \le CN^{-3/4}\sqrt{\log N}. \end{aligned}$$

The construction of Beck is probabilistic and an algorithm to generate random point sets with discrepancy matching this upper bound with high probability was obtained for instance in [2].

Bounds for deterministic point sets are usually hard to derive and were first achieved by Lubotzky et al. in [23] with an upper bound of the order $(\log N)^{2/3}N^{-1/3}$. Aistleitner et al. showed in [1] that for spherical digital nets and spherical Fibonacci lattices the spherical cap discrepancy is upper bounded by an order of $N^{-1/2}$. Further bounds were given for the diamond ensemble by Etayo in [18] and for HEALPix generated points by Hofstadler, Mastrianni, and the author in a preprint, where both point sets are shown to have a spherical cap discrepancy of order $N^{-1/2}$.

Etayo opened the contest to find deterministic point sets $P_N$ which allow for the smallest constant bounding $\sqrt{N}\mathcal {D}(P_N)$, where she took the lead in [18] with the Diamond ensemble and a bound of $4+2\sqrt{2}$. We will identify a family of point sets where $\sqrt{18}$ suffices, see Sect. 3.1.

We construct point sets based on the method deployed in [1], which originated in [17]. Let $\mathrm {GL(\mathbb {R}^2)}$ be the group of invertible $2\times 2$ matrices acting on $\mathbb {R}^2$ with identity matrix $\mathbbm {1}$. The Frobenius norm of the matrix Q is $\Vert Q\Vert _F=\sqrt{{\text {trace}}Q^tQ}$, the Lebesgue measure on $\mathbb {R}^2$ is $\lambda$, and $e_1,e_2$ denote the standard basis of $\mathbb {R}^2$.

Definition 1.2

A lattice $\Lambda ^Q$ is a set $Q\mathbb {Z}^2$ for some $Q\in \mathrm {GL(\mathbb {R}^2)}$. The associated scaled tiling via a fundamental domain $\Omega ^Q=Q[0,1)^2\subset \mathbb {R}^2$ and $K\in \mathbb {N}$ is

$$\begin{aligned} \mathbb {R}^2=\bigcup _{p\in \Lambda ^Q}T_K(p),\quad \ \ \text {where}\quad T_K(p)=\frac{1}{K}\hspace{0.55542pt}(p+\Omega ^Q). \end{aligned}$$

Let $I^2=[0,1)\times (0,1)$ denote the unit square with three boundary sides removed, then for fixed $K\in \mathbb {N}$ we choose arbitrary $z_K^p\in T_K(p)$ for $p\in \Lambda ^Q$ and define a point set

$$\begin{aligned} P^Q(K)=\{z_K^p\mid p\in \Lambda ^Q\}\cap I^2. \end{aligned}$$

See Fig. 1b. The Lambert map $L:I^2\rightarrow \mathbb {S}^2$, which we introduce later, identifies two sides of $\partial I^2$ and maps two sides to the poles—and this identification has an effect on the discrepancy, see Fig. 1. To bound it we define a parametrization $\rho :[0,4]\rightarrow \partial I^2$ via $f(x):=\max {(\min \hspace{0.7222pt}(x,1)+\min \hspace{0.7222pt}(2-x,0),0)},$

$$\begin{aligned} x\mapsto \rho (x)=f(x)\hspace{0.49988pt}e_1+f(4-x)\hspace{0.49988pt}e_2. \end{aligned}$$

(1)

Before we state our main result in Theorem 1.3, we need to introduce three terms, which are bounded above by constants depending on Q only, as we will show:

• 1) Let $N^Q(K)=\#P^Q(K)$ be the number of points in $P^Q(K)$, and set

  $$\begin{aligned} d^Q(K)=\frac{1}{K}\hspace{0.55542pt}\biggl |N^Q(K)-\frac{K^2}{|{\det \hspace{0.33325pt}(Q)}|}\biggr |. \end{aligned}$$

• 2) Set

  $$\begin{aligned} C_L^Q=\sup _{w\in \mathbb {S}^2}\,\sup _{-1\le t\le 1}{\text {length}}{\bigl (Q^{-1}\bigl (L^{-1}(\partial C(w,t)\cap \mathbb {S}^2_p)\bigr )\bigr )}, \end{aligned}$$

• 3) and with the short hand notation $[a,b]^c:=[0,a]\cup [b,1]$ we define

  $$\begin{aligned} M^Q(K)\,=\!\sup _{\begin{array}{c} S\in \{[a,b],[a,b]^c:\\ 0\le a<b\le 1\} \end{array}}\frac{K}{|{\det \hspace{0.33325pt}(Q)}|}\left| \,\sum _{p\in {\text {Ad}}\hspace{0.49988pt}(S,K)} \biggl (\frac{\chi _{P^Q(K)}(z^p_K)}{N^Q(K)}-\lambda \hspace{0.33325pt}(T_K(p)\cap I^2)\biggr )\right| , \end{aligned}$$

  where we sum over all p, such that the interior of $T_K(p)$ intersects $\partial I^2$ at some “height” in S: We define $R(S)=\{x\in [0,4]\mid f(4-x)\in S\}$ for $S\subset [0,1]$ and f as in (1), to be all x with $\langle \rho (x),e_2\rangle \in S$; then

  $$\begin{aligned} {\text {Ad}}\hspace{0.49988pt}(S,K)=\{p\in \Lambda ^Q\mid T_K(p)^o\cap \rho (R(S))\ne \emptyset \}. \end{aligned}$$

The term $M^Q(K)$ bounds the discrepancy that arises around $L(\partial I^2)$, while taking the geometry of images of spherical caps under $L^{-1}$ into account.

Fig. 1

Picture a is the image under the Lambert map of picture b. The dots represent $P^Q(K)$, the S-shaped curve is $L^{-1}(\partial C)$ for a spherical cap C with the north pole in its interior, see Fig. 2. Contributing factors to the spherical cap discrepancy are fluctuations: of the total number of points, of points in $T_K(p)$ intersected by $\partial C$ (shaded in blue) and of points in $T_K(p)$ intersected by $\partial I^2$ (shaded in red), which are represented by $d^Q(K)$, $C^Q(K)$, and $M^Q(K)$

Theorem 1.3

(main result)   Let $Q\in \mathrm {GL(\mathbb {R}^2)}$, $K\in \mathbb {N}$, and $P^Q(K)$ be chosen as in Definition 1.2 with $N=N^Q(K)$. Then

$$\begin{aligned} \mathcal {D}(L(P^Q(K)))\le \bigl (d^Q(K)+\sqrt{2}\cdot C_L^Q+M^Q(K)\bigr )\frac{\sqrt{|{\det (Q)}|}}{\sqrt{N}}+O(N^{-1}). \end{aligned}$$

Remark

A possible choice for $P^Q(K)$ is $(K^{-1}\Lambda ^Q)\cap I^2$, and Theorem 1.3 shows that small inaccuracies in numerical representation of the positions of these elements do not affect the bound on discrepancy.

A less precise but more succinct bound is given by the following:

Corollary 1.4

Let $Q\in \mathrm {GL(\mathbb {R}^2)}$, $K\in \mathbb {N}$, and $P^Q(K)$ be chosen as in Definition 1.2 with $N=N^Q(K)$. Then

$$\begin{aligned} \mathcal {D}(L(P^Q(K)))\le \frac{\Vert Q\Vert _F}{\sqrt{|{\det (Q)}|}}\cdot \frac{8+3\sqrt{2}}{\sqrt{N}}+O(N^{-1}). \end{aligned}$$

Proof

This follows from Theorem 1.3 with Lemmas 2.2, 2.3, and 2.8, and the remark after it. $\square$

Outline of the paper. In Sect. 2 we first state the definition of the Lambert equal area map and prove a bound on $C_L^\mathbbm {1}$. Next we introduce the notion of an n-convex curve, and then prove in Lemma 2.7 a bound on how many fundamental domains of $(1/K)\hspace{0.49988pt}\Lambda ^Q$ are intersected by it; this result constitutes the backbone of this work. The section then ends with a bound on $d^Q(K)$ and a proof of Theorem 1.3. In Sect. 3 we apply Theorem 1.3 to specific cases, thus obtaining many deterministic point sets with the least constant for the leading term up to date.

2 Intermediate Results and Proof of Theorem 1.3

2.1 The Lambert Map

Fig. 2

Illustration of the Lambert map. Boundaries of spherical caps on a sphere in a, in b we see their projection to the enveloping cylindrical surface, which is “cut”, “flipped”, and scaled to the unit square in c

By $\mathbb {S}^2_p$ we denote the punctured unit sphere, i.e., $\mathbb {S}^2$ with the poles removed.

Definition 1.5

The Lambert map L is a well-known area preserving map, i.e., for open sets $U\subset I^2$ and the Lebesgue measure $\lambda$, we have $\lambda (U)=\sigma (L(U))$, where

$$\begin{aligned} L:I^2&\rightarrow \mathbb {S}^2_p,\\ (x,y)&\mapsto \begin{pmatrix}2\sqrt{y-y^2}\cos 2\pi x\\ 2\sqrt{y-y^2}\sin 2\pi x\\ 1-2y\end{pmatrix}, \end{aligned}$$

and the inverse is given in terms of the standard parametrization¹ of $\mathbb {S}^2$,

$$\begin{aligned} \begin{aligned} L^ {-1}:\mathbb {S}^2_p&\rightarrow I^2,\\ \begin{pmatrix} \cos \phi \sin \theta \\ \sin \phi \sin \theta \\ \cos \theta \end{pmatrix}&\mapsto \frac{1}{2\pi } \begin{pmatrix}\phi \\ \pi \hspace{0.33325pt}(1-\cos \theta ) \end{pmatrix}\!. \end{aligned} \end{aligned}$$

(2)

Lemma 1.6

$C_L^\mathbbm {1}\le 3$.

Proof

Note that the map $L^{-1}$ projects points from the sphere, parallel to the plane $\mathbb {R}^2\times \{0\}$, to the enveloping cylindrical surface, see Fig. 2. In order to bound the length of the curve $L^{-1}(\partial C\cap \mathbb {S}^2_p)$, it will be enough to work with the projection on the enveloping cylinder. We make the following claim, that we consider obviously true, see Fig. 2:

Given any spherical cap C(w, t), then there exists a cap $C(w',t')$ and $\varepsilon >0$, such that

$$\begin{aligned} 1-\varepsilon =z_M(w',t')>z_m(w',t')=\varepsilon -1, \end{aligned}$$

where $z_M(w',t')$ and $z_m(w',t')$ denote the maximal and minimal z-value of $C(w',t')$ in cylindrical coordinates, and

$$\begin{aligned} C(w',t')~\text {contains exactly one of the poles in its interior}, \end{aligned}$$

with the property that

$$\begin{aligned} {\text {length}}{(\partial C(w,t))}\le {\text {length}}{(\partial C(w',t'))}. \end{aligned}$$

This inequality then also holds for the length of the projections $L^{-1}(\partial C(w,t)\cap \mathbb {S}^2_p)$ and $L^{-1}(\partial C(w',t')\cap \mathbb {S}^2_p)$.

Thus in order to maximize the length we let $z_M,z_m$ approach $\pm 1$ and choose w so that exactly one of the poles is contained in the cap, i.e., consider C(w, 0) with

$$\begin{aligned} w=\biggl (\sin {\biggl (\frac{\pi }{2}-\epsilon \biggr )},0,\cos {\biggl (\frac{\pi }{2}-\epsilon \biggr )}\biggr )^{\!t} \end{aligned}$$

and $\epsilon >0$ small. A parametrization for $\partial C(w,0)$ is then given by

$$\begin{aligned} \varphi _{\pm }:[\epsilon ,\pi -\epsilon ]&\rightarrow [0,2\pi ],\\ \theta&\mapsto \pm \arccos {\biggl (-\cot \theta \cot {\biggl (\frac{\pi }{2}-\epsilon \biggr )}\biggr )}, \end{aligned}$$

such that

$$\begin{aligned} \gamma _+:[\epsilon ,\pi -\epsilon ]&\rightarrow \partial C(w,0),\\ \theta&\mapsto \begin{pmatrix}\cos \varphi _+(\theta )\sin \theta \\ \sin \varphi _+(\theta )\sin \theta \\ \cos \theta \end{pmatrix}\!, \end{aligned}$$

defines a curve that runs from $z_M$ to $z_m$ along $\partial C(w,0)$, and $\gamma _-$ defines the other half. Since $L^{-1}\circ \gamma _+$ and $L^{-1}\circ \gamma _-$ have the same length, it is enough to consider just one of these curves, bound its length and multiply by 2: thus we consider the curve

$$\begin{aligned} \theta \mapsto \frac{1}{\pi }\begin{pmatrix} \arccos {\biggl (-\cot \theta \cot {\biggl (\displaystyle \frac{\pi }{2}-\epsilon \biggr )}\biggr )}\\ \pi \hspace{0.33325pt}(1-\cos \theta )\end{pmatrix}\!, \end{aligned}$$

where we already multiplied by a factor of 2 in (2). Thus we have to bound

$$\begin{aligned} {\text {length}}=\int _\epsilon ^{\pi -\epsilon }\!\sqrt{\frac{1}{1-(\cot \theta )^2(\cot {(\pi /2-\epsilon )})^2}\cdot \frac{(\cot {(\pi /2-\epsilon )})^2}{\pi ^2(\sin \theta )^4}+(\sin \theta )^2}\,\ \textrm{d}\theta . \end{aligned}$$

We can simplify the expression in the square root, first with the angle sum formula for the cosine (with $\epsilon<\theta <\pi -\epsilon$) to obtain

$$\begin{aligned} \frac{-1}{\cos {({\pi /2}-\epsilon -\theta )}\cos {(\pi /2-\epsilon +\theta )}} \cdot \frac{(\cos {({\pi /2}-\epsilon )})^2}{\pi ^2(\sin \theta )^2}+(\sin \theta )^2, \end{aligned}$$

and then with $\cos {(\epsilon -\pi /2)}=\sin \epsilon$ and a symmetry argument to get

$$\begin{aligned} {\text {length}}\,=\,2\int _\epsilon ^{\pi /2}\!\sqrt{\frac{1}{\sin {(\epsilon +\theta )} \sin {(\theta -\epsilon )}}\cdot \frac{(\sin \epsilon )^2}{\pi ^2(\sin \theta )^2}+(\sin \theta )^2}\,\ \textrm{d}\theta . \end{aligned}$$

Let

$$\begin{aligned} {{\,\textrm{sinc}\,}}x=\frac{\sin x}{x}, \end{aligned}$$

then for any choice of $a\in (0,\pi /2]$ we have

$$\begin{aligned} x{{\,\textrm{sinc}\,}}a\le \sin x\le x \end{aligned}$$

for $x\in [0,a]$, which we use for small $\epsilon$ and $0<2\epsilon<a<\pi /2$ to obtain

$$\begin{aligned} {\text {length}}&\le \frac{2}{({{\,\textrm{sinc}\,}}a)^2\pi }\int _\epsilon ^{a-\epsilon }\!\sqrt{\frac{1}{\theta ^2-\epsilon ^2}\cdot \frac{\epsilon ^2}{\theta ^2}}\,\ \textrm{d}\theta +\frac{\epsilon \cdot \pi ^2}{4\sqrt{a\hspace{0.33325pt}(a-2\epsilon )^3}} +2\int _\epsilon ^{\pi /2}\!\sin \theta \ \textrm{d}\theta \\&=\frac{2}{\pi \hspace{0.33325pt}({{\,\textrm{sinc}\,}}a)^2}\int _1^{a/\epsilon -1}\sqrt{\frac{1}{x^2-1}}\cdot \frac{1}{x}\ \textrm{d}x+O(\epsilon )+2\, \overset{\lim \epsilon \rightarrow 0}{=}\,\frac{2}{\pi \hspace{0.33325pt}({{\,\textrm{sinc}\,}}a)^2}\cdot \frac{\pi }{2}+2, \end{aligned}$$

where we used that the length increases with decreasing $\epsilon$, and that

$$\begin{aligned} \frac{\textrm{d}}{\textrm{d}x}\arctan \sqrt{x^2-1}=\sqrt{\frac{1}{x^2-1}}\cdot \frac{1}{x}. \end{aligned}$$

The inequality above is thus true for any $0<a$, and hence also for ${{\,\textrm{sinc}\,}}0=1$, which proves the claim. $\square$

The next lemma relates $C^Q_L$ to $C^\mathbbm {1}_L$.

Lemma 1.7

Given a matrix $A\in \mathbb {R}^{2\times 2}$ and a finite length $\mathcal {C}^1$-curve $\beta$ in $\mathbb {R}^2$, then for $\ell _\beta ={\text {length}}\hspace{0.33325pt}(\beta )$, $\ell _{A\beta }={\text {length}}\hspace{0.44434pt}(A\beta )$, $m_A=\min {\{\Vert Ae_1\Vert ,\Vert Ae_2\Vert \}}$, and $M_A=\max {\{\Vert Ae_1\Vert ,\Vert Ae_2\Vert \}}$, we have

$$\begin{aligned} m_A\cdot \ell _\beta&\le \ell _{A\beta }\le M_A\cdot \ell _\beta&\quad&\text {if}\;A\; \text {has rank}\; 2\; \text {and}\; A\; \text {is orthogonal},\\ \ell _{A\beta }&\le \Vert A\Vert _F\cdot \ell _\beta&\quad&\hbox {if}\; A\; \hbox {has rank}\; 2. \end{aligned}$$

Proof

Let $\beta (t)=(x(t),y(t))$ be an injective $\mathcal {C}^1$-parametrization with $0<t<1$ (thus differing from the geometric curve at most by two endpoints). Let $s_M=\max _{\Vert x\Vert =1}\Vert Ax\Vert$ and $s_m=\min _{\Vert x\Vert =1}\Vert Ax\Vert$ denote the maximal and minimal singular values of A, then we have

$$\begin{aligned} s_m\ell _\beta =s_m\int _0^1\hspace{-0.83328pt}\Vert \beta '(t)\Vert \,\textrm{d}t\le \int _0^1\hspace{-0.83328pt}\Vert A\beta '(t)\Vert \,\textrm{d}t\le s_M\int _0^1\hspace{-0.83328pt}\Vert \beta '(t)\Vert \,\textrm{d}t=s_M\ell _\beta . \end{aligned}$$

For an orthogonal matrix we have $s_m=m_A$ and similarly for $M_A$; also it is clearly true that $s_M\le \Vert A\Vert _F$. $\square$

2.2 Intersection of Convex Curves with Fundamental Domains

In this section we will introduce the notion of an n-convex curve, for which we can prove sharp bounds on the number of fundamental domains it intersects. This will then give the boundary contribution in the proof of Theorem 1.3.

Definition 1.8

A continuous curve $\beta :[a,b]\rightarrow \mathbb {R}^2$ ($a,b\in \mathbb {R}$, $a<b$) is n-convex for $n\in \mathbb {N}$, if there are points $a=t_0<t_1<\ldots<t_{n-1}<t_{n}=b$ with the property that $\beta \hspace{0.33325pt}([t_j,t_{j+1}])$ is a convex curve for each $0\le j<n$, i.e., there exist convex sets $A_1,\dots ,A_n$ with $\beta \hspace{0.33325pt}([t_j,t_{j+1}])\subset \partial A_j$.

A circle is 1-convex, as is a straight line segment. Finite spirals (in length and winding number) are n-convex. It seems that every (finite) connected part of the boundary of a pseudo-convex set, as introduced in [1], is n-convex and vice versa. This characterization is not necessary for our purposes, so we do not try to prove it here.

Corollary 1.9

The images $L^{-1}(\partial C(w,t))$ for all $(w,t)\in \mathbb {S}^2\times (-1,1)$ are at most three distinct curves, each is at most 7-convex, and they are not self-intersecting.

Proof

This follows from the analysis of [1, Sect. 6], where the authors show that there is an admissible covering by pseudo-convex sets of at most seven parts (each part has some arc of the curve contained in its boundary). $\square$

Fig. 3

A 4-convex curve to illustrate the proof of Lemma 2.7

Definition 1.10

Given a lattice $\Lambda ^Q$, a continuous curve $\beta :[a,b]\rightarrow \mathbb {R}^2$ and $K\in \mathbb {N}$. Let $\Omega ^Q=Q[0,1)^2$, then the intersection number of $\beta$ with the tiling $(1/K)(\Lambda ^Q+ \Omega ^Q)$ is

$$\begin{aligned} I_\beta ^Q(K)=\#\,\biggl \{p\in \Lambda ^Q\;\Big |\;\biggl (\frac{1}{K}\hspace{0.55542pt}\Omega ^Q+\frac{1}{K}\hspace{0.3888pt}p\biggr )\cap \beta \hspace{0.33325pt}([a,b])\ne \emptyset \biggr \}. \end{aligned}$$

Lemma 1.11

Let $\beta$ be a piece-wise $\mathcal {C}^1$-curve in $\mathbb {R}^2$, n-convex with finitely many self-intersections. Let $\Lambda ^Q$ be a full rank lattice, then

$$\begin{aligned} I_\beta ^{Q}(K)\le \sqrt{2}\cdot K\cdot {\text {length}}\hspace{0.44434pt}(Q^{-1}\beta )+19\hspace{0.49988pt}n+1. \end{aligned}$$

Proof

Let $\beta :[0,1]\rightarrow \mathbb {R}^2$ be a parametrization as in the statement of the lemma, and denote the x, y-coordinates of $\beta$ by $x(t)=\langle \beta (t),e_1\rangle$ and $y(t)=\langle \beta (t),e_2\rangle$.

We will first show monotonicity of the coordinates for $\beta$ in certain intervals. Let $t_1,\dots ,t_{n-1}$ be as in Definition 2.4. If $\beta \hspace{0.33325pt}([0,t_1])$ is a line segment, then x(t), y(t) are monotonous, otherwise let $M_j,m_j\in \beta \hspace{0.33325pt}([0,t_1])$ for $1\le j\le 2$ satisfy

$$\begin{aligned} \langle M_j,e_j\rangle =\max _{t\in [0,t_1]}\langle \beta (t),e_j\rangle \quad \text { and }\quad \langle m_j,e_j\rangle =\min _{t\in [0,t_1]}\langle \beta (t),e_j\rangle . \end{aligned}$$

See Fig. 3. Choose $o_j^M\in \beta ^{-1}(M_j)\cap [0,t_1]$ and $o_j^m\in \beta ^{-1}(m_j)\cap [0,t_1]$ for $j\in \{1,2\}$. Let $o_1,o_2,o_3,o_4$ denote these $o_j^m,o_j^M$ in ascending order. In the calculations below the pair $(\tau _1,\tau _2)$ is $(o_k,o_{k+1})$ for some choice of $k\in \{0,1,2,3,4\}$ such that $\tau _2-\tau _1>0$, where $o_0=0$ and $o_5=t_1$.

It follows by the convexity assumption that the x, y-coordinates of $\beta (t)$ are monotone for $t\in [\tau _1,\tau _2]$ as we will show: first, for any $\kappa \in [0,t_1]$ and $\tau \in \{s\in [0,t_1]\mid \beta (s)\ne \beta (\kappa )\}$ we either have that the arc segment of $\beta$ with domain between $\tau$ and $\kappa$ is a straight line, or

$$\begin{aligned} \{(1-s)\hspace{0.49988pt}\beta (\kappa )+s\beta (\tau )\mid 0<s<1\}\cap \beta \hspace{0.33325pt}([0,t_1])=\emptyset . \end{aligned}$$

To prove monotonicity of x(t) and y(t), we work out the example $\beta (\tau _1)=m_2$. The existence of numbers $\tau _1<\epsilon _1<\epsilon _2<\tau _2$ such that $y(\epsilon _1)>y(\epsilon _2)$ will lead to a contradiction in this case (by the assumption on $\beta (\tau _1)$, y(t) is monotonously increasing). Either $x(\epsilon _1)\le x(\epsilon _2)$ or $x(\epsilon _2)<x(\epsilon _1)$, and in both cases, one of the polygons with vertices and edges of the form

$$\begin{aligned} \beta (o^M_2)&\longrightarrow \beta (\tau _1) \longrightarrow \beta (\epsilon _1)\longrightarrow \beta (\epsilon _2),\\ \beta (\tau _1)&\longrightarrow \beta (\epsilon _1) \longrightarrow \beta (\epsilon _2)\longrightarrow \beta (o^M_2), \end{aligned}$$

will contradict convexity, depending if either $o^M_2<\tau _1$ or $o^M_2\ge \tau _2$ (by definition $o^M_2\notin (\tau _1,\tau _2)$). For one of the polygons, we can find two points A, B on it, such that $\overrightarrow{AB}$ intersects the polygon in three points, and the same will hence also be true for the arc segments $\beta \hspace{0.33325pt}([o^M_2,\tau _2])$ or $\beta \hspace{0.33325pt}([\tau _1,o^M_2])$. Note that $y(o^M_2)\ge y(\epsilon _1)>y(\epsilon _2)\ge y(\tau _1)=y(o^m_2)$.

Thus y(t) is monotonously increasing, and we use this fact to show that x(t) is monotone. Assume there are numbers $\tau _1<\epsilon _1<\epsilon _2<\epsilon _3<\tau _2$ so that $x(\epsilon _2)< x(\epsilon _1)$ and $x(\epsilon _2)<x(\epsilon _3)$, and if either $o^*_1<\tau _1$ or $o^*_1\ge \tau _2$ (here $o^*_1$ is a place holder where $*\in \{m,M\}$ depending on the polygonal shape), one of the polygons with vertices and edges of the form

$$\begin{aligned} \beta (\tau _1)&\longrightarrow \beta (\epsilon _1)\longrightarrow \beta (\epsilon _2) \longrightarrow \beta (\epsilon _3)\longrightarrow \beta (o^*_1),\\ \beta (o^*_1)&\longrightarrow \beta (\tau _1)\longrightarrow \beta (\epsilon _1) \longrightarrow \beta (\epsilon _2)\longrightarrow \beta (\epsilon _3), \end{aligned}$$

contradicts convexity in a similar fashion as above. The case “$x(\epsilon _1)<x(\epsilon _2)$ and $x(\epsilon _3)<x(\epsilon _2)$” is similar. Thus x(t) is monotonous. The other possibilities for $\beta (\tau _1)$ reduce to the case above by applying rotations to $\beta \hspace{0.33325pt}([0,t_1])$.

We define two supporting axes for each non-trivial arc $\beta \hspace{0.33325pt}([\tau _1,\tau _2])$ as follows:

$$\begin{aligned} \{(1-t)\hspace{0.33325pt}\beta (\tau _j)+tZ\mid 0\le t\le 1\}\quad \ \ \text {where}\quad Z=\left( {\begin{array}{c}\langle \beta (\tau _1),e_1\rangle \\ \langle \beta (\tau _2),e_2\rangle \end{array}}\right) \in \mathbb {R}^2. \end{aligned}$$

These line segments above are parallel to the axes, and we denote them accordingly by $L_x$ and $L_y$. Let $\gamma =\beta \hspace{0.33325pt}([\tau _1,\tau _2])$ and Q be the identity matrix $\mathbbm {1}$, then

$$\begin{aligned} I_\gamma ^{\mathbbm {1}}(K)\le I_{L_x}^{\mathbbm {1}}\hspace{-0.55542pt}(K)+I_{L_y}^{\mathbbm {1}}\hspace{-0.55542pt}(K) \end{aligned}$$

by the following argument: since x(t), y(t) are monotonous for $t\in [\tau _1,\tau _2]$, say both are increasing, then $\beta$ can only exit a domain $(1/K)\hspace{0.49988pt}\Omega ^\mathbbm {1}+(1/K)\hspace{0.49988pt}p$, $p\in \Lambda ^\mathbbm {1}=\mathbb {Z}^2$, through the top or right side.

• If $\beta$ leaves through the right side, $I_\gamma ^{\mathbbm {1}}(K)$ and $I_{L_x}^{\mathbbm {1}}\hspace{-0.55542pt}(K)$ increase by one,

• or else $I_\gamma ^{\mathbbm {1}}(K)$ and $I_{L_y}^{\mathbbm {1}}\hspace{-0.55542pt}(K)$ increase by one.

Thus, with ${\text {length}}(L_x)=c$ and ${\text {length}}(L_y)=d$, we have

$$\begin{aligned} I_\gamma ^{\mathbbm {1}}(K)\le I_{L_x}^{\mathbbm {1}}\hspace{-0.55542pt}(K)+I_{L_y}^{\mathbbm {1}}\hspace{-0.55542pt}(K)\ \le (c+d)\hspace{0.49988pt}K+4. \end{aligned}$$

We further use the inequality $c+d\le \sqrt{2}\cdot \sqrt{c^2+d^2}$ valid for all $c,d\in \mathbb {R}$, to derive

$$\begin{aligned} I_\gamma ^{\mathbbm {1}}(K)\le \sqrt{2}\cdot \sqrt{c^2+d^2}\cdot K+4\le \sqrt{2}\cdot {\text {length}}(\gamma )\cdot K+4, \end{aligned}$$

where we used that the shortest path between $\beta (\tau _1)$ and $\beta (\tau _2)$ has length $\sqrt{c^2+d^2}$. The same reasoning applies to all sub-intervals (which are at most five), and after summing up we obtain

$$\begin{aligned} I_\beta ^{\mathbbm {1}}(K)\le \sqrt{2}\cdot {\text {length}}(\beta )\cdot K+19\hspace{0.49988pt}n+1. \end{aligned}$$

We will reduce the general case to the one above, by regarding the curve $\gamma =Q^{-1}\beta$. It is clear that $I_\gamma ^{\mathbbm {1}}(K)=I_\beta ^Q(K)$. Regularity of a curve is not affected by invertible matrices, neither is the notion of n-convexity nor the values $t_1,\ldots ,t_n$. $\square$

Note that the constant $\sqrt{2}$ in Lemma 2.7 cannot be improved, as the example of the translated diagonal of $I^2$ with $Q=\mathbbm {1}$ already shows.

2.3 Bound of $d^Q(K)$ and Proof of the Main Result

Before proving Theorem 1.3, we first bound the quantity $d^Q(K)$ and use this bound to express $N^Q(K)^{-1/2}$ in terms of K and Q in (3).

Lemma 1.12

Given a lattice $\Lambda ^Q$ and $K\in \mathbb {N}$, then

$$\begin{aligned} d^Q(K)\le \sqrt{2}\cdot 2\cdot (\Vert Q^{-1}e_1\Vert +\Vert Q^{-1}e_2\Vert ) +\frac{20}{K}\le \frac{4\cdot \Vert Q\Vert _F}{|{\det (Q)}|}+\frac{20}{K}. \end{aligned}$$

Proof

Using the notation as introduced in Definition 1.2, we see that $|{\det (Q)}|\cdot K^{-2}$ is the area of each $T_K(p)$, with $p\in \Lambda ^Q$. Now the number of points $\{z^p_K\}$ with $T_K(p)\subset I^2$ is at most $\lfloor K^2\cdot |{\det (Q)}|^{-1}\rfloor$, and this differs from $N^Q(K)$ at most by the number of points $\{z^q_K\}$ where $T_K(q)$ intersects $\partial I^2$. The number of these points is linear in K by Lemma 2.7, where the constant can be computed explicitly since ${\text {image}}(\beta )=\partial I^2$. The last part follows by applying the inequality $a+b\le \sqrt{2}\cdot \sqrt{a^2+b^2}$ and the well-known formula for $Q^{-1}$ in terms of elements of Q and a factor of $\det (Q)^{-1}$.

$\square$

Remark

The term $M^Q(K)$ can be bounded in a similar fashion by the same constant $+\,O(K^{-1})$: one just has to apply the triangle inequality in its definition, bound each term by $|{\det (Q)}|\cdot K^{-2}$, and bound the number of summands as above.

For later use, we note that there is some $s_K$ with $|s_K|\le d^Q(K)/N^Q(K)$, such that

$$\begin{aligned} \sqrt{\frac{1}{|{\det (Q)}|\cdot N^Q(K)}}=\frac{1}{K}\sqrt{1+\frac{K^2-|{\det (Q)}|\cdot N^Q(K)}{|{\det (Q)}|\cdot N^Q(K)}}=\frac{1}{K}+s_K. \end{aligned}$$

(3)

Proof of Theorem 1.3

Let $P^Q(K)=\{z_1,\dots ,z_N\}$ where $N=N^Q(K)$. Given a spherical cap $C(w,t)\subset \mathbb {S}^2$, we regard $A_{w,t}:=L^{-1}(C(w,t)\cap \mathbb {S}^2_p)\subset I^2$. Since L is area preserving, the proof will be complete once we can bound

$$\begin{aligned} (\star ):=\left| \frac{1}{N}\sum _{j=1}^N\chi _{A_{w,t}}(z_j)-\lambda (A_{w,t})\right| . \end{aligned}$$

An upper bound of $(\star )$ is established by a classical approach,² where $\Lambda ^Q$ is reduced to sets V, B of volume and boundary contributions in order to apply the triangle inequality: let $\{p_1,\dots ,p_N\}\subset \Lambda ^Q$ be such that $z_j\in T_K(p_j)$, then

$$\begin{aligned} (\star )\le \sum _{p\in V}\,\biggl |\frac{1}{N}-\lambda (T_K(p))\biggr |+\Biggl |\,\sum _{p_j\in B}\frac{1}{N}\chi _{A_{w,t}}(z_j)-\sum _{p_j\in B}\lambda \hspace{0.33325pt}(T_K(p_j)\cap A_{w,t})\Biggr |, \end{aligned}$$

(4)

where V and B are defined below, and where the notation is as in Definition 1.2. Set

$$\begin{aligned} V=V(w,t,K)=\{p\in \Lambda ^Q\mid T_K(p)\subset A_{w,t}\}, \end{aligned}$$

hence $z^p_K\in A_{w,t}$ for $p\in V$, and we define the boundary term $B=B_C\cup B_I$ by

$$\begin{aligned} B_C&=B_C(w,t,K)=\{q\in \Lambda ^Q\mid T_K(q)\cap (\partial A_{w,t}\setminus \partial I^2)\ne \emptyset \}\quad \text {and}\\ B_I&=B_I(w,t,K)=\{q\in \Lambda ^Q\mid T_K(q)\cap (\partial A_{w,t}\cap \partial I^2)\ne \emptyset \}. \end{aligned}$$

(Note that we potentially over-count in $B_C$ or $B_I$, since we do not remove points present in previously defined sets.) For each $p\in V$, the difference $\epsilon _K=N^{-1}-\lambda (T_K(p))$ is constant, thus the contribution to discrepancy coming from the area is given by ($\#V\le N$)

$$\begin{aligned} |\epsilon _K|\cdot \#V\le \biggl |\frac{1}{N}-\frac{|{\det (Q)}|}{K^2}\biggr |\cdot N=d^Q(K)\cdot \frac{|{\det (Q)}|}{KN}\cdot N. \end{aligned}$$

Next we bound the discrepancy coming from the boundary terms $B_C$ and $B_I$. If for $q\in B$ we have $z_K^q\notin A_{w,t}$, then the difference inside the absolute value of the second sum in (4) has a negative contribution of

$$\begin{aligned} \lambda \hspace{0.33325pt}(T_K(q)\cap A_{w,t}); \end{aligned}$$

otherwise the difference has a contribution of

$$\begin{aligned} \frac{1}{N}-\lambda \hspace{0.33325pt}(T_K(q)\cap A_{w,t})=\lambda \hspace{0.33325pt}(T_K(q)\setminus A_{w,t})+\epsilon _K. \end{aligned}$$

Both contributions are hence bounded by $\lambda (T_K(p))$ up to $\epsilon _K$, and we obtain

$$\begin{aligned} \sum _{p\in B_C}\,\biggl |\frac{\chi _{A_{w,t}}(z_K^p)}{N}-\lambda \hspace{0.33325pt}(T_K(p)\cap A_{w,t})\biggl |\le \frac{|{\det (Q)}|}{K}\cdot \sqrt{2}\cdot C^Q_L+O(K^{-2}), \end{aligned}$$

where we applied Lemma 2.7 (thanks to Corollary 2.5) and the definition of $C^Q_L$. Finally, the discrepancy coming from the contribution of points in $B_I$ is less than $|{\det (Q)}|\cdot K^{-1}M^Q(K)$ by definition, and (3) puts our bounds in terms of N. $\square$

3 Applications to Specific Cases

In this section we first focus on point sets with special choice $Q=\mathbbm {1}$, for which we obtain the lowest upper bound on the leading term of the spherical cap discrepancy up to date. This example also shows that in general the order of $O(N^{-1/2})$ cannot be improved. We further see that a separation distance of matching order cannot be derived in general. The second example serves as visual evidence that some point sets of the type regarded in this article should have a spherical cap discrepancy of much lower order.

Fig. 4

Image of the points $P^\mathbbm {1}(50)$ with $N=2500$

3.1 The Standard Lattice

Let

$$\begin{aligned} P^\mathbbm {1}(K)=\biggl (\frac{1}{K}\hspace{0.55542pt}\mathbb {Z}^2+\frac{1}{2K}\left( {\begin{array}{c}1\\ 1\end{array}}\right) \biggr )\cap I^2, \end{aligned}$$

see Fig. 4. Then $d^\mathbbm {1}(K)=0$ and $M^\mathbbm {1}(K)=O(K^{-1})$, and we obtain with Theorem 1.3 and Lemma 2.2 the constant mentioned in the introduction:

$$\begin{aligned} \frac{1}{2}\le \sqrt{N}\cdot \mathcal {D}(L(P^\mathbbm {1}(K)))\le \sqrt{18}\approx 4.242641. \end{aligned}$$

The lower bound comes from a special choice for a spherical cap: take as center the north pole and let the height $t\rightarrow ((2K-1)/(2K))^+$. The boundary of the aforementioned cap with height $t=(2K-1)/(2K)$ has length of order $K^{-1/2}$, while there are K points equi-distributed on it, thus the distance between consecutive points is of order $K^{-3/2}=N^{-3/4}$.

3.2 Orthonormal Lattices

Fig. 5

Image of points related to the lattice $\Lambda ^{Q(\varphi ,1)}$ with $K=50$ and $N^Q=2500$

We choose points $P^{Q(x,y)}(K)$, where Q is chosen orthonormal up to a factor, i.e.,

$$\begin{aligned} Q(x,y)=\frac{1}{y}\begin{pmatrix}x&{}-1\\ 1&{}x\end{pmatrix} \end{aligned}$$

and

$$\begin{aligned} Q^{-1}(x,y)=\frac{y}{x^2+1}\begin{pmatrix}x&{}1\\ -1&{}x\end{pmatrix}, \end{aligned}$$

for $x\in \mathbb {R}$, $y>0$. Then, by Lemma 2.3,

$$\begin{aligned} C^{Q(x,y)}_L\le 3\cdot \Vert Q^{-1}(x,y)\hspace{0.49988pt}e_1\Vert =3\frac{y}{\sqrt{x^2+1}} \end{aligned}$$

and also note that $y\cdot \sqrt{{\det (Q(x,y))}}=\sqrt{x^2+1}$. We can modify $P^{Q(x,y)}(K)$ such that $d^Q(K),M^Q(K)$ are of order $K^{-1}$, and hence by Theorem 1.3 we obtain many deterministic point sets with the bound

$$\begin{aligned} \mathcal {D}\bigl (L\bigl (P_mod ^{Q(x,y)}(K)\bigr )\bigr )\le \sqrt{\frac{18}{N^{Q(x,y)}_m}}+O\biggl (\frac{1}{N^{Q(x,y)}_m}\biggr ). \end{aligned}$$

For $\varphi =(1+\sqrt{5})/2$, the choice $Q(\varphi ,1)$ yields the image in Fig. 5, resembling spherical Fibonacci lattices and grids as in [1, 26]. Note that no modification was necessary for $P^{Q(\varphi ,1)}(K)$—this seems to be related to directional discrepancy as in [10], but we do not pursue this direction.

Remark

Definition 2.4 and Lemma 2.7 were first developed by this author to prove the result in a work with with Julian Hofstadler and Michelle Mastrianni, but the items were improved and streamlined in the current work.

Remark

Clearly the proof idea of Theorem 1.3 extends beyond the Lambert projection to any area preserving map $\Gamma$ between a surface and shape $R\subset \mathbb {R}^2$ with $\partial R$ being n-convex—as long as the boundary of the analog of spherical cap under $\Gamma$ is n-convex with universally bounded n and length.