How to find the point most distant from a given set and its bounding box

Question

I have a bounding box, and a number of points inside of it. I'd like to add another point whose location is farthest away from any previously-added points, as well as far away from the edges of the box.

Is there a common solution for this sort of thing? Thanks!

Answer 1

Here is a little Mathematica program.

Although it is only two lines of code (!) you'll probably need more in a conventional language, as well as a math library able to find maximum of functions.

I assume you are not fluent in Mathematica, so I'll explain and comment line by line.

First we create a table with 10 random points in {0,1}x{0,1}, and name it p.

p = Table[{RandomReal[], RandomReal[]}, {10}];

Now we create a function to maximize:

f[x_, y_] = Min[ x^2, 
                 y^2, 
                 (1 - x)^2, 
                 (1 -  y)^2, 
                 ((x - #[[1]])^2 + (y - #[[2]])^2) & /@ p];  

Ha! Syntax got tricky! Let's explain:

The function gives you for any point in {0,1}x{0,1} the minimum distance from that point to our set p AND the edges. The first four terms are the distances to the edges and the last (difficult to read, I know) is a set containing the distance to all points.

What we will do next is maximizing this function, so we will get THE point where the minimum distance to our targets in maximal.

But first lets take a look at f[]. If you look at it critically, you'll see that it is not really the distance, but the distance squared. I defined it so, because that way the function is much easier to maximize and the results are the same.

Also note that f[] is not a "pretty" function. If we plot it in {0,1}, we get something like:

That's why you will need a nice math package to find the maximum.

Mathematica is such a nice package, that we can maximize the thing straightforward:

max = Maximize[{f[x, y], {0 <= x <= 1, 0 <= y <= 1}}, {x, y}];

And that is it. The Maximize function returns the point, and the squared distance to its nearest border/point.

HTH! If you need help translating to another language, leave a comment.

Edit

Although I'm not a C# person, after looking for references in SO and googling, came to this:

One candidate package is DotNumerics

You should follow the following example provided in the package:

 file: \DotNumerics Samples\Samples\Optimization.cs
 Example header:

  [Category("Constrained Minimization")]
  [Title("Simplex method")]
  [Description("The Nelder-Mead Simplex method. ")]
  public void OptimizationSimplexConstrained()

HTH!