# How to generate nD point process?

Context:
Poisson point processes (PPP) are widely discussed in the literature. In the following figure a framework to generate two-dimensional PPP is demonstrated. First the area being studied (part of space which can be in 1D, 2D, 3D, ..., in our example is a 2D shape i.e., square) is divided into cells (gridding). Second, for each cell a random number n is drawn from a Poisson distribution with density of $\lambda$. Then within each cell n points are uniformly distributed. The resulting point pattern is a homogeneous point process.

Questions:

1. Is the described method correct?
2. If we shuffle the numbers within area, then is it still a valid PPP?
3. Is it valid for further dimensions?

Please check whether the following steps are the same as I illustrated.

note Please read the following invaluable answers and comments which are appreciable. I don't repeat them here. However I put a confusing point here hopefully to be solved by a gentle explanation.

The second point is if we do realization only once then why should we call it Poisson where it is simply a uniform-random-values?

• It's polite to check the "accept answer" check mark for one of the answers to your questions, if you feel that it has been reasonably well answered. (See the faq.) – Karl Sep 30 '11 at 13:11
• @Karl - Absolutely, you're right. The only reason that I'm still waiting is to have more satisfactory and developed answers to my questions. I believe they are many aspects to be discussed in my questions. Nevertheless I happily accept your polite suggestion. – Developer Sep 30 '11 at 15:48
• I can appreciate that. If the answers don't quite hit the mark, you might expand/refine the questions a bit so others can better understand your thinking. – Karl Sep 30 '11 at 16:33
• @Developer It is a realization of Poisson point process - generate a Poisson number and then do a binomial point process (uniform). See this if you want to understand Poisson point process more rigorously: www2.warwick.ac.uk/fac/sci/statistics/staff/academic-research/… – user66961 Jan 19 '15 at 21:44

You don't need to grid. You could just draw a Poisson count, $n$, for the total number of points and then simulate $n$ iid points uniform on the region. For a square, you can draw $x_i$ and $y_i$ as independent uniforms. (For a more complex region, the simplest thing would be to embed it in a square, simulate for the square, and then just keep the points in the target region.)

The same thing can be done in higher dimensions. You draw the count from a Poisson with mean $\lambda V$ where $\lambda$ is the rate for the Poisson process and $V$ is the volume of the region, and then simulate that number of iid uniform points from the region.

And so 1: yes, 2: yes (if the grid regions are the same area), and 3: yes.

• +1 I believe the point to gridding is to sample irregular regions with (slightly) higher computational efficiency, assuming an efficient data structure for locating grid cells within the region. (The alternative is to sample the region's bounding box and reject samples outside the box. That's usually ok in 2D but in higher dimensions tends to get bad. E.g., a spherical region occupies an exponentially vanishing portion of the hypervolume of its bounding box as the dimension grows.) – whuber Sep 30 '11 at 14:03
• @whuber, you wrote +1 but forgot to upvote :) – mpiktas Sep 30 '11 at 14:26
• @mp Thanks for the reminder. I frequently forget to vote for a few minutes--sometimes inadvertently for a long time--but I do get around to it! (I also make a point of upvoting good questions; with very rare exception, any question worth answering is a good one.) – whuber Sep 30 '11 at 14:28
• @ Whuber I grabbed the idea from somewhere (let me try to find the source). The figure is my implementation. I believe gridding stage was a necessity to the method. It was not to do optimization in computing due to the source (book) was a pure statistics (as I remember). – Developer Sep 30 '11 at 16:16
• Any comments on the steps that I added at the end of question. I grabbed it from an academic paper (ref. reserved). It is the source of my confusing, I think. Especially the step of sub-dividing region to sub-regions! – Developer Oct 2 '11 at 10:37

@Karl gave a good answer but it deserves an explanation.

A homogeneous Poisson point process (or "complete spatial randomness," CSR) is determined by two intuitive properties:

1. The probability that a point will be located within a small region $dA$ is directly proportional to $dA$ (up to second order in the hypervolume of $dA$). Note that this immediately implies the expected number of points in any finite region of hypervolume $A$ is proportional to $A$.

2. The points are located independently of each other.

Assuming the points introduced within each cell are done so independently, using a Poisson distribution of counts in each cell assures overall independence. To check (1), we lose no generality by assuming $dA$ is wholly located within a grid cell (because the probability that it straddles two cells is vanishingly small). That reduces the check to verifying that points are generated with the same intensity within the cells. Using a Poisson distribution of counts with expectation proportional to each cell's hypervolume assures this, as noted in (1).

This argument is independent of dimension. In fact, it would apply to any finite dimensional manifold with a volume form (such as the surface of a sphere in 3D) in which a region has been partitioned into measurable "cells" of arbitrary shape. The reason for using a grid, of course, is that grid cells can be addressed in $O(1)$ computational time and it's simple to generate random points within a rectangular region (merely by generating random coordinates within it). If, as a preliminary matter, an irregular region is preprocessed to identify the cells it contains, this leads to a computationally efficient way to simulate a CSR process. In higher dimensions the preprocessing for an arbitrary or complex region could be messy and time-consuming, but for simply defined manifolds and regions within them (such as spheres or their boundaries) there's no problem.

• I found this explanation useful. However as I commented above (@Karl) I am still in doubt that gridding is arbitrary to be done. – Developer Sep 30 '11 at 16:18
• @Developer The gridding is not statistically necessary. In fact, a standard way to generate realizations of a homogeneous Poisson process within a GIS is to generate them within the bounding box and eliminate all points falling outside the region; no gridding whatsoever is involved. We can only surmise that your stats text had an ulterior motive, either to clarify the exposition, to prepare for a later discussion of inhomogeneous processes, or because the author actually did have computational issues in mind. – whuber Sep 30 '11 at 16:22
• I added steps at the end of question. Are they same as I've illustrated? There is a step to divide region to sub-regions! It is source of my confusing. – Developer Oct 2 '11 at 10:34
• @Developer Those steps are exactly as you described. In particular, for generating homogeneous processes in low-dimensional spaces, subdivision is unnecessary. – whuber Oct 3 '11 at 14:31
• Well then why have they used sub-regions when they could just generate a number (random) n, then generate n uniform random coordinates (x,y)? According to your and Karl's comment generating regions is completely unnecessary. The second point is if we do realization only once then why should we call it Poisson where it is simply a uniform-random-values? – Developer Oct 3 '11 at 14:42