Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects? - MathOverflow

Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects?

2011-08-23T17:17:45Z

Update: problem reformulation

Following the advice in comments, I now restate my problem using Voronoi tessellation.

Given a unit hypercube $H_n=\{(x_1,\ldots,x_n)\in \mathbb{R}^n: 0\leq x_i\leq 1\}$, generate $K$ random points in $H_n$ using uniform Poisson point process with intensity 1.

Let $V_k$ be the $k$-th Voronoi cell. Define

$\mathcal{V}=\{k\in\{1,\ldots,K\}|L\cap V_{k}\neq \emptyset\}$,

where $L$ is a line that intersects $H_n$

My question

Assume that $L$ is a random line (i.e. $L$ is uniformly distributed over all lines that intersect $[0,1]^n$), what is the expected value of $|\mathcal{V}|$? i.e. what is the average number of Voronoi cell that a random line intersects?

Clarification of edits

In the last formulation, $K$ points were uniformly distributed on $[0,1]^n$. Anthony Quas suggests that using a Poisson point process is preferable.
My original definition of a random $L$ is: the end points of $L$ are uniformly distributed on $H_n$'s edges. However, in Remark's comment:

I suggest that $L$ should be uniformly distributed over all lines that intersect $[0,1]^n$ . It is not equivalent to the current distribution because with uniform distribution if you know the first intersection point is close to a corner, then the second intersection point is also more likely to be close to that corner.

I guess this formulation is clearer than the old one. So if you can understand my question by reading above, please ignore everything I wrote below.

Old formulation: a messy one

I'll first describe how I divide $\mathbb{R}^{n}$ into $K$ convex sets, then describe my problem.

First of all, I define a function $\mathcal{C}(\mathbf{x}): \mathbb{R}^{n}\mapsto \{1,\ldots,K\}$ as follows:

$\mathcal{C}(\mathbf{x})=\underset{k=1,\ldots,K}{\mathrm{sargmax}} \mathbf{w}_{k}^{T}\mathbf{x}$,

where sargmax denotes the maximizer with the smallest $k$ value. Moreover, define

$S_{k}=\{\mathbf{x}\in \mathbb{R}^{n}|\mathcal{C}(\mathbf{x})=k\}$,

where $ k\in\{1,\ldots,K\}$.

The following statements can be easily proved.

-The collection $S_{1},S_{2},\ldots,S_{K}$ forms a partition of $\mathbb{R}^{n}$.

-$\forall k\in\{1,\ldots,K\}$, $S_{k}$ is a convex set.

For a line $L$ in $\mathbb{R}^{n}$, let

$V=\{k\in\{1,\ldots,K\}|L\cap S_{k}\neq \emptyset\}$.

A random line in $\mathbb{R}^n$ is a line connecting two points sampled from a $n$-dimensional normal distribution.

Here comes my question:

Assume that $\mathbf{w}_1,\ldots, \mathbf{w}_K$ are iid random variables in $\mathbb{R}^n$, each $\mathbf{w}_i \sim \mathcal{N}_n(\mu, \Sigma)$. For a random line $L$ in $\mathbb{R}^{n}$, what is the expected value of $|V|$?

It would be also nice if someone could re-formulate this problem into a less cumbersome one, or perhaps point me to some literature about this problem.

Answer by Raphael L for Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects?

2011-08-24T12:43:36Z

I'm not saying the distribution of $L$ is inappropriate, but I think it will be more easy to work with another one.

Let me give an answer that works with a general class of distributions. I also only assume that the tessellation is only made from convex polytopes.

First remark that if I denote by $T$ the union of all faces of cells of the tessellation (edges of $[0,1]^n$ included), you are interested in the variable $$F=card (T\cap L)-1$$ (because a.s. each time the line touches a cell, it only touches its border twice, and the exit point is actually the entrance point for a new cell, except at the end-points).

Let $\mathcal{L}$ be the class of all lines of $\mathbb{R}^n$, and $\mu$ some measure on $\mathcal{L}$ (endowed with a topology coming from a parametrization of $\mathcal{L}$), and for a set $C$ of $\mathbb{R}^n$, denote by $[C]$ the class of all lines intersecting $C$. Instead of working with a single line $L$, consider an independant Poisson point process of lines $\Pi$ on $\mathcal{L}$ with intensity measure $\mu$. I emphasize that a.s. only a finite number of lines of $\Pi$ will hit $[0,1]^n$, so I can label them independantly $N_1, N_2, ...$ so that the $L_i$ are iid. Call $N$ then number of lines touching $[0,1]^n$. Given any fixed tessellation $T$, we have $$\mathbb{E}\sum_i card(T\cap L_i)=\mathbb{E}\sum_n \mathbb{P}(N=n) \sum_{i=1}^n card(T\cap L_i)=\sum_n \mathbb{P}(N=n) n\mathbb{E} card(T\cap L_1)$$

$$=(\mathbb{E}(F)+1)\mathbb{E}(N).$$

So we will compute $\mathbb{E}(N)$ and $\mathbb{E}\sum_i card(T\cap L_i)$. We have $\mathbb{E}(N)=\mu([[0,1]^n])$ because $\Pi$ is a Poisson point process.

Let $T$ be a deterministic tessellation, written as $T=\cup f$, where the $f$ are the facets of the tessellations. Remarking that any given line can hit a facet no more than one time, we have $$\mathbb{E}\sum_i card(T\cap L_i)=\mathbb{E}\sum_i\sum_f card(f\cap L_i)=\sum_f \mathbb{E} card(i:f\cap L_i\neq \emptyset)=\sum_f \mu([f])$$ because $(L_1,L_2,...)$ is a Poisson point process with intensity $\mu$.

At this point you need to make assumptions on the distribution of the lines, so I make the assumption that $\mu$ is translation invariant. In this case it is a standard fact from integral geometry that $\mu([f])=c |f|$ where $c$ is a constant depending solely on $\mu$ and $|f|$ is the $(n-1)$-dimensional measure of $f$. Thus you have $$\mathbb{E}F=\mathbb{E}\frac{\sum_f c|f| }{\mu([[0,1]^n])}-1=c\frac{\mathbb{E}|T|}{\mu([[0,1]^n])}-1.$$

With normalisation conditions you can probably compute $c/\mu([[0,1]^n])$. Thus the above results holds for any random tessellation with facets as convex polytopes and a random line segment that is the restriction of a stationary measure $\mu$ on $\mathcal{L}$ to $[[0,1]^n$. For example the uniform distribution works, but you can also choose a different directional distribution, for instance "only horizontal lines and vertical lines", etc...I don't know if the iid intersection points enters this framework.

Answer by Raphael L for Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects?

2011-08-25T12:39:31Z

I was trying to write this as a comment, but the place is too small.

According to the intro of http://www.jstor.org/stable/1428226, the perimeter of the typical cell is in $\mathbb{R}^2$: $4/\sqrt{\lambda}$ ($\lambda$: intensity of the Poisson point process). It means that if you take a large ball, compute the sum of perimeters of all cells, and divide by the number of cells, you converge to this value. So using ergodicity the average perimeter should be the average number of cells (i.e. of points) multiplied by the perimeter of the typical cell, and divided by $2$ (because each cell is counted twice), which makes $2\sqrt{\lambda}$ (asymptotically). All this is quite vague but in the same intro there are vey good references, which also allow for arbitrary dimension.

Answer by mayak for Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects?

2011-08-27T10:19:33Z

Is there any monotonicity of E|T| and μ[[0,1]^n] with K and n?