Voronoi Diagrams in the Knight Metric

11.11.2023

I had the random idea this morning to consider Voronoi diagrams using the distance induced from some leaper. For the vanilla knight \(L(1,2)\), for example, pick squares on the infinite chessboard and color them uniquely. Call these the seeds. Then color each other square on the board the color of the closest seed, where distance is the fewest number of \(L(1,2)\)-moves needed to get between two squares. Here is a Voronoi diagram using \(L(1,2)\), where there are eight seeds placed around a circle of radius 200 (on a 1000x1000 board):

voronoi diagram L(1,2) eight seeds

I'm interested in what happens when we fix the set of seeds and vary the metric. For instance, keeping the same seeds as the above picture but using an \(L(1,6)\) leaper, we get this much wavier picture:

voronoi diagram L(1,6) eight seeds

I've used the same seed set as above, but varried the leaper along \(L(1,i)\) for \(1\leq i \leq 50\). I slowed down the first few frames of the following gif so you can see the structure before it starts to devolve:

voronoi L(1,i) eight seeds

But I think the best one so far is choosing \(L(i, i+i) \). I've changed the color palette to fit the fall time and generated the first 477 frames of this changing diagram.

very cool :)
In this animation, I'm only slowing down the gif during the first and last frame, so the slowness at the end is natural. This is cool and it seems a bit continuous. There are some problems, as with a lot of discrete visuals. A square can be equal distance from two seeds, for example, so we have to break the tie. But as long as we're consistent in tie-breaking, it should be okay. It's also worth showing that \(L(i,i+1)\) actually does induce a metric for \(i\geq1\). I want to spend more time on this but I'm already using this to procrastinate grad applications and school work so maybe I will leave it here.

< back to posts