Choose a point maximizing the distance to its nearest neighbor

Question

Consider a set of points in an n-dimensional space. Each dimension is bounded in the range [0, 1] inclusive. Add a new point to the space as far away as possible from its nearest neighbor. Where should that point go?

One-Dimensional Example: You are given the points 0, 1, 0.5, and 0.75. The solution is 0.25. Its nearest neighbors are 0 and 0.5 –– tied. The distance to its nearest neighbors is 0.25. No other point in the range [0, 1] inclusive is further from its nearest neighbor than 0.25.

Two-Dimensional Example: You are given the points (0, 0), (1, 0), and (0.75, 0). The solution is (0.375, 1). Its nearest neighbors are (0, 0), and (0.75, 0) –– tied. The distance to its nearest neighbors is 1.068. No other point with both dimensions on the range [0, 1] inclusive is further from its nearest neighbor than 1.068.

Multiple Solutions: You are given the points 0.4, 0.5, and 0.6. The solutions are 0 and 1. The nearest neighbor to 0 is 0.4, and the nearest neighbor to 1 is 0.6. For both solutions, the distance to the nearest neighbor is 0.4. No other point in the range [0, 1] inclusive is further from its nearest neighbor than 0.4.

Concrete Example: Consider an island containing cellular phone towers. Some areas of the island have service, and some areas do not have service. You are erecting a new tower. You could erect the new tower right next to an existing tower. This would provide coverage to the same area –– it would not improve the coverage area. Or you could erect the new tower as deep as possible in the largest uncovered area. This would yield the most improvement to the coverage area.

Context: I am doing research in graduate school about case-base maintenance (a sub-field of artificial intelligence). I am applying case-base maintenance to multiple domains. In the current domain, a case is a travel agency package. The package contains multiple features such as destination, number of travelers, and price. Given a query from a user, look up the most similar travel package. When adding a new travel package, try make it different from the existing packages.

Question: What algorithm can I use to solve this? Can you point me to search terms or an academic paper?

Answer 1

You could solve this problem using a Voronoi diagram.

_{(Image source: Wikipedia.)}

A Voronoi diagram colors each region of the image according to which point is closest. The key reasons why this is useful are the following:

1. A maximally far away point cannot occur in the middle of any of the regions. If you had a point there, you could move it further toward the edge of the region until you reached either a line separating two regions or a vertex.
2. By a similar argument, a maximally far away point cannot occur in the middle of a line separating two regions. If you had a point there, you could move it up or down the line and move it further away from both points, until you reached a vertex.

So, the only place where a maximally far away point can occur is at one of these Voronoi vertices, or the bounds. There is also a fast algorithm for computing a Voronoi diagram, taking only O(n ln(n)) time, where n is the number of points. Once you have your voronoi vertices, loop through and pick the one with the minimum distance.

What about when the maximally far away point is at the bounds? The standard Voronoi algorithm will not find this, unless you use a clever trick. Essentially, you reflect all of the points across each of your bounds, and each of the bounds will have voronoi vertices at the places where a line in the voronoi diagram intersects with the bounds. Here's a better, full length description.

Answer 2

1. Negate the point.
2. Multiply times infinity.