I have been working on a particularly challenging problem and was hoping for some guidance. Here is my problem. I have a point cloud containing millions of points. For each point in the set, I need to determine whether there exists an enclosing circle of radius r that can be drawn around the point (the point can lie anywhere within the circle) but that does not also contain any neighbouring point. Here is a diagram to help illustrate my scenario.
The blue point in the diagram above is the point of interest. The red points all lie within a 2r radius of the point of interest (any neighbouring points beyond this distance couldn't affect the result). In this case it is possible to draw a r radius circle that contains the point of interest and no other points. In fact there are clearly many such candidate circles. I'm not interested in getting all of the candidates, but rather simply knowing whether this condition occurs at all.
Perhaps there is an obvious way of performing this analysis that I am overlooking. I have thought about using Delaunay triangulation (does the point of interest lie inside a triangular facet?) but I'm not convinced that approach will work because of the specified circle size. I know that if there are two or fewer neighbours, then it is always possible to fit a circle that meets the requirements. I also know that if the convex hull of the neighbours doesn't enclose the point of interest, my condition is met. But none of these things help me with the general solution. Does anyone know of an approach or algorithm that could be used to accomplish this task?