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$, $$\frac{|\partial_E(A, \Gamma)|}{|A|}\geq \frac{c}{n}$$ for any $A\subset DT(\mathcal{P})\cap Q$ with high probability?

Is there any reference for this problem? Thanks.

New contributor
Lucas is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Your Answer

Lucas is a new contributor. Be nice, and check out our Code of Conduct.

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.