[Math] Calculating circle in taxicab geometry

circlesgeometrylinear algebra

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

Best Answer

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} $$

Related Question