Random Euclidean coverage from within

Abstract

Abstract Let $$X_1,X_2, \ldots $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo></mml:mrow></mml:math> be independent random uniform points in a bounded domain $$A \subset \mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>A</mml:mi><mml:mo>⊂</mml:mo><mml:msup><mml:mrow><mml:mi>R</mml:mi></mml:mrow><mml:mi>d</mml:mi></mml:msup></mml:mrow></mml:math> with smooth boundary. Define the coverage threshold $$R_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>R</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:math> to be the smallest r such that A is covered by the balls of radius r centred on $$X_1,\ldots ,X_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>X</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>X</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math> . We obtain the limiting distribution of $$R_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>R</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:math> and also a strong law of large numbers for $$R_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>R</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:math> in the large- n limit. For example, if A has volume 1 and perimeter $$|\partial A|$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>|</mml:mo><mml:mi>∂</mml:mi><mml:mi>A</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:math> , if $$d=3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math> then $$\mathbb {P}[n\pi R_n^3 - \log n - 2 \log (\log n) \le x]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>P</mml:mi><mml:mo>[</mml:mo><mml:mi>n</mml:mi><mml:mi>π</mml:mi><mml:msubsup><mml:mi>R</mml:mi><mml:mi>n</mml:mi><mml:mn>3</mml:mn></mml:msubsup><mml:mo>-</mml:mo><mml:mo>log</mml:mo><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mn>2</mml:mn><mml:mo>log</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mo>log</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>≤</mml:mo><mml:mi>x</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:math> converges to $$\exp (-2^{-4}\pi ^{5/3} |\partial A| e^{-2 x/3})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>exp</mml:mo><mml:mo>(</mml:mo><mml:mo>-</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mo>-</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mi>π</mml:mi><mml:mrow><mml:mn>5</mml:mn><mml:mo>/</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:msup><mml:mo>|</mml:mo><mml:mi>∂</mml:mi><mml:mi>A</mml:mi><mml:mo>|</mml:mo><mml:msup><mml:mi>e</mml:mi><mml:mrow><mml:mo>-</mml:mo><mml:mn>2</mml:mn><mml:mi>x</mml:mi><mml:mo>/</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math> and $$(n \pi R_n^3)/(\log n) \rightarrow 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mi>π</mml:mi><mml:msubsup><mml:mi>R</mml:mi><mml:mi>n</mml:mi><mml:mn>3</mml:mn></mml:msubsup><mml:mo>)</mml:mo></mml:mrow><mml:mo>/</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mo>log</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>→</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math> almost surely, and if $$d=2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> then $$\mathbb {P}[n \pi R_n^2 - \log n - \log (\log n) \le x]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>P</mml:mi><mml:mo>[</mml:mo><mml:mi>n</mml:mi><mml:mi>π</mml:mi><mml:msubsup><mml:mi>R</mml:mi><mml:mi>n</mml:mi><mml:mn>2</mml:mn></mml:msubsup><mml:mo>-</mml:mo><mml:mo>log</mml:mo><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mo>log</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mo>log</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>≤</mml:mo><mml:mi>x</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:math> converges to $$\exp (- e^{-x}- |\partial A|\pi ^{-1/2} e^{-x/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>exp</mml:mo><mml:mo>(</mml:mo><mml:mo>-</mml:mo><mml:msup><mml:mi>e</mml:mi><mml:mrow><mml:mo>-</mml:mo><mml:mi>x</mml:mi></mml:mrow></mml:msup><mml:mo>-</mml:mo><mml:mo>|</mml:mo><mml:mi>∂</mml:mi><mml:mi>A</mml:mi><mml:mo>|</mml:mo><mml:msup><mml:mi>π</mml:mi><mml:mrow><mml:mo>-</mml:mo><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:msup><mml:mi>e</mml:mi><mml:mrow><mml:mo>-</mml:mo><mml:mi>x</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math> . We give similar results for general d , and also for the case where A is a polytope. We also generalize to allow for multiple coverage. The analysis relies on classical results by Hall and by Janson, along with a careful treatment of boundary effects. For the strong laws of large numbers, we can relax the requirement that the underlying density on A be uniform.

Topics & Concepts