1

I struggle with the problem of calculating radius and center of a circle when being in taxicab geometry. I need the case for two and three points including degenerate cases (collinear in the three point example, where the circle then should contain all three points, while two or more on its borders). Normally, I would simply use the equations

$ \sqrt{\left(x - a \right)^2 + \left( y - b \right)^2 }=r $

and resolve them to get radius $r$ and center point $c = (a,b)$ .

But in taxicab geometry, it is (from what Wikipedia says)

$ | x - a | + | y - b | =r. $

I have no idea how to get a equation system in order to reach a general formula for my circle, and Google was not too helpful here. Is there a way to deal with it?

So what I want is:

1) Given two points, calculate a circle with both points on its border. If there is more than one, pick the one with the smallest radius.

2) Given three points, calculate a circle with three points on its border if it exists, or two on its border and one inside. Again, smallest radius.

All that takes place in taxicab metric.

Edit:

To clarify, I do not mind whether there is no unique solution, but I would pick the one with smallest radius from the set of solution candidates.

I have no fixed center point, it can be chosen arbitrarily and has not to be one of the three points.

Edit:

I made a GeoGebra Sheet with the formula given by *Emanuele Paolini *, and it looks like it may work (I have no idea how to thoroughly proove it mathematically), but I as a non-math dude am satisfied with 'it looks like it works'.

http://www.geogebratube.org/student/m65241

jcklie
  • 233
  • As a first step, I'd figure out what a circle looks like using the taxicab metric. Have you done this? – RghtHndSd Dec 13 '13 at 22:38
  • I love the fact that circles in taxicab are squares. – jcklie Dec 13 '13 at 22:38
  • To be clear, you are asking: Given three points $(x_1, y_1), (x_2,y_2), (x_3,y_3)$, how do I find the center and radius for the "circle" going through those three points? – RghtHndSd Dec 14 '13 at 00:12
  • On second thought, that is not well-defined: three points do not determine a (unique) circle in the taxi-cab metric. So I do not follow what you are asking. – RghtHndSd Dec 14 '13 at 00:14
  • Can you say why there is no unique circle? I do not care whether it is unique, I just want one with the smallest radius. – jcklie Dec 14 '13 at 00:15
  • Consider the points $(0,0), (1,1), (1,-1)$. There are infinitely many circles that go through those three points. Indeed, start with a square whose corner is at the origin. The sides of the square can be make arbitrarily large and will always contain those three points. – RghtHndSd Dec 14 '13 at 00:16
  • In that case, I would want $c=(1,0)$ with r= 1 – jcklie Dec 14 '13 at 00:22
  • 2
    It would be helpful to include the requirement that the circle have the smallest radius in the question! – RghtHndSd Dec 14 '13 at 00:22

2 Answers2

1

In the taxi-cab metric the distance between two points $x,y \in \mathbb{R}^n$ is defined as : $$ d(x,y) = d((x_1,x_2,\ldots,x_n),(y_1,y_2,\dots,y_n)) := |x_1-y_1| + \dots + |x_n-y_n| = \sum_{i=1}^n |x_i-y_i| $$ Which is the shortest distance if we are only allowed to move "north, east, south or west", hence, squares.

The radius is the distance, so $r=d(x,y)$. Now remembering that the "circles" are squares and you know the radius, you can draw the square around it. If you have three points calculate the distance as above between one point(the center) and the other two points, take the max distance of those calculations and you have the radius such that the square contains all 3 points.

Edit: If you want the smalles radius from a certain center point you can use the above, if you can choose one of the points randomly, you need to check some more, because if we have the following situation:point example

The center point with the smallest radius is point 2. Because the distance between point 1 and point 2 is bigger then between point 1 and point 3, the square around point need to have at least the radius of the (taxi-cab) distance between point 1 and 2. (with center 2). If we take point 1 as the center, the radius has to be at least the distance between point 1 and 3. I hope this will make things more clear.

user112167
  • 1,812
  • I have no fixed center point, it can be chosen arbitrarily and has not to be one of the three points. – jcklie Dec 14 '13 at 00:38
  • for question 1: the center point is $((x_1-x_0)/2,(y_1-y_0)/2)$, and the radius you can calculate by above. In $\mathbb{R}^n$ you can also calculate the average coordinate values. With the 3 points situation it's the same, look at the radius which get all points within the border or on it. – user112167 Dec 14 '13 at 00:47
  • I think you solved the variant with two points. How do I get this radius for 3 points with unknown center? – jcklie Dec 14 '13 at 10:02
  • Sorry it had to be $((x_1+x_2)/2,(y_1+y_2)/2)$. In case of three points it becomes $((x_1+x_2+x_3)/3,(y_1+y_2+y_3)/3,(z_1+z_2+z_3)/3)$ assuming that it is in $\mathbb{R}^3$, if it is in $\mathbb{R}^2$ then $((x_1+x_2+x_3)/3,(y_1+y_2+y_3)/3)$ – user112167 Dec 14 '13 at 11:10
  • Why does that work? – jcklie Dec 14 '13 at 14:40
1

So what you are asking is: find the smallest square (rotated 45 degrees with respect to axes) containing $2$ or $3$ points. Automatically the smallest square will have at least two points on the bounday.

  1. It is simpler if you make a 45 degree rotation of your problem so that square have sides parallel to the axes.

  2. The solution is not unique, even if you request the smallest square. For example if you take points $(0,0),(1,0),(2,0)$ (in the rotated frame) any square of size $2$ which contains $(0,0)$ and $(2,0)$ will be a solution.

  3. Clearly the side of the minimal square will be given by this formula: $$ s = \max\{|x_1-x_2|,|x_1-x_3|,|x_2-x_3|,|y_1-y_2|,|y_1-y_3|,|y_2-y_3|\} $$ where $(x_i,y_i)$ are the coordinates (in the rotated frame) of your points.

  4. To find a particular solution you can always take the lower-left vertex of your square to be the point with coordinates: $$ \begin{cases} x = \min\{x_1,x_2,x_3\}\\ y = \min\{y_1,y_2,y_3\} \end{cases} $$

  5. The 45-degree rotation is given by $$ \begin{cases} x' = \frac{\sqrt 2}{2}(x-y)\\ y' = \frac{\sqrt 2}{2}(x+y)\\ \end{cases} $$

Emanuele Paolini
  • 21,447