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.


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.