A Remark on Disk Packings and Numerical Integration of Harmonic Functions

Abstract

We are interested in the following problem: given an open, bounded domain $\Omega \subset {\mathbb{R}}^2$, what is the largest constant $\alpha =\alpha (\Omega )>0$ such that there exist an infinite sequence of disks $B_1,B_2,\dots ,B_N,\cdots \subset {\mathbb{R}}^2$ and a sequence $(n_i)$ with $n_i\in \left\{1,2\right\}$ such that $$\underset{N\in \mathbb{N}}{\sup }{N}^{\alpha }{\Vert {\chi }_{\Omega }-\sum _{i=1}^N(-1{)}^{n_i}{\chi }_{B_i}\Vert }_{L^1({\mathbb{R}}^2)}<\infty ,$$ where $\chi$ denotes the characteristic function? We prove that certain (somewhat peculiar) domains $\Omega \subset {\mathbb{R}}^2$ satisfy the property with $\alpha =0.53$. For these domains there exists a sequence of points $(x_i{)}_{i=1}^{\infty }$ in $\Omega$ with weights $(a_i{)}_{i=1}^{\infty }$ such that for all harmonic functions $u:{\mathbb{R}}^2\to \mathbb{R}$ $$\left|{\int }_{\Omega }u(x)dx-\sum _{i=1}^N{a}_{i}u(x_i)\right|\le C_{\Omega }\frac{\Vert u{\Vert }_{L^{\infty }(\Omega )}}{N^{0.53}},$$ where $C_{\Omega }$ depends only on $\Omega$. This gives a Quasi-Monte-Carlo method for harmonic functions which improves on the probabilistic Monte-Carlo bound $\Vert u{\Vert }_{L^2(\Omega )}/N^{0.5}$ \textit{without} introducing a dependence on the total variation. We do not know which decay rates are optimal.

to appear in Journal of Complexity