Finding unusually large empty regions in a field of coordinate points

algorithmsgeometry

I have a list of coordinates representing arbitrary points in space.

[0.2, 0.55],
[1.23, 4.56],
[7, 8],
...

I want to find two things: regions with no points that are especially large, and collated separately, large regions with especially few points.

For example: In this image, Fig 1 shows a sample field of points. Fig 2 shows the same field of points, but denoted with red circles indicating large regions that have no points.

Field of points (left), and field of points with empty regions highlighted (right)

I am looking for a function which, given the coordinates for Fig 1, returns coordinates one could use to produce Fig 2. (Not illustrated here: the large regions with few points result.)

Here are a few constraints to work with.

  • We can assume the space is flat. (It's not curved or circular.)
  • But the space may have any number of dimensions >= 2
  • The space should be bounded by the outermost points.
  • We should not highlight regions that clip outside that boundary.
  • The preferred geometry for the highlighted regions is spherical, but that's not a hard requirement.

I initially sought to solve this problem in the following two ways:

By subdivision: Subdivide the space into equal regions (n-orthotopes). Then count the number of points in the subdivision volume. Take the average number of points-per-subdivision at this scale, then look for subdivisions that have lower than a standard devision of points, and add it to my list of candidates. The subdivide the subdivisions, and repeat down to a minimum scale. Sort the list of candidates to find the volumes that best meet my criteria.

By random sampling: Choose a point at random within the space. Choose a random radius value so that we describe an n-sphere at that point. Count the number of points within the n-sphere volume. Keep doing this up to some maximum defined number of iterations, then sort the list to find the volumes that best meet my criteria. (I like this idea better than the subdivision one, for its relative simplicity.)

But I thought I would ask Mathematics SE in case there is a known solution to this kind of problem. Is there an established/solved/common/conventional way to do this?

Best Answer

Construct the Voronoi partition of your space. If your circle is centered in the region around point $p$, as you grow its radius, it will meet point $p$ first. Therefore, maximal circles are where three or more regions meet (i.e. are vertices in the partition). There are finitely many such vertices, so you can find the distance from each to the equidistant points giving any of the regions meeting at that vertex and sort these from largest to smallest.

A Voronoi partition of 20 points.

Note that higher order Voronoi diagrams can meet your requirement for large regions containing a few points.

Lloyd's algorithm can be used to compute Voronoi diagrams in arbitrary dimensions. In the plane, Fortune's algorithm is (asymptotically and practically) faster.

Software for computing (higher order) Voronoi diagrams exists. I make no representation of fitness for the following Google search results.

Related Question