5
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Peter Shor
    Jul 10, 2014 at 17:57
  • $\begingroup$ (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) $\endgroup$
    – John
    Jul 10, 2014 at 18:04
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Jul 10, 2014 at 18:08
  • $\begingroup$ 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 $\endgroup$
    – John
    Jul 10, 2014 at 18:09
  • $\begingroup$ I.e. How many recursive calls are made for a fixed r. Or maybe for something like r=n/2 $\endgroup$
    – John
    Jul 10, 2014 at 18:10

1 Answer 1

Reset to default
3
$\begingroup$

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/

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.