Consider an empty room with $5$ people standing inside it. These people will be randomly placed throughout the room. Each person has their own $(x,y)$ position based on where they are in the room (imagine looking overhead). My goal is to have the people form a straight line somewhere in the room. This line can start at any point in the room, and have any heading. Let's say each person in the line has a $1$ unit gap in between one another.
Let's ignore any possible collisions in formation, and assume every person is identical. All the people will walk at the same time.
Here is my analysis:
A Trivial Solution: Have the people line up vertically at the center of the room. The person whose position is closest to the center will be the "leader" of the line, and will move to the center of the room $(0,0)$ and face vertically. The second closest person will move to the point $(0,-1)$, and so forth for each person.
Here is my goal: I want to find the coordinates of the line that minimizes the amount of time it takes for the people to organize. The person that is furthest from where they need to travel to will be the one who takes the longest.
In other terms, given a set of $5$ people's $(x,y)$ coordinates, I want to create a line with $5$ points, each of them separated by $1$ unit, that is the line that minimizes the furthest distance that any person needs to travel.
I have read the https://en.wikipedia.org/wiki/Smallest-circle_problem which describes a similar scenario, but in their scenario, each person would meet at a common center point. In my problem, the people need to be separated and thus we need to find some line.
Consider the example: $(-5,7)$, $(1,5)$, $(1,3)$, $(2,-1)$, $(5,0)$ as your five people positions. I need to find where to send each person to minimize the time.