Approximation of curves

Question

When constructing minimax (sup-norm) polynomial approximations of real-valued functions, well-known results say (roughly speaking) that optimal solutions are characterized by the fact that they have equi-oscillatory errors.

Can this be generalised to cover approximation of 2D or 3D curves?

The simplest example is the first quadrant of the circle $x^2 + y^2 = 1$. I have constructed very good approximations using polynomials $P(t) = (u(t), v(t))$, and I find that they are equi-oscillatory, in the sense that the error function $u(t)^2 + v(t)^2 -1$ oscillates equally about zero. I'd like to know if there's any theory that supports this experimental finding.

Of course, I could just write the circle quadrant as $x=\cos t$, $y=\sin t$, and approximate the sine and cosine functions by polynomials on $[0, \tfrac12 \pi]$. But this is a different problem, and this approach gives circle approximations that are significantly inferior to the ones I constructed. So, decomposing the 2D problem into two 1D ones is not what I'm after.

In three dimensions, my "curve" would be given by a pair of equations $f(x,y,z)=0$ and $g(x,y,z)=0$. In this case, I don't even know how to define "equi-oscillatory" or even "oscillation".

I asked this question on Math.Stackexchange, and got zero response.

For circles, specifically, there are some good results in the answers to this related question, but no progress on more general curves or any underlying theory.

Edit: Here is a more formal/rigorous statement of the 2D problem. We are given a function $f:\mathbf{R}^2 \to \mathbf{R}$, and we are considering the set $F = \{(x,y) \in \mathbf{R}^2 : f(x,y)=0\}$ to be a planar curve. Let $P_0 = (x_0, y_0)$ and $P_1 = (x_1, y_1)$ be two points in $F$ (i.e. two point on our curve). We can assume that $P_0$ and $P_1$ belong to the same connected component of $F$. For each $(x,y) \in \mathbf{R}^2$, let $d(x,y)$ denote the Euclidean distance from $(x,y)$ to the set $F$. I want to find polynomials $u:[0,1] \to \mathbf{R}$ and $v:[0,1] \to \mathbf{R}$ such that $$ u(0) = x_0 \quad ; \quad u(1) = x_1 \\ v(0) = y_0 \quad ; \quad v(1) = y_1 $$ and such that $$ \max\big\{ d\big(u(t),v(t)\big) : t \in [0,1]\big\} $$ is minimised. In other words, I want the curve $t \mapsto \big( u(t), v(t) \big)$ to be an optimal approximation of the portion of my original curve lying between the points $P_0$ and $P_1$. And I'm interested in knowing if this optimal solution is equi-oscillatory, in some sense.

A simple concrete example is $f(x,y) = x^2y^2 + (x-1)(x-2)$, with $P_0 = (0,0)$ and $P_1=(2,0)$. I want an optimal approximation of the piece where $y \ge 0$. It looks like this:

Answer 1

This is an extended comment. What exactly you are trying to minimize?

First version: given an algebraic curve with equation $F(x,y)=0$, and two points on this curve $M,N$, find the polynomials $p,q$ of degree at most $d$ such that $(p(0),q(0))=M$, $(p(1),q(1))=N$, and $$\max_{t\in[0,1]}|F(p(t),q(t))|$$ is minimal. Some condition about two points is necessary here, otherwise you will have a trivial constant solution $(p(t),q(t))=X$ where $X$ is any point on your curve. But of course you may consider various conditions at the ends.

Second version. Given two functions $x(t),y(t)$ on $[0,1]$, to minimize $$\max_{t\in[0,1]}(|p(t)-x(t)|^2+|q(t)-y(t)|^2).$$

These are two completely different problems.

The solution for the circle you refer to seems to be related to the first problem. If this is what you ask, there are several possible generalizations to higher dimension, using any norm. For example, if the curve is given by two polynomials $F$ and $G$ of three variables, you may want to minimize $\max\{|P(p,q,r)|,|Q(p,q,r)|\}$. But again some additional condition is necessary to avoid the trivial constant solution.

