Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am looking for an example of a stationary, infinite point process on $\mathbb R^n$ with a few simple properties. I would not be surprised to discover that there is a well-studied, canonical process with these features, but I don't know the field very well and have had no success in my search thus far.

The most important property I want is for the points to be repulsive and in the sense that there is a characteristic distance $r> 0$ between any two nearby points, and attractive in the sense that there is zero probability of finding a ball of radius say, $10r$, in which there are no points. Finally, the process should be stationary so that the distribution is unchanged by translation. Isotropy (invariance under rotations) would be nice, but I don't really care. It is crucial for my purposes that it be an infinite process, defined on all of $\mathbb R^n$, and in dimension $n\geq 2$. I believe that in one dimension it is easy enough to construct such an example.

The idea is to model, for example, the location of trees in a forest.

Is there some well-known point process I am informally describing (or is it easy enough to construct one?), or is there some good reason I am having trouble finding one?

share|improve this question
1  
What about taking a Poisson process (with intensity 1 say) and deleting any point whose nearest neighbour is at a distance less than 1/4 say. In this way you delete pi/16 proportion of points (in the plane - it gets better in higher dimensions). The minimum distance between points is 1/4. In any disc of size 10/4 the probability that the original Poisson process contains a point is very high. It must still be true for the thinned Process (but I haven't done the calculation). –  Anthony Quas Jan 6 '11 at 19:52
1  
It might help to look at the discussion of homogeneous Poisson point processes by Béla Bollobás and Oliver Riordan in their book Percolation (p.241), which you can access through Google books. Not certain if this will help meet your criteria... –  Joseph O'Rourke Jan 6 '11 at 19:57
    
By thinking through Anthony's example, I realized I need the probability of finding a large ball with no points to actually be zero. So I have edited the question according-- sorry for moving the goal posts on you. –  user5678 Jan 6 '11 at 20:29
add comment

1 Answer

up vote 3 down vote accepted

All your requirements are satisfied by the Poisson-Disk process. It's the limit of a uniform sampling process with a minimum-distance rejection criterion. The easiest way to describe it is as the limit of the following process: uniformly sample points in the area of interest, rejecting any points that are less than $r$ from an existing point. Keep sampling points until there is no area not within $r$ of a point, and you're done.

This process is popular in computer graphics and image processing because its Fourier Transform has some nice properties.

This process generates a distribution without any big holes, so it may not be the right thing for a forest where small clearings are allowed but big ones are not.

The process as described is very slow to converge. Some Googling for "Poisson Disk" suggests there are far more efficient modern algorithms than this for generating a Poisson-Disk distribution. But I can't guide you to that literature; I last generated a Poisson Disk distribution in 1982, and we did it the hard way.

share|improve this answer
add comment

Your Answer

 
discard

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.