Suppose you have a function $f: \mathbb{R} \rightarrow \mathbb{R}$ and a Point $P = (x,y) \in \mathbb{R}^2$. Now you want to find all $x_1, \dots, x_n$ such that

$$\forall \tilde x \in \mathbb{R} \setminus \{x_1, \dots, x_n\}: d(P, (x_1, f(x_1))) = \dots = d(P, (x_n, f(x_n))) < d(P, (\tilde x, f(\tilde x)))$$

with $d$ is the euclidean distance.

For this question, I am only interested in the number $n$ of points with minimal distance. Especially, you can assume that $f(x) = x^2$.

It is obvious that $n=2$ is possible:

$$P = (0,5)$$ $$x_1 \approx -2.179$$ $$x_2 \approx +2.179$$

But is $n=3$ or even higher $n$ also possible?

I guess if this is the case, then $P = (0, y_P)$ with $0 < y_p < 1$ and $x_1, \dots, x_n < 1$ like in the folliwng image:

enter image description here

  • $\begingroup$ So in plain English, you want a circle centred at $P$ to meet the graph of $\operatorname{f}$ in $n$ distinct places, and for there to be at least one point on the graph of $\operatorname{f}$ that is outside the circle? $\endgroup$ – Fly by Night Nov 5 '13 at 16:38
  • $\begingroup$ @FlybyNight: I want to get the center $P$ of a circle that has as many point of the graph of $f$ on its line as possible, but no point of $f$ is allowed to be inside of the circle. But I'm rather interested in how many points of $f$ are on the circle line. So $P$ is not enough (except if there is a formula to find all closest points to the graph of a quadratic function). $\endgroup$ – Martin Thoma Nov 5 '13 at 16:41
  • $\begingroup$ What does "on the circle line" mean? Do you mean "on the circle"? $\endgroup$ – Fly by Night Nov 5 '13 at 16:47
  • $\begingroup$ If $C$ is the circle with radius r around $(a,b)$ then all point in $\{(x,y) \in \mathbb{R}^2: \sqrt{(a-x)^2 + (b-y)^2}=r\}$ are on the circle line of $C$. I'm sorry, I only want to make clear that I don't mean $\{(x,y) \in \mathbb{R}^2: \sqrt{(a-x)^2 + (b-y)^2}<r\}$. I'm not sure how to say that properly in English. $\endgroup$ – Martin Thoma Nov 5 '13 at 16:51

In your problem, you need a curve to be tangent to a circle in as many places as possible without the curve going inside the circle. Let's think about this locally first. The curve is not allowed to cross inside the circle so, to use the $x$-axis as an extreem close up of the circle, we can't have $y=x$ and the $x$-axis. We can have $y=x^2$ and the $x$-axis. We can't have $y=x^3$ and the $x$-axis, etc.

Let's look at this question using the so-called "distance squared function". We consider the distance squared because squaring prserves the ordering of non-negative real numbers, i.e. for $x,y\ge 0$ we have $x>y \iff x^2 > y^2$. Moreover, taking away the square root makes it differentiable.

If we have a curve in the plane parametrised by $\gamma : I \to \mathbb{R}^2$, where $I \subseteq \mathbb{R}$, then define a two-parameter family of functions on $\gamma(I)$ given by $F : \mathbb{R}^2 \times I \to \mathbb{R}$ where $$F(P,t) := \operatorname{d}\left(P,\gamma(t)\right)^2 = \langle P-\gamma(t),P-\gamma(t)\rangle = \left(P-\gamma(t)\right)\cdot \left(P - \gamma(t)\right)$$ for all $P \in \mathbb{R}^2$ and $t \in I$. You can show that $F(P,t)=0$ if and only if there exists a circle, centre $P$, that passes through $\gamma(t)$. Moreover, we can show that $F=\partial F/\partial t = 0$ if and only if there is a circle, centre $P$, which is tangent to $\gamma(I)$ at $\gamma(t)$.

In general, for any $t \in I$, we can find a one-parameter family of points $P$ for which $F=\partial F/\partial t = 0$ (two equations in three variables). In fact there is a line of possible points $P$ for which there is a circle centred at $P$ and tangent to $\gamma(I)$ at $\gamma(t)$. This line is the normal line.

