Algorithm that finds the connectivity distance of a graph on uniform points on the unit square
algorithm, discrete-mathematics, graph-algorithm, math
Solution
Here is an algorithm which requires `O(n2)` time and `O(n)` space.
It's based on the observation that if you partition the points into two sets, then the connectivity distance cannot be less than the distance of the closest pair of points one from each set in the partition. In other words, if we build up the connected graph by always adding the closest point, then the largest distance we add will be the connectivity distance.
Create two sets, `A` and `B`. Put a random point into `A` and all the remaining points into `B`.
Initialize `r` (the connectivity distance) to 0.
Initialize a map `M` with the distance to every point in `B` of the point in `A`.
While there are still points in `B`:
Select the point `b` in `B` whose distance `M[b]` is the smallest.
If `M[b]` is greater than `r`, set `r` to `M[b]`
Remove `b` from `B` and add it to `A`.
For each point `p` in `M`:
If `p` is `b`, remove it from `M`.
Otherwise, if the distance from `b` to `p` is less than `M[p]`, set `M[p]` to that distance.
When all the points are in `A`, `r` will be the connectivity distance.
Each iteration of the `while` loop takes `O(|B|)` time, first to find the minimum value in `M` (whose size is equal to the size of `B`); second, to update the values in `M`. Since a point is moved from `B` to `A` in each iteration, there will be exactly `n` iterations, and thus the total execution time is `O(n2)`.
The algorithm presented above is an improvement to a previous algorithm, which used an (unspecified) solution to the bichromatic closest pair (BCP) problem to recompute the closest neighbour to `A` in every cycle. Since there is an `O(n log n)` solution to BCP, this implied a solution to the original problem in `O(n2 log n)`. However, maintaining and updating the list of closest points is actually much simpler, and only requires `O(n)`. Thanks to @LajosArpad for a question which triggered this line of thought.
Problem
Situation Suppose we are given n points on the unit square [0, 1]x[0, 1] and a positive real number r. We define the graph G(point 1, point 2, ..., point n, r) as the graph on vertices {1, 2, ..., n} such that there is an edge connecting two given vertices if and only if the distance between the corresponding points is less than or equal to r. (You can think of the points as transmitters, which can communicate with each other as long as they are within range r.) Given n points on the unit square [0, 1]x[0, 1], we define the connectivity distance as the smallest possible r for which G(point 1, point 2, ..., point n, r) is connected. Problem 1) find an algorithm that determines if G(point 1, point 2, ..., point n, r) is connected Problem 2) find an algorithm that finds the connectivity distance for any n given points My partial solution I have an algorithm (Algorithm 1) in mind for problem 1. I haven't implemented it yet, but I'm convinced it works. (Roughly, the idea is to start from vertex 1, and try to reach all other vertices through the edges. I think it would be somewhat similar to this.) All that remains is problem 2. I also have an algorithm in mind for this one. However, I think it is not efficient time wise. I'll try to explain how it works: You must first convince yourself that the connectivity distance rmin is necessarily the distance between two of the given points, say p and q. Hence, there are at most *n**(n-1)/2 possible values for rmin. So, first, my algorithm would measure all *n**(n-1)/2 distances and store them (in an array in C, for instance) in increasing order. Then it would use Algorithm 1 to test each stored value (in increasing order) to see if the graph is connected with such range. The first value that does the job is the answer, rmin. My question is: is there a better (time wise) algorithm for problem 2? Remarks: the points will be randomly generated (something like 10000 of them), so that's the type of thing the algorithm is supposed to solve "quickly". Furthermore, I'll implement this in C. (If that makes any difference.)