Skip to main content
8 of 11
using point process; added 3 characters in body

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 segment that connects two points on $H_n$'s edges.

###My question is:###

Assume that $L$ is a random line segment in $H_n$ (i.e. the end points of $L$ are uniformly distributed on $H_n$'s edges), what is the expected value of $|\mathcal{V}|$? i.e. what is the average number of Voronoi cell a random line intersects?


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.