Fast algorithm for computing the union of "local convex hulls"

Question

I have a set of 2D points from which I want to create a polygon (or a set of polygons) that sets out the "shape" of these points using the following concept:

For each point of the set, we compute the convex hull of all points of radius R of this point. Having done this for each point, take the union of these convex hulls to get the final shape.

The brute force approach to actually constructing all these convex hulls is something like O (N ^ 2 + R ^ 2 log R). Is a more efficient algorithm known to get the same result? Or maybe another way to express the problem?

Note. I know alpha forms, they are different; I am looking for an algorithm to accomplish what is described above.

---

The following solution does not work - experimentally refuted in MATLAB.

Update: I have a suggested solution.

Suggestion: take the Delaunay triangulation from the set of points, remove all triangles having a circle greater than R. Then we take the union of the remaining triangles. Strike>

Answer 1

A line sweep algorithm can improve the search for R neighbors. As an alternative, you can only consider pairs of points located in adjacent squares of a square grid of width R. Both of these ideas can get rid of N ^ 2 - of course, only if the points are relatively rare.

, , , N ^ 2, ( ), .

Answer 2

, . , 19.

Answer 3

, , .

, N ^ 2 (1). , 2 , R - N ^ 2 * logN, , .

, R ^ 2 * logR ?

1 ( ) N - R/2 .