Return to Question

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. $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 a random line intersects?

###Clarification of edits###

1. In the last formulation, $K$ points are uniformly distributed on $[0,1]^n$. Anthony Quas suggests that 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.

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.

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. $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 a random line intersects?

###Clarification of edits###

1. My original formulation describes $K$ points are uniformly distributed on $[0,1]^n$. Anthony Quas recommended using a Poisson point process of intensity 1.

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.

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. $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 a random line intersects?

###Clarification of edits###

1. In the last formulation, $K$ points are uniformly distributed on $[0,1]^n$. Anthony Quas suggests that 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.

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.

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. $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 a random line intersects?

###Clarification of edits###

1. My original formulation describes $K$ points are uniformly distributed on $[0,1]^n$. Anthony Quas recommended using a Poisson point process of intensity 1.

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.