If we change the circle or if we change the curve ever-so slightly then this will break-up. Instead of the circle being tangent (think $y=x^2$ and the $x$-axis), the circle will either miss the curve (think $y=x^2+\varepsilon$, where $0<\varepsilon\ll 1$, and the $x$-axis), or the circle will intersect the curve in two distinct places (think $y=x^2-\varepsilon$ and the $x$-axis).

Usually, for each point $\gamma(t)$, there is a unique $P$ for which $F=\partial F/\partial t = \partial^2 F/\partial t^2=0$. The point $P$ is the so-called centre of curvature and the corresponding circle is the so-called osculating circle.

If we change the circle slightly, or if we change the curve slightly, then this situation will break-up. Instead of having a circle touching $\gamma(I)$ at $\gamma(t)$ three times at the same point (think $y=x^3$ meeting the $x$-axis) we will get a circle intersecting the curve and then ordinarily tangent to it (think $y=x^2(x-\varepsilon)$ and the $x$-axis) or a circle intersecting the curve in three nearby places (think $y=x(x-\varepsilon)(x+\varepsilon)$ and the $x$-axis) or a circle intersecting the circle one (think $y=x(x^2+\varepsilon^2)$). Notice that in all of these cases the curve must cross inside of the circle, and so are of no use to you.

Recap: So far, we have seen that we can satisfy your conditions for almost all curves and at almost all points, as long as your happy that $n=1$.

What about the case $F=\partial F/\partial t=\partial^2 F/\partial t=\partial^3 F/\partial t^3=0$? For isolated points on the curve, there are isolated point $P$ for which this holds. The points $\gamma(t)$ are called vertices. The corresponding circle is, again, the osculating circle. This time, the circle meets the curve "four times at once". This means that the osculating circle is tangent but, moreover, the curve does not cross inside the circle (thing $y=x^4$ and the $x$-axis). The parabola $y=x^2$ has a vertex at the origin. The osculating circle is centred at $\left(0,\tfrac{1}{2}\right)$. This set-up can break-up into a number of unwanted cases. The only favourable way is for the "order four" contact to break up into two "order two" contact (think $y=(x-\varepsilon)^2(x+\varepsilon)^2$ and the $x$-axis). In the case, the circle will be tangent to the curve in two places, but so that the curve does not cross inside the circle.

In the case of the parabola, $\gamma(t)=(t,t^2)$, the circles centred at $\left(0,\tfrac{1}{2}+\varepsilon^2\right)$ and with radii $\tfrac{1}{2}\sqrt{1+4\varepsilon^2}$ are tangent to $\gamma(I)$ at the points $\left(\pm\varepsilon,\varepsilon^2\right)$.

Even in this case, with $n=2$, there is not $P$ which minimises your distance. As $\varepsilon \to 0$ the radii get smaller, however, when $\varepsilon=0$ we have a circle tangent to the curve once and so this degenerates into the $n=1$ case.

Recap: Even locally, to get $n=2$ you need the curve to have an ordinary vertex. This happens at isolated points. The four vertex theorem tells us that on a "well-behaved" closed curve, there are at least four vertices.

If you want $n \ge 3$ then you're imposing hopelessly many conditions on the distance squared function. You want many, many derivatives to be zero for the same $P$ and for different $t$. In general, you'll be very, very lucky to find solutions to the problem for $n=3$. Of course, you can construct solutions for arbitrary $n$, try $P=(0,0)$ and $\gamma(t) = \left((2+\sin nt)\cos t, (2+\sin nt)\sin t\right)$.

  • $\begingroup$ I found another (much simpler) way to proof that there are no such points for quadratic functions. Do you think I should also post my solution? (It's a little bit long ... but maybe even shorter than yours) $\endgroup$ – Martin Thoma Dec 5 '13 at 23:33
  • $\begingroup$ @moose My post was not intended as a proof.It was intended as an explanation for you. Had I been writing a formal proof, it would have been much shorter. $\endgroup$ – Fly by Night Dec 7 '13 at 16:18

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.