Ellen Εμίλια Άννα Zscheile (RWTH Aachen University, Aachen, Germany)
29.08.2026
This paper is part of documentation for the anyangle project. The pull requests related to this paper are usually tagged via “45 deg pathing”.
This project is funded through NGI0 Commons Fund, a fund established by NLnet with financial support from the European Commission’s Next Generation Internet program. Learn more at the NLnet project page for the Topola autoplacer.
This paper introduces the “diagonal taxicab norm” (and implicitly also a corresponding distance metric), that can be used to take a shortest-path search algorithm, and make it find shortest paths on a grid where every bend in a path must have an angle that is an integer multiple of 45° (“45° bent paths”), instead of e.g. shortest paths according to the usual euclidean metric, without having to perform the search itself on a fine grid, which would be computationally too expensive. Note that a resulting path that is neither aligned to an axis or a diagonal, that is, has both some non-zero axis-aligned component, and some diagonal component (in case of working in a dimension higher than 2, this can also be diagonal over some axes and axis-aligned for other axes), then corresponds conceptually to a non-singular equivalence class of 45° bent paths which all have the same length in the euclidean metric (where each straight segment gets measured separately, then they get summed), that is equal to the length in the diagonal taxicab norm between the main endpoints.
Given that only the second variant of the norm that this paper presents behaves as expected indepenent of the amount of dimensions, the first variant should be deemed as expository for the development of the second variant (the “adaptive diagonal taxicab norm”). In the anyangle project, for now only the 2D variant was implemented, and in that case, both variants coincide.
Let be an arbitrary field with absolute value function .
Definition 2.1: Given a -vector space , a norm on is a function with the following properties:
Definition 3.1: Let . We define the naïve diagonal taxicab norm as:
Proof: is indeed a norm because all of the following holds: Let and . Then:
In general, the following norm bounds hold (whereby is the taxicab norm):
Well-definedness:
Subadditivity:
Note that the in the definition doesn’t need any special considerations, and we want the to get smaller in the split case because it gets multiplied with . The transformation in the second line warrants special attention because there the values to minimize over actually get larger, but they only get larger in a sense bounded by the the smallest entry of in the first term.
Absolute homogeneity:
Positive definitivity:
The norm defined in the previous section has a big problem: It has a too strong dependency on the dimension on , and for differing dimensions , they don’t have much in common. The “scaling” of the norm along the dimension only admits going through the center of a (potentially “higher”) cube. It doesn’t achieve the goal of allowing arbitrary 45° paths for .
For a vector , define
For reference, the naïve diagonal taxicab norm of the previous section with fixed is:
Therefore, we want to also explore a different choice: Also allowing to go through the center of an arbitrary lower-dimensional cube. It should coincide with the norm of the previous section for .
Definition 4.1: We define the property of a function or sequence being a monotonically decreasing and non-negative by fulfilling all of the following:
We embed the tuples of finite length into the space of functions with that property by taking the absolute value of each , and then sorting them by decreasing (absolute) value.
Definition 4.2: On the space of monotonically decreasing, non-negative sequences , such that , we define the following fundamental diagonal taxicab norm:
Similarly, we define this inthe same way for tuples of finite length by embedding it in the space of these sequences, and extending them into infinite sequences by assigning for all .
For simplicity, we consider only sequences for which this “norm” is finite / converges.
Proof: Let be monotonically decreasing, non-negative sequences. Let .
Linearity:
Positive definitivity:
For , we have the following:
Proof: As stated at the beginning of this section, the left-hand side is equal to:
and the right-hand side is equal to:
which are equal.
There is a relation to the forward difference operator:
Definition 4.4: Let be a commutative monoid, and be a step-size (for , we assume unless stated otherwise). Let be an abelian additive group with inverse . Then we have the forward difference operator
Remark 4.5: We can thus alternatively express/define this fundamental diagonal taxicab norm as follows:
In order to continue, we need some monotonicity properties:
Lemma 4.6: The functions
is convex, non-negative and monotonically decreasing.
Lemma 4.7: Let . For a monotonically decreasing function the following holds for all :
Proof: Let be monotonically decreasing. Let and .
Definition 4.8: On the space of bounded sequences , such that a permutation exists with
we define the diagonal taxicab norm:
Similarly, we define this in the same way for tuples of finite length by embedding it in the space of these sequences, and extending them into infinite sequences by assigning for all .
For simplicity, we consider only sequences for which this “norm” is finite / converges.
Proof: Let be in the given space above with corresponding . W.l.o.g. assume that is the identity. The two given equation for are equal via:
Proof: Let be in the given space above with corresponding . W.l.o.g. assume that are identity functions. Let be the corresponding permutation for , which is defined by pointwise addition.
Subadditivity:
i.e. changing the permutation away from the mon. decreasing one can only make the sum smaller.
Absolute homogeneity: Let . We have for all . Thus:
Positive definitivity:
In order to avoid having to deal with rounding complications and such arising from the usage, we propose the following:
Consider two monotonically decreasing tuples with non-negative entries, corresponding to the norm values and respectively.
If and holds (and analogous for instead of ), we can directly conclude that the first tuple is smaller (resp. larger) than the second one. If the two tuples are equal, the associated norm values are obviously also equal.
Otherwise, we perform the following modifications:
If (analogously with the two tuples swapped), then we can square both sides, which are non-negative, and because squaring is convex on non-negative arguments, we get:
That way, we avoid the potential rounding problems that would’ve come with dealing with at the cost of “square-rooting” the allowed input ranges in the usual case of fixed data type size of bounded computer integers and IEEE 754 floating-point numbers.