Let's say you're given n points e.g. A(1,2) B(4,2) C(3,1)

How could you reach any of the points from the orign while minimising the longest jump from point to point

For example: A: OA, B: OACB, C: OAC

But this closest point approach won't always work as you risk getting further away from the target

Can anyone help me get started with writing an efficient algorithm for solving this please, I feel like some sort of dynamic approach may work

(This isn't homework or anything by the way, just a problem I came up with and can't find a solution anywhere)

New contributor
DanielKel is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

So input of your algorithm is "O" as starting point, "T" as the target point, and a set of intermediate points. I would try the following approach:

  1. Create the list of all segments (formed by all pairs of two points, including the intermediate points as well as O and T).

  2. Sort the list by segment length in increasing order.

  3. Now start with the empty graph containing all points as vertexes, and add segments from the list as edges one-by-one until there is a connected path in the graph from O to T.

Any of the paths found in step 3 is a valid solution. The latest added segment is obviously part of such a path, and it represents the "longest jump" necessary. Whatever path you choose, all other segments will be shorter than the last one.

The key here is to implement step 3 in an efficient manner, for not having to run a full path search after adding each segment. This can be accomplished as follows:

In the graph data structure of step 3, maintain the set of currently connected subgraphs (at the beginning, each point/vertex has its own subgraph). Whenever a segment is added, check if the endpoints of the segment belong to two different subgraphs, and if yes, merge those subgraphs. As soon as O and T belong to the same subgraph, the algorithm has found a solution.

Your Answer

DanielKel is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.