In a random point cloud in Rn, say d1 <= d2 <= ... dk are the distances of the k points nearest the origin — I know only their distances, not their coordinates. What's a "good" estimate of the point density near 0 ?

In density estimation in statistics, it seems common to use volk = k / dkn for a fixed k, not using d1 d2 ... at all.
For example, one could take a weighted average of the naive vol1 vol2 ..., but with what weights ?

Added, re convex hull: can't say — 0 might not even be in the convex hull (cf. Wendel's formula). So there are two related but separate questions: estimating volume (answered by Joseph O'Rourke's reference), and estimating density.

(Experts, please add tags.)

  • $\begingroup$ What is the model for the distribution of points? $\endgroup$ – Boris Bukh Oct 26 '10 at 10:34
  • $\begingroup$ @Boris, anything you can analyze :) the q said "uniformly distributed", exponential would be nice $\endgroup$ – denis Oct 26 '10 at 11:57
  • $\begingroup$ It is a little difficult to give unambiguous mathematical meaning to this without saying something about the shape of the region whose volume you are trying to guesstimate. For example, if the shape is restricted to be the interior of a sphere the answer will be quite different than if you restrict it to a hypercube. And if you allow a union of balls as a possibility it can of course be arbitrarily small. $\endgroup$ – Dick Palais Oct 26 '10 at 12:27
  • $\begingroup$ What do you mean by "inside"? Convex hull? $\endgroup$ – Dylan Thurston Oct 26 '10 at 12:55
  • $\begingroup$ I think you should first think about a model or additionnal assumption for your density: is it only a function of distance to zero ? an increasing function of the distance to zero ? decreasing function ? smooth function ? may idea can be dealt with but I guess you have to introduce something more. $\endgroup$ – robin girard Dec 6 '10 at 15:14

Perhaps what would help is the expected volume of the convex hull of random points? For example, "Distribution-independent properties of the convex hull of random points" by Christian Buchta in the Journal of Theoretical Probability, 1990. He quotes a formula for this volume $V^{(d)}_n$ for $n$ points determined by Affentranger and Badertscher for $d=2$ and $d=3$,

$$ V^{(d)}_{d+2m} = \sum_{k=1}^m (2^{2k}-1) \frac{B_{2k}}{k} \binom{d+2m}{2k-1} V^{(d)}_{d+2m-2k+1} $$

where the $B_{2k}$ are the Bernoulli numbers. Buchta extends this (in some form) to arbitrary dimensions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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