Finding Remote Points in 2D

Answer 1

This is a naive algorithm:

1. Get the list of points within the convex shape.
2. Of those, find the minimum distance to any other point.
3. Rank all points by their respective R values
4. Select the top x points.

For (2), thinking of this as a radius search still means you end up calculating the distance from each point to each other point, because finding out whether a point lies within a given radius of another point is the same thing as finding the distance between the points.

To optimize the search, you can divide the space into a grid, and assign each point to a grid location. Then, your search for (2) above would first check within the same square and the surrounding 8 squares. If the minimum distance to another point is within the same square, return that value. If it is from one of the 8 and the distance is such that a point outside the 9 could be closer, you have to then check the next outline of grid locations outside those 9 for any closer than those found within the 9. Rinse/repeat.

Answer 2

This is a good example of a problem that may be solved using KD-Trees... there are some good notes in Numerical Recipes 3rd Addition.

If you are trying to find point locations that are relatively isolated... maybe the center of the largest quad elements would be a good candidate.

The complexity would be O(n log^2 n) for creating the KD-Tree... and creating a sorted list of quad sizes would be O(n Log n). Seems reasonable for even a large number of points (of course, depending on your requirements).