The Proceedings of the 36th Canadian Conference on Computational Geometry (CCCG 2024) are now online! The conference was mid-July but when I looked for the proceedings at that time I didn’t find them. I have two papers in the proceedings: “Maintaining Light Spanners via Minimal Updates” (with Hadi Khodabandeh) and “Well-Separated Multiagent Path Traversal” (with Gleb Dilman, Valentin Polishchuk, and Christiane Schmidt). I’ve already written here about the spanner paper but the path traversal paper is newer, so I thought I’d say a little about it here.

The basic problem we study is to coordinate a collection of moving objects (modeled as unit disks) so that they don’t crash into each other. The objects must all follow a fixed path at a fixed speed, but they can start at different times, so the only choice is to find a start time that won’t put each object on a collision course with the others. This might model the paths of amusement park ride carriages, certain forms of public transport, or parts in a manufacturing process, for instance. My coauthors have put together a web applet where you can try scheduling the start times yourself, with the goal of getting a target number of items through in a target time: Necklace Game. The rest of this post will make more sense if you try it. I don’t find it easy!

The applet includes examples of objects on multiple paths, but the main problem that we study in the paper involves only a single polygonal path, such as the one in the third panel of the applet. The goal of that panel is to get as many items as possible through the path in a fixed time limit; instead, you could think of it as getting the highest rate of items through in some kind of steady state. If you try it, you’ll notice that at first it makes sense to send out objects at a fixed rate, as tightly as you can without having consecutive objects crash at the tight bends of their paths. But that doesn’t work by itself to get the best score out of that panel, because it will cause a crash later at a point where the path draws near to itself. Instead, you could use a wider uniform spacing that causes the objects to perform a zipper merge when they draw near to each other, or you could send bursts of tightly packed objects with gaps between the bursts.

The first of these two types of solution, with a uniform spacing between objects, is the first one we study in the paper. It turns out that each potential crash (between items \(k\) releases apart, on any two nearby edges of the path) blocks out an interval of spacing times, and that the number of these blocked-out intervals is polynomial in the complexity of the path and the length of its segments (relative to the unit disk radius), giving us a polynomial time algorithm for finding the optimal uniform spacing.

But uniform spacing is not optimal, in general. For some instances, scheduling the release times in a bursty or irregular pattern can achieve significantly greater density than uniform release times. Our paper shows how to find near-optimal schedules for paths of bounded length, but it turns out to be hard to optimize or approximate to within even a polynomial factor when the length of the path can be high. The proof involves designing a path for which the good release times approximate a discrete set, and for which only certain pairs of these good release times would avoid a collision, so that finding a good schedule amounts to finding a large clique in the graph of good pairs of release times.

(Discuss on Mastodon)