MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

share|cite|improve this question
What is the model for the distribution of points? – Boris Bukh Oct 26 '10 at 10:34
@Boris, anything you can analyze :) the q said "uniformly distributed", exponential would be nice – denis Oct 26 '10 at 11:57
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. – Dick Palais Oct 26 '10 at 12:27
What do you mean by "inside"? Convex hull? – Dylan Thurston Oct 26 '10 at 12:55
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. – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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