10
$\begingroup$

The taxicab metric can be used to measure distances in idealized gridded cities. However, usually this serves only as a fun exercise for students.

I'm looking for engaging (as non-technical as possible) examples of real-world applications of the taxicab metric (or other metrics inspired by cities, such as the British rail metric).

It seems that it's mostly used in machine learning, but everything I've seen so far is too technical to explain to laypeople. So, I'd love to get some ideas!

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ "taxicab metric", "British rail metric" -- Even though this stack exchange is probably where you'd expect to find the folks most-likely to know these terms, you might just give (or link to) a definition for them so there is no question what you're referring to. $\endgroup$
    – Nick C
    Apr 22 at 18:13
  • 1
    $\begingroup$ You could use "distance in a game like D&D," perhaps. $\endgroup$
    – Opal E
    Apr 22 at 22:29
  • $\begingroup$ @OpalE D&D (since fourth edition) has allowed diagonal and usual movement at equal cost. Third edition used Pythagoras. I am not sure of a miniature-based roleplaying game that forbids diagonal movement, though some probably exist. $\endgroup$
    – Tommi
    Apr 23 at 7:05
  • 1
    $\begingroup$ Actually, movement in Miseries and misfortunes may not be diagonal. So there you have it. An obscure niche indie game, but still. $\endgroup$
    – Tommi
    Apr 23 at 7:07
  • 2
    $\begingroup$ I remember driving a convoluted zig-zaggy route to university since the route more closely resembled a direct path (the hypotenuse). It took me far too long to realize my route was no more efficient than a route with a single turn, even though it deviated a long way from the hypotenuse. $\endgroup$
    – Rebecca J. Stones
    Apr 24 at 5:20

2 Answers 2

Reset to default
8
$\begingroup$

A variation on Matthew's bakeries:

The taxicab Voronoi diagram shows which firestation can reach a fire fastest in a city whose roads follow an orthogonal grid. The dots below are firestations, and each region collects the points closer to its firestation than to any other.

VorDiag

Wikimedia Commons image

There are also applications to VLSI layout, but less easily explained:

Papadopoulou, Evantha, and D. T. Lee. "The $L_\infty$ Voronoi diagram of segments and VLSI applications." International Journal of Computational Geometry & Applications 11, no. 05 (2001): 503-528. Journal link. "the $L_\infty$ and $L_1$ Voronoi diagram of segments are equivalent under a $45^\circ$ rotation."

Incidentally, the taxicab metric is also known as the Manhattan metric, or the $L_1$ or $\ell_1$ metric.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What does "… collects the points closer to its firestation" mean, please? $\endgroup$
    – Robbie Goodwin
    Apr 24 at 0:07
  • 1
    $\begingroup$ @RobbieGoodwin It just means that each region is the set of all points that is closest to the fire station in its region. $\endgroup$
    – Matthew Daly
    Apr 24 at 4:11
  • $\begingroup$ I'd remark that the example taxicab Voronoi tesselation is ill-defined: because the two points in the upper right lie exactly on a diagonal, there is a whole region of locations whose distance is the same to both points. The shown cells with the L-shaped boundary between teal and light green are apparently an artifact of the way the diagram was computed. $\endgroup$
    – leftaroundabout
    Apr 24 at 11:23
  • $\begingroup$ @leftaroundabout: You are correct re a whole bisector region when the two sites lie on a diagonal. The convention has been to select a boundary of the bisector for display. I think this goes back to 1980: Lee, Der-Tsai. "Two-dimensional Voronoi diagrams in the Lp-metric." Journal of the ACM (JACM) 27, no. 4 (1980): 604-618. $\endgroup$
    – Joseph O'Rourke
    Apr 24 at 12:12
  • $\begingroup$ @MatthewDaly Thanks for that. $\endgroup$
    – Robbie Goodwin
    Apr 24 at 17:50
7
$\begingroup$

I would argue that the taxicab metric as such is actually carrying its weight if it is a "fun exercise for students" that points out that there are real-world applications where the Euclidean distance is not an effective metric for modeling.

The notion of metrics in general is chock-full of real-world applications. Here is an example

I own three bakeries in a city and I'm planning to open a fourth. I want a location that is "close" to as many potential new customers as possible, but not so "close" to my existing stores that the new store would compete with my existing business (but "close" enough that I can still effectively manage all four locations).

The mathematical model that I can use to turn that abstract concept of closeness into data that I can use to make a real-world decision is a metric space. Is the taxicab metric the right metric space for me? It might be a reasonable place to start, depending on the city I live in and the amount of simplicity I am willing to trade for valid data.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.