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



Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects?
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.


