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

## 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

1. In the last formulation, $K$ points were uniformly distributed on $[0,1]^n$. Anthony Quas suggests that using a Poisson point process is preferable.

2. 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.

• I think $D$ is supposed to be $n$ in your question. "Uniformly distributed" doesn't make sense since $\mathbb R^n$ has infinite volume; perhaps you mean "normally distributed"? For what it's worth, the decomposition of $\mathbb R^n$ is called the Vornoi decomposition determined by the $\mathbf w_i$. See en.wikipedia.org/wiki/Voronoi_diagram. Aug 23 '11 at 17:32
• Once the distributions of the w's and L are clarified, this is likely to reduce to a one-dimensional problem: Given $k$ random affine functions $f_i$ on $\mathbb R$, how many of them are "somewhere maximal" in the sense that, for some $x$, $f_i(x)$ exceeds all $k-1$ of the other $f_j(x)$'s? Aug 23 '11 at 17:55
• Thanks Joseph O'Rourke for the reference. I also found my problem formulation cumbersome. I will try to restate my problem in a clearer way in the next few minutes. Aug 24 '11 at 0:42
• I'd suggest a further reformulation: Look at the Voronoi tiling induced by a Poisson process of intensity 1. Given a line segment of length 1, what is the expected number of cells that it meets? Call this quantity a. The relationship is that as $K$ becomes large, the process becomes similar to a Poisson process. The other variable is the length of the line. This has some expectation $L$. The expected number of points should be very close to $L$ times $a$. Aug 24 '11 at 3:36
• If I may, I think your problem should have a nice answer if you also allow for another distribution of $L$. 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. Aug 24 '11 at 9:52

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.

• I forgot to mention it, but $\mathbb{E}|T|$ is the total $(n-1)$-dimensional measure of the facets of the tessellation. For Voronoi, it should be somewhere in the literature, at least asymptotically. While searching the literature, I noticed that in books.google.com/… there is a chapter called "typical k-face of a section of a Poisson-Voronoi tessellation". It probably helps if you assume that the underlying points are Poisson. Aug 24 '11 at 13:41
• Thanks for a very detailed answer. As the problem now becomes finding $E|T|$, I'm searching some literatures about the general result on a convex polytopes tessellation. Thanks for your help again. Furthermore, as you mentioned it in the end, I'd like to know more about restricting $L$ to axis-aligned lines. Aug 25 '11 at 7:15
• The above result is true for any "stationary" random line (meaning the law of the random line does not change if you shift it by a constant vector); it is in particularly true if you take a uniformly distributed horizontal line. Aug 25 '11 at 12:30
• It takes me some time to understand the result. While searching related literatures, I found this "Integral geometry and geometric probability By Luis Antonio Santaló, pp71" books.google.com/… From my point of view, 'Remark''s answer looks like a generalised version of eq(5.10) in $\mathbb{R}^{n}$ when the breadth $a=0$. Sep 14 '11 at 13:01

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.

• Thanks for your information. I also found [this document] (algo.inria.fr/csolve/vi.pdf) which summaries useful statistics for Poisson-Voronoi Tessellations on $R^1$, $R^2$ and $R^3$. I haven't found any result about $(n-1)$-dimensional measure of the facets of the tessellation. Nevertheless, there are bunch of software can give asymptotic statistics by simulation, e.g. Qhull Aug 26 '11 at 4:48
• I just realised that most published results give $\mathbb{E}|T|$ when K is infinity, whereas I'm mostly interested in a convex ploytope tessellation with small number of cells. So maybe this changes everything, what if I want to find $\mathbb{E}F$ when the number of cells $K$ is small, e.g. $K<50$. In particular, is there a way to write $\mathbb{E}F$ as a function (or approximated function) of $n$, dimension of space and $K$, the number of cells? Aug 26 '11 at 15:51
• For approximated function I think you already have an answer. For exact result, for Voronoi tessellations, I don't know (and I doubt it). But if you would accept another random tessellation which cells are convex polytopes, you have the STIT tessellation, and Poisson hyperplane tessellation, for which $E F$ and $E |T|$ are very easy to compute. Aug 27 '11 at 11:15

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