Consider the cones and circles as vertices of a graph, where the edge between any 2 vertices has length equal to the distance between the corresponding elements of the obstacle course. Note that the longest edge in the graph is the one that connects the edges corresponding to the 2 circles. Our goal is to partition the vertices of the graph into 2 sets representing the “inside” and “outside” of the car’s path, so that the distance between any two vertices from different sets is at least the diameter of the car. We do this by constructing the minimum spanning tree (MST) of the graph, then removing the longest edge on the path from the outer edge of the track to the inner edge. Because the spanning tree is minimal, no two verticies from different sets can have an edge longer than the removed edge. Because there exists a path from the outer circle to the inner circle consisting only of edges not exceeding the length of the removed edge, there cannot be a partition which is separated by a longer distance. Therefore the length of the removed edge is the maximal diameter.
The MST can be easily computed in O(N2) time using Prim’s algorithm, though a O(N2log N) algorithm such as Kruskal’s will suffice. Both Prim’s and Kruskal’s can be modified to compute the length of the edge in question without actually computing the MST itself. Because the graph is mostly Euclidean, a more complicated O(N log N) solution also exists.
Layman explanation: create a MST considering all vertices on inner radius as one vertex, and all vertices on outer radius as one vertex. Remove the maximal length edge from the MST , this maximal length edge is the required diameter of the car.
The explanation before is almost clear, except when one has to considet the outer and inner circles.
Do I have to put additional vertices on the circles to “simulate” the presence of the circles ?
Do I have to replace the circles with one vertice so that that additional vertice is the closer to any of the vertices ?
There’s another point which is to discuss…
As the description above is provided by the admin, which I guess is fairly skilled in solving these problems, I think the solution above has been tested. But it’s not difficult to find an example which doesn’t work.
Let’s consider the picture I am posting. The MST here is drawn at random but look realistic. Imagine the red edge is the longest one.
When I erase the red edge, how is this going to create a path for the car to travel within, taking a car as big as the edge removed ?
Please look at the image as the rules prevents me to upload a file.
consider inner circle cr, outer circle cR, as additional nodes besides the N cones.
create MST
List path from cr to cR in the MST
output longest edge in that path, say of length l
proof-part1: since every edge in a path from cr to cR <= l, required path width <= l
proof-part2: remove this edge of len l. Nodes split into 2 sets of nodes, with cr & cR falling in different sets. Now for all xϵset(cr), yϵset(cR), dist(x,y)>=l, otherwise that x,y instead of this edge would have been part of our MST.
∴ l width path does exist
@quinzio, thanks for the graph. it helps understanding. In your graph, at-least one of branches should connect to cr. If both branches connect to cr, then they donot connect among themselves. In either case, the algorithm gives correct solution.
