2
$\begingroup$

Given a Poisson point process $\mathcal{P}$ in $\mathbb{R}^2$, the $\textbf{Voronoi cells}$ of a point $p\in \mathcal{P}$ is defined by $$V(x):=\{y\in \mathbb{R}^2: \|x-y\|=\min_{x'\in \mathcal{P}}\|x'-y\|\} $$ where $\|\cdot\|$ is the $\ell^2$ norm.

The Delaunay triangulation $DT(\mathcal{P})$ is the dual graph of the Voronoi diagram.(See figure as below) enter image description here

Given a square $Q$ with side length $s(Q)=n$ and $\hat{Q}$ with side length $s(\hat{Q})=n/25$ such that each cell of $Q$ that is divided into $25^2$ parts by cells of $\hat{Q}$. Assume that there exists at least one point in $\hat{Q}$ with high probability. If we define the $\Gamma:=DT(\mathcal{P})\cap Q-A$ where $A\subset DT(\mathcal{P})\cap Q$ and $\partial_E(A_1, A_2)=\{e=\{x,y\}: x\in A_1, y\in A_2\}$.

How to prove that isoperimetric inequality on Delaunay triangulation $DT(\mathcal{P})$ within a square $Q$, $$\mathbb{P}(\frac{|\partial_E(A, \Gamma)|}{|A|}\geq \frac{c}{n})\ge 1-e^{-cn}$$ for any $A\subset DT(\mathcal{P})\cap Q$ and $|A|\le 0.5| DT(\mathcal{P})\cap Q|$?

Is there any reference for this problem? Thanks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.