[math-fun] Disks in Euclidean approximation metrics ...
I've been asked a question to which I don't know the answer. Although this is not unusual, I'm wondering if there is an answer at all. If there is one, the audience here is likely to know of it. Let's start with the well-known to give a context. Embed Z^2 in R^2, and define the distance (0,0) to (x,y) to be |x|+|y|. Disks around a point are square diamonds. We now depart into vaguely familiar territory, but I'm finding it hard to pin down exactly what the question is, so I'm going to ask for some leniency, and for some creativity in finding the right question that's close to what I might be asking. When we use the Taxi-Cab metric above we are saying that the distance from (0,0) to (1,1) is 2. So let's short-circuit that and say that the distance from (0,0) to (1,1) is sqrt(2), and that we can only get somewhere by taking diagonal hops followed by taxi-cab journeys, and the *distance* is the minimum taken over all possible journeys. Disks around (0,0) are now octogons. I think. Are they regular? I suspect not. And then add that we are permitted to make a knight's move of distance sqrt(5). So journeys now consist of diagonal steps, knight's move, and taxi-cab journeys, and the distance from (a,b) to (c,d) is the minimum over all such journeys. Disks around (0,0) are now 16-gons, but are not regular. Obviously we can continue, but the question is: * Have these specific n-gons been studied? * Do these specific n-gons have names? * Do they have any interesting properties? Thanks for reading, I look forward to your thoughts, which I'll pass on to my interlocutor. Colin -- The power of accurate observations is commonly called cynicism by those who haven't got it. -- George Bernard Shaw
An easy starter problem is taking the endpoint to be any two knight moves from the origin. Sometimes it is better to move by three diagonals, and sometimes it is better to move by two horizontals or two verticals. The endpoint +(3,1) is also worth considering. Three diagonals is better than two Knight's moves, but not as good as one night move and one horizontal. Generally it seems best if (X,Y) is the total remaining distance to chose the move (x,y) for which x/y most closely matches X/Y, only resorting to horizontal and vertical at last. Is there a proof? I really love lattice walk problems, think that they are entirely practical, and with many branch points into other areas of mathematics and physics. Most of what I have seen has to do with counting and generating functions. The original article by Polya is an incredible landmark, and Alin Bostan's Habilitation is also great. Neither of these references deal with your question, but oh well, worth reading anyways. One critique, I'm not sure that I would say octagon, because it seems more like a square to me. Happy wanderings, --Brad On Wed, Oct 14, 2020 at 3:36 PM Colin Wright <math_fun@solipsys.co.uk> wrote:
I've been asked a question to which I don't know the answer. Although this is not unusual, I'm wondering if there is an answer at all. If there is one, the audience here is likely to know of it.
Let's start with the well-known to give a context.
Embed Z^2 in R^2, and define the distance (0,0) to (x,y) to be |x|+|y|. Disks around a point are square diamonds.
We now depart into vaguely familiar territory, but I'm finding it hard to pin down exactly what the question is, so I'm going to ask for some leniency, and for some creativity in finding the right question that's close to what I might be asking.
When we use the Taxi-Cab metric above we are saying that the distance from (0,0) to (1,1) is 2. So let's short-circuit that and say that the distance from (0,0) to (1,1) is sqrt(2), and that we can only get somewhere by taking diagonal hops followed by taxi-cab journeys, and the *distance* is the minimum taken over all possible journeys.
Disks around (0,0) are now octogons. I think. Are they regular? I suspect not.
And then add that we are permitted to make a knight's move of distance sqrt(5). So journeys now consist of diagonal steps, knight's move, and taxi-cab journeys, and the distance from (a,b) to (c,d) is the minimum over all such journeys.
Disks around (0,0) are now 16-gons, but are not regular.
Obviously we can continue, but the question is:
* Have these specific n-gons been studied?
* Do these specific n-gons have names?
* Do they have any interesting properties?
Thanks for reading, I look forward to your thoughts, which I'll pass on to my interlocutor.
Colin -- The power of accurate observations is commonly called cynicism by those who haven't got it. -- George Bernard Shaw
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If you restrict the hops to integer multiples of the allowed moves, then the set of points at a given distance from (0, 0) is going to be finite and lie on integer grid points. If you want to associate a polygon with it, you could define it as the convex hull of all points at the given distance from (0, 0). Consider the case where diagonal moves are allowed, but not knight moves. What is the set of points that are distance 4 from (0, 0)? They are: (4, 0) (0, 4) (-4, 0) (0, -4) And that's it. There are no diagonal moves involved in any of these points, since any diagonal move would result in a non-integral distance. The convex hull is a diamond. For a distance of sqrt(2), we get: (1, 1) (-1, 1) (-1, -1) (1, -1) In this case the convex hull is a square. On the other hand, if we want a distance of 1 + sqrt(2), then we get: (2, 1) (1, 2) (-1, 2) (-2, 1) (-2, -1) (-1, -2) (1, -2) (2, -1) So in this case the convex hull is an octogon. On the other hand, if the definition allowed arbitrary multiples of the allowed moves, then any point could be reached by: a*(1, 1) + b*(-1, 1) + c*(1, 0) + d*(0, 1) where a, b, c, and d are real rather than restricted to integers. (And only one of a, b is non-zero, and only one of c, d is non-zero, since we only care about minimal paths). Any given minimal path would then consist of a 45 degree diagonal segment, of any length, and a horizinal or vertical segment, again of any length. Determining the path is simple: Choose a diagonal segment that places you on a horizontal or vertical line with the point, then complete the path with a horizonal or vertical segment. "Circles" centered at (0, 0) would then be continuous curves consisting of the set of points at some given distance from (0, 0). I haven't looked looked at it closely, but I think you'd end up with an octogon in all cases (where the radius is > 0). Adding knight's moves to the mix complicates it a little, but I think the same basic approach would work. In all cases, the vertices of the polygon correspond to points where a particular class of line segment appears or disappears from the minimal path. Tom Colin Wright writes:
I've been asked a question to which I don't know the answer. Although this is not unusual, I'm wondering if there is an answer at all. If there is one, the audience here is likely to know of it.
Let's start with the well-known to give a context.
Embed Z^2 in R^2, and define the distance (0,0) to (x,y) to be |x|+|y|. Disks around a point are square diamonds.
We now depart into vaguely familiar territory, but I'm finding it hard to pin down exactly what the question is, so I'm going to ask for some leniency, and for some creativity in finding the right question that's close to what I might be asking.
When we use the Taxi-Cab metric above we are saying that the distance from (0,0) to (1,1) is 2. So let's short-circuit that and say that the distance from (0,0) to (1,1) is sqrt(2), and that we can only get somewhere by taking diagonal hops followed by taxi-cab journeys, and the *distance* is the minimum taken over all possible journeys.
Disks around (0,0) are now octogons. I think. Are they regular? I suspect not.
And then add that we are permitted to make a knight's move of distance sqrt(5). So journeys now consist of diagonal steps, knight's move, and taxi-cab journeys, and the distance from (a,b) to (c,d) is the minimum over all such journeys.
Disks around (0,0) are now 16-gons, but are not regular.
Obviously we can continue, but the question is:
* Have these specific n-gons been studied?
* Do these specific n-gons have names?
* Do they have any interesting properties?
Thanks for reading, I look forward to your thoughts, which I'll pass on to my interlocutor.
Colin -- The power of accurate observations is commonly called cynicism by those who haven't got it. -- George Bernard Shaw
Wed 14 Oct 2020, 16:36, Colin Wright wrote:
Embed Z^2 in R^2, and define the distance (0,0) to (x,y) to be |x|+|y|. Disks around a point are square diamonds.
(...) say that the distance from (0,0) to (1,1) is sqrt(2), and that we can only get somewhere by taking diagonal hops followed by taxi-cab journeys, and the *distance* is the minimum taken over all possible journeys. Disks around (0,0) are now octogons. I think.
I think you mean by octagon (or whatever shape of the disc) the convex hull in R^2 of the points in Z^2 having a given maximum distance from the origin, is that correct? Then the disc of radius 4 is not an octagon but a 12-gon with vertices at (+-4, 0), (0, +-4), (+-2, +-3), (+-3, +-2), the latter having distance 1+2 sqrt(2) = 3.828 from the origin. The distances of the grid points near the origin are as follows, in milli-units: [7071 6657 6243 5828 5414 5000 5414 5828 6243 6657 7071] [6657 5657 5243 4828 4414 4000 4414 4828 5243 5657 6657] [6243 5243 4243 3828 3414 3000 3414 3828 4243 5243 6243] [5828 4828 3828 2828 2414 2000 2414 2828 3828 4828 5828] [5414 4414 3414 2414 1414 1000 1414 2414 3414 4414 5414] [5000 4000 3000 2000 1000 0000 1000 2000 3000 4000 5000] [5414 4414 3414 2414 1414 1000 1414 2414 3414 4414 5414] [5828 4828 3828 2828 2414 2000 2414 2828 3828 4828 5828] [6243 5243 4243 3828 3414 3000 3414 3828 4243 5243 6243] [6657 5657 5243 4828 4414 4000 4414 4828 5243 5657 6657] [7071 6657 6243 5828 5414 5000 5414 5828 6243 6657 7071] - Maximilian
participants (4)
-
Brad Klee -
Colin Wright -
M F Hasler -
Tom Karzes