1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As a first step, I'd figure out what a circle looks like using the taxicab metric. Have you done this? $\endgroup$ – RghtHndSd Dec 13 '13 at 22:38
  • $\begingroup$ I love the fact that circles in taxicab are squares. $\endgroup$ – reindeer Dec 13 '13 at 22:38
  • $\begingroup$ 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? $\endgroup$ – RghtHndSd Dec 14 '13 at 0:12
  • $\begingroup$ 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. $\endgroup$ – RghtHndSd Dec 14 '13 at 0:14
  • 2
    $\begingroup$ It would be helpful to include the requirement that the circle have the smallest radius in the question! $\endgroup$ – RghtHndSd Dec 14 '13 at 0:22
1
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It might be a stupid question, but do I rotate first, then do the steps you described, and then unrotate the result, or only rotate the result at the end? $\endgroup$ – reindeer Dec 19 '13 at 20:02
  • $\begingroup$ Rotate-compute-rotate. $\endgroup$ – Emanuele Paolini Dec 19 '13 at 22:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have no fixed center point, it can be chosen arbitrarily and has not to be one of the three points. $\endgroup$ – reindeer Dec 14 '13 at 0:38
  • $\begingroup$ 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. $\endgroup$ – user112167 Dec 14 '13 at 0:47
  • $\begingroup$ I think you solved the variant with two points. How do I get this radius for 3 points with unknown center? $\endgroup$ – reindeer Dec 14 '13 at 10:02
  • $\begingroup$ 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)$ $\endgroup$ – user112167 Dec 14 '13 at 11:10
  • $\begingroup$ Why does that work? $\endgroup$ – reindeer Dec 14 '13 at 14:40

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.