[math-fun] Number of points on convex hull, and number of undominated points
Let P(X,Y) be any fixed probability density in the plane that is unimodal on lines. For any such density I conjecture these upper bounds: (i) sampling N points from it independently will yield expected #vertices on convex hull growing like O(N^(1/3)) and (ii) expected #undominated points growing like O(N^(1/2)). A point (X,Y) is "undominated" if the infinite closed axis-parallel rectangle with lower left corner (X,Y) is empty of other points. These bounds (if valid) are tight since the uniform density within a circle (zero outside) achieves them. The variances might (more strongly) be conjectured also to be bounded by the same upper bounds. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
It turns out my conjecture about undominated points is false! Here is the counterexample: N*(logN)^2 points sampled independently from a uniformly bounded probability density in the XY plane that is unimodal on lines, such that the expected number of undominated points is of order>=N: Consider the infinite width=1 rectangle bounded by the 3 lines X+Y=0, X+Y=1, and X=Y and containing (9, -8.5). The probability density is 0 outside the rectangle, and inside it is given by C/(z*ln(z)^2) where z=X-Y+9 and C>0 is an appropriate normalization constant. I do not know whether my conjecture about convex hull vertices is true, but I have a proof sketch that it is true, which perhaps can be turned into a proof... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (1)
-
Warren D Smith