EDIT. However, there are additional difficulties with the First formulation. An algebraic curve $F(x,y)=0$ may consist of several pieces, and if we really want to approximate it, one has an additional requirement that the two points $M,N$ are on one piece. Moreover, there can be several ways along the curve $F(x,y)$ from $M$ to $N$ (always more than one way!) and this is not reflected in the precise formulation. So it is possible to have $F(p(t),q(t))$ uniformly small on $[0,1]$ but the curve $(p(t),q(t))$ does not approximate $F(x,y)$ in any reasonable way: the curve $F(x,y)=0$ may have a loop between $M$ and $N$, while the curve $(p(t),q(t))$ cheat and skip this loop.

All this shows that there is no meaningful precise statement of the problem yet.

Answer 2

In response to a previous answer of you mentioned the Remez exchange algorithm. Looking into that makes me suggest the following comments and conjectures:

Consider for now the 2D case

1. Let's just say that you have a connected curve $F$ (since you could always define $f$ as "distance from $F$").

2. The notion of distance still seems a bit unspecified. I'll take this as the definition: Given The curve $F$ with points $P_0,P_1$ and a candidate approximation $Q(t)=(u(t),v(t))$ defined on $[0,1]$ consider all "acceptable" parametrizations $P(t)=(x(t),y(t))$ of $F$ with $P(0)=P_0$,$P(1)=P_1$ and look at $\max_t d(P(t),Q(t))$. I'll not require $Q(0)=P_0$ and $Q(1)=P_1$. although one could. Some pathological $F$ could create various problems but I'll ignore that and also assume that the degree of the approximation is high enough to handle the twists and turns of $F$. Then (if all goes well) the set of points at distance $\delta$ from $F$ form a simple closed curve $F^*$

3. I'll guess that the best approximation $Q$ is unique and has some number $M$ of points $Q_1,Q_2,\cdots,Q_M$ occurring in order on $Q$ and all lying on the closed curve $F^*$ and on "alternating sides" of $F.$ I'd like to define that by saying that each segment $Q_i,Q_{i+1}$ crosses $F$ ($\cdots$ an odd number of times) but instead I'll say that $F^*$ can be traversed so that they occur in order $Q_1,Q_3,Q_5,\cdots Q_6,Q_4,Q_2.$

4. What $M$ should be (depending on the allowed degree) I'm not quite sure. Just enough that passing through those points (with gradient directed away from $F$) determines $Q(t)$.

5. For 3D the best I can do is say that something similar is true with the condition that for each three consecutive $Q_{i-1},Q_i,Q_{i+1}$ the disk $D$ they determine is cut by $F$.

6. What we can say is this: If $Q,Q'$ are two curves both at distance $\delta$ from $F$ then the curve $\frac{Q+Q'}{2}$ is at distance no more than $\delta$ and equality requires at least one value of $t$ such that $Q(t),Q'(t)$ are the same point and that point is at the maximum distance , $\delta$ from $F$. Furthermore, if $\delta$ is optimal then there must be at least one point at maximum distance from $F$ which is common to all $\delta$-good approximants (otherwise take enough of them and average).

7. More should be true (I'd guess) namely that the best approximation is unique and determined by the $M$ points mentioned before. (I'm not giving an algorithm to find $Q$, just a test to determine that you have it). If we have a curve $Q$ which achieves a distance $\delta$ but only at a few places (relative to the degree allowed), say $M'$ at $t_1,t_2,\cdots,t_{M'}$ then it should be possible to find $M'$ polynomial pairs of the appropriate degrees the $i$th of which is $(0,0)$ at all but one of these $t$ values except at $t_i$ it is not only non-zero, it is also not orthogonal to $P(t_i).$ If so then adding any small enough linear combination (with appropriate signs) of these to $Q(t)$ will decrease the distance at each of the maximally distant points and in some neighborhood of each without creating any new problems.