Archived

This topic is now archived and is closed to further replies.

Christoph

L1-Norm

Recommended Posts

Hi, I''ve often read that in many algorithms, the so called L1-Norm is used to calculate distances. The equation is d = |x2-x1| + |y2-y1| + |z2-z1| It is applied because it is linearic rather than quadratic. However, I noticed that the L1-Norm doesn''t give us the exact distance between two points. Example: P(1|1|1) and Q(0|0|0|) The "classical" distance is d = Sqrt(3) Yet, the L1-Norm returns d = 3 Assuming that I am able to compare two numbers, I ask myself whether I can use the L1-Norm in my algorithm without any changes for the calculations... Can you explain the difference between these two equations? Thx

Share this post


Link to post
Share on other sites
The L1-Norm distance, also sometimes called "Manhattan" distance, is only an approximation. It is equivalent to approximating the length of a triangle's hypotenuse by summing the lengths of the adjacent sides. It can get you ballpark, but not accurate. If you look at a graph of 2D points around a central point equally distant from the center, the Pythagorean distance graphs a circle around the center point, while L1-Norm graphs a square (or, rather, a diamond). All points on this square are considered to be the same distance from the center, while in reality (based on the accurate Pythagorean method) they are not.

Manhattan can be used in some cases where exact distance is not necessary, and where accuracy can be traded off for speed. It's really up to the programmer to make that distinction.


Golem
Blender--The Gimp--Python--Lua--SDL
Nethack--Crawl--ADOM--Angband--Dungeondweller


[edited by - VertexNormal on April 3, 2004 4:13:08 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by VertexNormal
The L1-Norm distance, also sometimes called "Manhattan" distance, is only an approximation.



Sort of. The L1-Norm (I normally hear it referred to as the "Taxicab Metric", though Manhattan distance is perfectly correct), is a specific measurement known as a metric. Metrics are a way of describing "distance", and have to satisfy three properties: the triangle inequality, symmetry, and that the "distance" between a point and itself is zero. (See http://mathworld.wolfram.com/Metric.html for specifics).

Anyways, the L1-Norm is still measure of distance (http://mathworld.wolfram.com/TaxicabMetric.html), and isn''t really an approximation as it is really just a different way to measure distance. The way you are used to calculating distance is known as the Euclidean Metric (http://mathworld.wolfram.com/EuclideanMetric.html).

The specific details why you can swap the Euclidean Metric and the L1-Norm is something best left for a math class that talks about metrics (e.g. Topology or Analysis). Breifly, since the L1-Norm is still a metric, when it is the metric that is always used everything is fine.

Share this post


Link to post
Share on other sites