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$
8
  • $\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, 2013 at 22:38
  • $\begingroup$ I love the fact that circles in taxicab are squares. $\endgroup$
    – jcklie
    Dec 13, 2013 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, 2013 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, 2013 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, 2013 at 0:22

2 Answers 2

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$
2
  • $\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$
    – jcklie
    Dec 19, 2013 at 20:02
  • $\begingroup$ Rotate-compute-rotate. $\endgroup$ Dec 19, 2013 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$
5
  • $\begingroup$ I have no fixed center point, it can be chosen arbitrarily and has not to be one of the three points. $\endgroup$
    – jcklie
    Dec 14, 2013 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, 2013 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$
    – jcklie
    Dec 14, 2013 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, 2013 at 11:10
  • $\begingroup$ Why does that work? $\endgroup$
    – jcklie
    Dec 14, 2013 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.