# Minimizing the distance to a finite set of points in the plane

Let $A_1,A_2, \ldots ,A_n$ be a finite set of $n$ distinct points in ${\mathbb Q}^2$. For any $\varepsilon >0$, let $B(A_i,\varepsilon)$ denote the closed ball with center $A_i$ and radius $\varepsilon$. If we set

$$I = \bigg\lbrace \varepsilon >0 \bigg| \bigcap_{k=1}^n B(A_k,\varepsilon) \neq \emptyset \bigg\rbrace$$

then clearly $I$ is a closed interval of the form $[\varepsilon_0,+\infty ($.

Is it true that $\varepsilon_0$ is always algebraic over $\mathbb Q$ ?

Is it true that $[{\mathbb Q}(\varepsilon_0):{\mathbb Q}]$ must always be a power of $2$ ?

-

By Helly's Theorem, $\epsilon_0 = \max \epsilon_{i, j, k}$, where $\epsilon_{i, j, k}$ denote the corresponding value of '$\epsilon_0$' for just the points $A_i, A_j, A_k$.

For an obtuse triangle (or 3 collinear points), $\epsilon_0$ will be half of the longest distance, which is algebraic, and $[\mathbb{Q}(\epsilon_0) : \mathbb{Q}] = 1$ or 2 by the distance formula.

For an acute triangle, $\epsilon_0$ will be the circumradius. I don't know immediately what the cartesian coordinate formula is, but since it's just mid points and perpendicular bisectors, it will be constructible, and hence $\epsilon_0$ is algebraic. I believe your guess about power of 2 will follow from knowing the formula.

Edit: (Note: This paragraph is irrelevant, as there is a better approach using the circumradius directly.) From Wikipedia, you can obtain the Cartesian Coordinates, which only involve the coordinates and their squares. This only gives the circumcenter. We still need to calculate the circumradius, but given the equations, we have $\mathbb{Q}(\epsilon_0) \subset \mathbb{Q}[ \sqrt{A_x}, \sqrt{A_y}, \sqrt{B_x}, \sqrt{B_y}, \sqrt{C_x}, \sqrt{C_y}]$, where $A, B, C$ are the cartesian points of the triangle. Hence, this implies that $[ \mathbb{Q}(\epsilon_0) : \mathbb{Q}] = 2^n$, where $n$ is an integer from 0 to 6 for the triangle (and hence general case). We may additionally assume that $(A_x, A_y) = (0,0)$ since we can translate otherwise, which shows that it $n\leq 4$.

Alternatively, use the Euclidean geometry expression that $$R = \frac {abc}{\sqrt{(a+b+c)(a+b-c)(a-b+c)(-a+b+c)}} = \frac {abc} {\sqrt{2a^2b^2 + 2b^2 c^2 + 2c^2 a^2 - a^4 -b^4 - c^4}} = \frac {abc}{4S}$$ where $a, b, c$ are side lengths of the triangle. $a^2, b^2, c^2$ are all rational by the distance formula, so $R^2 \in \mathbb{Q}$, shows that the degree of the extension is at most 2.

Edit: The first paragraph should have been max, instead of min. I can explain this in slightly more detail if you need.

Edit: For the obtuse triangle case, we have $\mathbb{Q}(\epsilon_0) = 1, 2$ directly from the distance formula of 2 points $\sqrt{X^2 + Y^2}$.

-
Of course, the details that interest me are not the ones about Helly’s theorem, but the ones about the circumradius. It is an interesting exercice to say all about it without getting lost in the complicated formulas. If this slighly off your league, perhaps someone else will fill that gap. – Ewan Delanoy Jan 9 '13 at 3:02
It is out of my league because I haven't done algebraic extensions in a long time. I believe that $\mathbb{Q}(\epsilon_0) \subset \mathbb{Q}( \sqrt{A_x}, \sqrt{A_y}, \sqrt{B_x}, \sqrt{B_y}, \sqrt{C_x}, \sqrt{C_y} )$ is sufficient to answer your question on degrees, but am not 100% certain. This should be a trivial undergrad algebra fact. – Calvin Lin Jan 9 '13 at 3:06
It is a “trivial undergrad algebra fact” indeed, even I know how to show this. What I am expecting is a nice geometrical characterization of when the degree of $\varepsilon_{i,j,k}$ is exactly $2^p$, for each $0\leq p\leq 6$. – Ewan Delanoy Jan 9 '13 at 3:15
@EwanDelanoy In that case, this is a complete proof. – Calvin Lin Jan 9 '13 at 3:17
@EwanDelanoy That wasn't stated in your question. Furthermore, that is just simple undergrad algebra on field extensions. I believe that $\mathbb{Q} (\epsilon_0) = \mathbb{Q} [ \ldots]$, which will then give you the classification. – Calvin Lin Jan 9 '13 at 3:25