Searching for a point in space

[JoAuSc]

What area of mathematics would encompass the following problems? (Any comments you have on the problems would be welcome.)


1. Let's say you're trying to find a path (defined as some f(t) for t>=0) on the x-y plane (i.e. all (x,y) in R^2) that is close to every point on the plane, so that if you're trying to find a certain point, you can just start at t = 0 and increase t until the path crosses the point. (A computer would be used, so the parameter t would really be a series of points rather than a continuous variable.) The path should be one such that every point (x,y) is within a distance d of some point on the path. For a 2D plane, one solution would be to make the path start at d units from the origin and spiral outwards so that each revolution is ~2d units outwards from the previous one. (One example of this type of problem would be finding a lost child in the woods, although this algorithm would assume they didn't move while you searched for the child.)

2. Now imagine the space as a function space. How can one have a path through function space such that every function can be closely approximated by some point on this path? (I'm talking about everyday functions like f(x) = x^2 or a step function, not a delta function or something pathological like f(x) = 1 for rational x, 0 for irrational x.) We would define "closely approximate" by choosing a d such that |g(x)-f(x)| < d for all x in the domain. To make things simple, let the domain be all x in [a,b]. One idea I had was this:

Consider an arbitrary Fourier expansion with coefficients a_0 through a_n and b1 through b_n. As t goes to infinity, make the coefficients functions of t such that the following happens: First all coefficients are zero except for a_0, which starts at -q and increases through to +q in steps less than d. Once a_0 is equal to t, have a_0 jump down to -2q. While a_0 = -2q, increase a_1 from -q to +q as with a_0 in the previous step. After a_1 reaches +q, repeat with a_0 = -2q plus a step, and repeat the whole thing until a_0 reaches +2q. (This would be a loop within a loop. For each step of a_0, a_1 cycles from -q to q.) In this manner, we'd cycle through n nested loops for a_n (including b_n in there somehow). It seems reasonable that if f(x) is limited to x=[a,b], we would eventually reach some Fourier approximation g(x) that's close to f(x), though the nested loops would make this just about impossible to get a solution in a reasonable time. Does anyone know a better way to find an approximation to some arbitrary function by simply varying one parameter?

It didn't occur to me until after I thought of the problem that I was actually wrestling with the same problem whenever I had to mess around with my AC adapter cord for my laptop to get power to flow through it (it has a loose connection or something.) Just let h be a path in 3D space equal to the correct curve that my cord needs to be in, and let f(t) be the cord at time t as I wiggle it about, trying to find h. (I think about h as a function of a parameter s, where for each s, h is the position vector of a certain point on the cord. As s goes from start to finish, the cord is traced out. f(t) yields a path g(s) for each time t.) I wonder if there's an optimal f(t) that would allow me to find the correct cord position in a definite manner rather than just stumbling upon the solution.

 

[Crosson]

Does anyone know a better way to find an approximation to some arbitrary function by simply varying one parameter?

The only reason the mission succeeded for 2-space, is because instead of two space you choose to work with a discrete lattice. This is the difference between countable and uncountable. Every countable set is 1-dimensional in the sense that, because the set can be listed, you can trace out all the elements by a single parameter.

So the answer is: there is a way to do it if and only if you are working in a discrete approximation to function space.

 

[AKG]

What exactly do you mean by a "path"? Normally, a path in some space X is a function F : [0,1] -> X which is continuous. Continuity only makes sense if X is topological, but a space of "reasonable" functions can be given a natural topology. For example, the space of continuous functions on [a,b], denoted C([a,b]) has a metric p defined by p(f,g) = sup_a<x<b|f(x)-g(x)|, and this metric gives a topology. However, you don't seem to be placing any continuity requirements on your path, so we're just looking for a function F : [0,1] -> X such that for all f in X, there exists t in [0,1] such that p(F(t),f) < d.

Suppose we take X = C([a,b]). It turns out |X| = |[0,1]|, so there actually exists a bijection F : [0,1] -> X such that for all f in X, there exists t in [0,1] such that p(F(t),f) = 0. Now you want X to also include functions that may not be continuous, like the step function, but not so pathological like the characteristic function of the rationals. I suspect that the set X you're interested in will still satisfy |X| = |[0,1]|.

What if it doesn't? That's okay, we still might be able to do something. Suppose |X| > |[0,1]|, but suppose that X has a dense subset D such that |D| = |[0,1]| (D is dense in X means that for all d > 0 and for all f in X, there exists g in D such that p(f,g) < d). Then just let F be a bijection from [0,1] to D. With this choice, the function F satisfies:

For all d > 0, for all f in X, there exists t in [0,1] such that p(F(t),f) < d.

Note that this is stronger than the desired result, which you haven't asked to hold for all d > 0, but merely to hold for some fixed d > 0.

I know this doesn't answer some of your questions. For example, you want a "quick" way to approximate an arbitrary function. You'll have to clarify further what exactly you want though, before I could try to give a clear answer.