<p>Computing the probability that a point is inside a random convex-hull is quite interesting, and got some attention recently (under a slightly different sampling model). The exact probability can be computed (but not too quickly). Good estimates follow by looking on the Tukey depth of the points of interest. See the following recent paper, and references therein.</p>

<p><a href="http://sarielhp.org/p/14/prob_ch/" rel="nofollow">http://sarielhp.org/p/14/prob_ch/</a></p>

CC BY-SA 3.0
2014-07-16T09:42:50.570Z
2014-07-16T09:42:50.570Z
Sariel Har-Peled
<p>This question is in regards to the following problem:</p>

<blockquote>
  <p>Suppose you are given a set $S$ of $n$ points in the plane. Let $R$ be a random subset of $S$ of size $r$ with all subsets of size $r$ equally likely. What is the expected number of points of $S$ that lie on the interior of the convex hull or $R$? I.e. What is $E[|S\cap \operatorname{int}(\mathcal{CH}(R))|]$?</p>
</blockquote>

<p>I have been looking in Clarkson and Shor's <em>Applications of Random Sampling in Computational Geometry, II</em>, Mulmuley's chapter in the handbook of computational geometry, and related papers. As far as I understand it, these methods all apply to bounding the number of points of $S$ outside the convex hull, but do so by finding the expected sums of the sizes of conflict lists. For instance, the conflict list of an edge in the problem above is the number of points in $S$ that are beyond it, and the sum of the sizes of all conflict lists is $O(n)$. But because the same point may appear in $O(n)$ conflict lists itself, this doesn't seem to say anything about the number of points on the interior. </p>

<p>Any help in understanding the problem, or useful references is appreciated. Unfortunately, I have a sneaking suspicion that the answer is obvious, but find myself a bit stuck. Thanks.</p>

CC BY-SA 3.0
2014-07-10T17:57:12.870Z
Doesn't it depend on the shape of $S$? Can't it range from anywhere from $0$ to $c_r|S|$ for some constant $c_r$ that approaches $1$ as $r$ gets large? Are you looking for an algorithm to compute this expected value that's better than the obvious Monte Carlo method?
Peter Shor 
CC BY-SA 3.0
2014-07-10T18:04:41.263Z
(I should say I'm assuming general position.) I would have thought the same for the sum of the conflict lists, but your result applies regardless of the shape of S, so I thought something similar might apply here. If S is in convex position, obviously the value is zero, so that is a sort of best case. Worst case seems to be something like a set S such that it's onion peel convex hulls are all triangles (Repeatedly taking he convex hull and removing the points only removes three at a time.) I guess it doesn't seem obvious to me that it is definitely the case that the expected size is |S|-o(S)
John
CC BY-SA 3.0
2014-07-10T18:08:30.117Z
If *r* is fixed (I was assuming that $r$ grew with $|S|$ when I said $|S| - o(|S|)$),  I think the worst-case is something like $(1-\frac{3}{r})|S|$ for the worst-case set you describe.
Peter Shor 
CC BY-SA 3.0
2014-07-10T18:09:24.513Z
I'm somewhat interested in the expected running time of the algorithm mentioned in the introduction to your applications of... paper: randomly select a subset of size R, recursively compute convex hull and then fix the remaining O(n) conflicts
John
CC BY-SA 3.0
2014-07-10T18:10:27.147Z
I.e. How many recursive calls are made for a fixed r. Or maybe for something like r=n/2
John
CC BY-SA 3.0
2014-07-10T18:38:02.387Z
I should mention: the algorithm above is for computing the convex hull recursively.
John
<cg.comp-geom><randomness>
Number of points on the interior of the convex hull of a random subset
John
# Number of points on the interior of the convex hull of a random subset

(Asked by: username_0 on 2014-07-10)

This question is in regards to the following problem:

> Suppose you are given a set $S$ of $n$ points in the plane. Let $R$ be a random subset of $S$ of size $r$ with all subsets of size $r$ equally likely. What is the expected number of points of $S$ that lie on the interior of the convex hull or $R$? I.e. What is $E[|S\cap \operatorname{int}(\mathcal{CH}(R))|]$?

I have been looking in Clarkson and Shor's *Applications of Random Sampling in Computational Geometry, II*, Mulmuley's chapter in the handbook of computational geometry, and related papers. As far as I understand it, these methods all apply to bounding the number of points of $S$ outside the convex hull, but do so by finding the expected sums of the sizes of conflict lists. For instance, the conflict list of an edge in the problem above is the number of points in $S$ that are beyond it, and the sum of the sizes of all conflict lists is $O(n)$. But because the same point may appear in $O(n)$ conflict lists itself, this doesn't seem to say anything about the number of points on the interior.

Any help in understanding the problem, or useful references is appreciated. Unfortunately, I have a sneaking suspicion that the answer is obvious, but find myself a bit stuck. Thanks.

**Tags:** cg.comp-geom, randomness

> **Comments:**
> **username_1**: Doesn't it depend on the shape of $S$? Can't it range from anywhere from $0$ to $c_r|S|$ for some constant $c_r$ that approaches $1$ as $r$ gets large? Are you looking for an algorithm to compute this expected value that's better than the obvious Monte Carlo method?  
> **username_0**: (I should say I'm assuming general position.) I would have thought the same for the sum of the conflict lists, but your result applies regardless of the shape of S, so I thought something similar might apply here. If S is in convex position, obviously the value is zero, so that is a sort of best case. Worst case seems to be something like a set S such that it's onion peel convex hulls are all triangles (Repeatedly taking he convex hull and removing the points only removes three at a time.) I guess it doesn't seem obvious to me that it is definitely the case that the expected size is |S|-o(S)  
> **username_1**: If *r* is fixed (I was assuming that $r$ grew with $|S|$ when I said $|S| - o(|S|)$),  I think the worst-case is something like $(1-\frac{3}{r})|S|$ for the worst-case set you describe.  
> **username_0**: I'm somewhat interested in the expected running time of the algorithm mentioned in the introduction to your applications of... paper: randomly select a subset of size R, recursively compute convex hull and then fix the remaining O(n) conflicts  
> **username_0**: I.e. How many recursive calls are made for a fixed r. Or maybe for something like r=n/2  
> **username_0**: I should mention: the algorithm above is for computing the convex hull recursively.  

---

## 1 answers

### Answer by username_2 on 2014-07-16. Score: 3

Computing the probability that a point is inside a random convex-hull is quite interesting, and got some attention recently (under a slightly different sampling model). The exact probability can be computed (but not too quickly). Good estimates follow by looking on the Tukey depth of the points of interest. See the following recent paper, and references therein.

<http://sarielhp.org/p/14/prob_ch/>


---

