2
$\begingroup$

We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \in\mathbb{R}^d$ selected uniformly at random from the unit origin-centered ball $\mathcal{B}^{d}$.

Consider the random process that keep generating random hyperplanes $H=\{\mathbf{z}\in\mathbb{R}^d: z_1=b\}$ where $b$ is drawn uniformly at random from $[-1,1]$, until the intersection of $H$ with the convex hull $C(X)$ of $X$ is not empty. That is, $H$ is rejected (and thereafter regenerated) until we have $H\cap C(X)\neq\emptyset$.


Question: In expectation over the generation of $X\subset \mathcal{B}^d$, what is an asymptotic lower bound (for $d\to\infty$ and $n:=n(d)\to\infty$) for the number $n$ of points that we need to have in $X$, such that the rejection probability in the above process is at most a given expression $p(n)$ (e.g., $p(n)=\frac{1}{n}$) — where $n$ is therefore expressed in terms of $d$ and $p(n)$?



Note: I think we can fix $b\in[-1,1]$ and calculate the minimum number of points $n$ drawn uniformly at random from $\mathcal{B}^d$, such that with probability at least $1-p(n)$, there is at least one point $\mathbf{x}'$ and one point $\mathbf{x}''$ with $x'_1\ge b$ and $x''_1\le b$. Then we can get the final result integrating over $b$. Am I wrong?

$\endgroup$
6
  • 1
    $\begingroup$ unit ball $\mathcal{B}^d$: I assume unit origin-centered ball? $\endgroup$ Feb 6, 2021 at 16:05
  • $\begingroup$ Yes @JosephO'Rourke, added. Thanks. $\endgroup$ Feb 6, 2021 at 16:25
  • 3
    $\begingroup$ If I'm reading this correctly, it seems this all reduces to the $x_1$-axis. The $z_1=b$ hyperplane will intersect the hull only if there is a hull vertex $v$ whose $x_1$-coordinate is $\ge b$. If I'm right, then you can reduce $d$ to $1$, and $\mathcal{B}^d$ to the interval $[-1,1]$. $\endgroup$ Feb 6, 2021 at 21:10
  • 1
    $\begingroup$ (1) Your note is correct; (2) $d$ only determines the distribution of the first coordinates of points $x_i$; (3) it's not necessarily the case that the property holds for all $n$ starting with some $n_0$, since both the rejection probability and $p(n)$ depend on $n$ $\endgroup$
    – Yury
    Feb 6, 2021 at 21:20
  • $\begingroup$ Thank you @Yury $\endgroup$ Feb 6, 2021 at 22:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.