I think the problem here is they were trying to solve two different problems, but were trying solutions that solve only one or the other at a time, and then complaining it made the other worse:
1. It should not be possible to draw a rectangle wider than a certain diameter and length through the points (at any orientation).
2. The distance between any point and the nearest neighbouring point must not exceed a specified threshold.
An easy way to sample points from a random distribution but with additional constraints applied would be to do rejection sampling - if a point doesn't meet the constraints, reject it and start again. For this to work, you would need to formulate your constraints based on the number of points accepted so far so you don't reject all the points (for example, sample the first few points randomly, and then sample the next points using rejection criteria based on a multiple of the theoretical minimum values of the distance between points / size of the rectangles for the number of points sampled so far).
This requires being able to efficiently work out the greatest distance between points and finding the largest rectangle of a given width. You could do the former with a quad-tree; if the new candidate point is too close to the nearest neighbour, reject it; if it is accepted, add it to the quad-tree. For the rectangles, you could optimise by creating a Fibonacci heap with the largest rectangle so far for each point - the largest rectangle will never get bigger as you add more points, so you should be able to do much better than O(n^2) time in the number of points (I haven't verified this, however) because you can skip checking most points most times.
If you read the series, you'll see that what you call "rejection sampling" is in fact the first thing that was tried, and it was set aside for performance reasons. Yes you can try to improve the perf of this kind of system, but the goal was to build something that would run with much less overhead than that. And this was accomplished, and it seems to me that the end result runs faster than any optimized version of the system you are proposing. So I'd be careful with dishing out what reads to me here like middlebrow dismissal.
This requires being able to efficiently work out the greatest distance between points and finding the largest rectangle of a given width. You could do the former with a quad-tree; if the new candidate point is too close to the nearest neighbour, reject it; if it is accepted, add it to the quad-tree. For the rectangles, you could optimise by creating a Fibonacci heap with the largest rectangle so far for each point - the largest rectangle will never get bigger as you add more points, so you should be able to do much better than O(n^2) time in the number of points (I haven't verified this, however) because you can skip checking most points most times.