Your point selection rules can be satisfied by a Poisson-Disk sampling distribution & can be solved in O(n) with Bridson's algorithm. Basically, the algorithm divides the output region into a grid of cells sized relative to the minimum allowable distance, such that only one point can appear in each cell. Then, when you consider adding a new point, you only need to check a disk shaped collection of neighboring cells as opposed to the entire list of points. With respect to your problem, the cell & neighborhood size will account for your M parameter, the disk radii will account for your M parameter. Your N parameter is handled by terminating when enough points have been generated.

Mike Bostock has a nice animation showing the algorithm in progress.

The standard implementation is only concerned with a fixed minimal distance between points. amitp mentioned Herman Tulleken's Poisson Disk sampling article; it includes an adaptation to for varying the minimum distance across the resulting image/map which may make it better suited for your problem. It also includes source code.

Your point selection rules can be satisfied by a Poisson-Disk sampling distribution & can be solved in O(n) with Bridson's algorithm. Basically, the algorithm divides the output region into a grid of cells sized relative to the minimum allowable distance, such that only one point can appear in each cell. Then, when you consider adding a new point, you only need to check a disk shaped collection of neighboring cells as opposed to the entire list of points. With respect to your problem, the cell & neighborhood size will account for your M parameter, the disk radii will account for your M parameter. Your N parameter is handled by terminating when enough points have been generated.

Mike Bostock has a nice animation showing the algorithm in progress.

The standard implementation is only concerned with a fixed minimal distance between points. amitp mentioned Herman Tulleken's Poisson Disk sampling article; it includes an adaptation to for varying the minimum distance across the resulting image/map which may make it better suited for your problem. It also includes source code.

Your point selection rules can be satisfied by a Poisson-Disk sampling distribution & can be solved in O(n) with Bridson's algorithm. Mike Bostock has a nice animation showing the algorithm in progress.

The standard implementation is only concerned with a fixed minimal distance between points. Herman Tulleken's Poisson Disk sampling article includes an adaptation to for varying the minimum distance across the resulting image/map which may make it better suited for your problem. It also includes source code.

Your point selection rules can be satisfied by a Poisson-Disk sampling distribution & can be solved in O(n) with Bridson's algorithm. Basically, the algorithm divides the output region into a grid of cells sized relative to the minimum allowable distance, such that only one point can appear in each cell. Then, when you consider adding a new point, you only need to check a disk shaped collection of neighboring cells as opposed to the entire list of points. With respect to your problem, the cell & neighborhood size will account for your M parameter, the disk radii will account for your M parameter. Your N parameter is handled by terminating when enough points have been generated.

Mike Bostock has a nice animation showing the algorithm in progress.

The standard implementation is only concerned with a fixed minimal distance between points. amitp mentioned Herman Tulleken's Poisson Disk sampling article; it includes an adaptation to for varying the minimum distance across the resulting image/map which may make it better suited for your problem. It also includes source code.