Where should you place a business if one of your customers keeps moving?

Imagine you are the owner of a hot dog stand and, after many stressful years in the streets of New York City, you are moving the business to the countryside.

Of course, you want all the potential users to have your stand as close as possible. After thinking on it for a while, you take the bizarre decision of hiring a mathematician. He immediately detects that you are facing a facility location problem, where you want to minimize the maximum distance between your stand and the users.

You are lucky, my friend! He says. It turns out that this is a well-known problem, first posed by Sylvester ¹ in 1857. The solution is not difficult: Your stand should be placed at the center of the smallest circle enclosing the users, known as the smallest enclosing circle.

You are still a bit concerned about the difficulty of finding that place, but the mathematician calms you down. Megiddo found an optimal algorithm ² in 1983, which for users takes linear time. This means that even your cell phone could compute the solution for a quite large number of users.

You are curious and ask about the algorithm, but the mathematician tells you that the one by Welzl ³ is simpler to describe. On the other hand, this algorithm is randomized instead of deterministic. But its expected time complexity is also .

The mathematician has certainly deserved the payment. Being a reasonably good option for all the users in the area, your incomes keep regular for many years. But, suddenly, one day your best customer decides to buy a motorhome.

He is not planning to leave the area, just to travel back and forth between his current house near the mountains and a nice spot next to river, sleeping on the way and moving along the straight road which connects them.

So you may no longer be a reasonable choice for your best customer! Of course, this is a serious problem for your business. Having a mobile stand, you could also move following him… but you are not willing to lose any of the other customers. What should you do? Overwhelmed, you decide to call the mathematician again.

You are really lucky, you know? He says this time. Your problem has just been solved by Banik et al.⁴. They consider a set of static points (your other customers) in addition to a single point which moves along a straight line (your best customer).

Their work describes the path you should follow, in order to be at the best location possible for the whole set customers. More technically, the authors provide a complete characterization of the locus of the center of the smallest enclosing circle for the whole set of points.

They first choose a coordinate system such that the straight trajectory of the mobile point coincides with the, horizontal, -axis. Then, they define the center function which sends each position of the mobile point to your best location, i.e., to the center of the smallest circle enclosing .

The authors show that this center function is continuous and piecewise differentiable. Actually, each of those differentiable pieces lies either on the boundary of the farthest-point Voronoi diagram of the set of static points, or on a horizontal line (parallel to the trajectory of the mobile point).

In addition, they prove that the number of pieces of the center function is linear in the number of static points. In other words, this center function is not too intricate, having a combinatorial complexity of .

This property allows them to give a simple linear algorithm for computing the center function, given the farthest-point Voronoi diagram of the set of static points (which can be computed in time ⁵). In order to do so, they use the line sweep technique. The event points are those where the center function changes from one segment to another.

All right, but what if my best customer decides to follow a non-straight road? You ask, just to show mathematician that you are following the flow of ideas.

That is a good question! He answers. The authors remark that the above results can be generalized to the case where the mobile point travels along a concatenation of straight segments. Then, the combinatorial complexity of the center function changes to , and this is also the complexity of its computation (again given the farthest-point Voronoi diagram of the static points).

Before you can ask what happens if a second customer decides to become mobile as well, the mathematician runs away heading to his office. He maybe trying to solve that case right now.