Sampling and Monte Carlo
Monte Carlo methods answer hard questions by random sampling. Throw random points into a room and count how many miss the furniture, and you have an estimate of the free floor area. Particle filters and sampling-based planners work on the same idea.
The estimate
Throw \(N\) points uniformly into a room of area \(A\). If \(k\) of them land on free floor, the estimated free area is
$$\hat{A}_{\text{free}} = A\,\frac{k}{N}, \qquad \text{error} \approx \frac{\sigma}{\sqrt{N}}$$
What to notice
The error shrinks like one over the square root of \(N\), shown by the dashed line on the log plot. To halve the error you need four times as many samples. That is slow, but it does not care how complicated the shape is, or how many dimensions the problem has. That is why sampling is the tool of choice when a robot's state has many dimensions, such as an arm with seven joints.