I've recently become interested in randomly generating Voronoi diagrams to create "territory" maps (similar to this) for a project I've been working on.

Traditional Voronoi diagrams using an Euclidean metric don't present sufficient cell variation for my liking so I've been attempting to utilize a L∞ metric instead, using Fortune's Algorithm as the means to create the diagrams. Fortune's method utilizing a L∞ metric, unlike its Euclidean counterpart, is not particularly well-documented and my understanding as a result has been less than clear.

Specifically, I'm unsure whether my understanding of how spike events (called circle events in the Euclidean instance) are determined - and thus the vertices of the Voronoi diagram discovered - is correct or not, and I would very much appreciate some help in either confirming my method or correcting it.

My understanding thus far is based on the following: that the L∞ distance between two points p and q is defined d(p,q) = max(|px-qx|, |py-qy|), and the bisector between p and q is representative of all points equidistant using that formula.

I believe then, as stated in the last paragraph on pg. 12 in this paper by Evanthia Papadopoulou, that a square containing both points and whose sides are equal to the L∞ between them (rather than the Euclidean circle) can be used to check for spike events.

Insquare test

Two squares (one solid, one dashed) containing points p and q (Figure 1). The point in the middle of each square (blue) would seem to suggest a spike event, or vertex, when it is resolved (below, Figure 2).

pq Bisector

The same method applied to points p, q, and r yields the following (Figure 3):

Voronoi Diagram pqr

It seems to work well, but I'm uncertain because Papadopoulou goes on to add

[the Euclidean incircle test] now simplifies to a test involving the square defined by the three elements. (Note that three elements need not always define a square). In the worst case the L∞ incircle test corresponds to 1) determining the intersection point I of two lines (bisectors), 2) determining the intersection point J of a line and a 45◦ line through I, and 3) comparing the horizontal or vertical distances between I and J and between I and one of the defining elements (12)


A spike event C takes place at t = xc + w where xc is the abscissa of the intersection point and w is the distance of the intersection from the inducing element (14).

I'm not entirely sure whether the method is consistent with the above, as I'm not entirely sure what she means.

Additionally, I'm concerned because in Figure 3 the first vertex to the right (point a below, Figure 4) potentially should not exist because its partner vertex b would fail to be created as a third point, q, would lie inside the second square of p and r.

enter image description here

As Fortune's Algorithm traces the Voronoi edges when it creates the diagram with the movement of the sweep line, would the theoretical edge being traced from a to b not already be past the point next to a when the sweep line arrives at q? Or, since b is not created, does the edge moving left from a simply not grow until the point next to it is found?

Thank you in advance for any feedback/insight/comments/answers. I think I'm nearly there but any affirmation or corrections would be extremely appreciated and welcome. I hope I've explained myself sufficiently (and that my post is not too open-ended) but please let me know if I can clarify or elaborate on anything.


Your Answer

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

Browse other questions tagged or ask your own question.