Theorem 1. For every and every there exists a Lipschitz retraction .
Compared to previous posts, I changed notation to improve readability: now stands for the set of all nonempty subsets of with at most elements. The metric on is the Hausdorff metric . The map was defined in Collisions II as follows:
Given a set , enumerate its elements and consider the initial-value problem
Define where be the time of the first collision between particles in this system. Also define when .
for all . Interestingly, the Lipschitz constant does not depend on the dimension of ambient space. (Well, I’m not so sure it has to depend on cardinality either.)
It is easy to check that the function is -Lipschitz on .
Let . If , then (2) already gives (1). From now on assume , hence . The geometric meaning of these inequalities is that the points of are spread out in space, yet each of them is close to a point of . Therefore, we can enumerate them and in such a way that for all .
Let and be the solutions of our ODE with initial data and , respectively. Here comes a monotonicity lemma.
Lemma 2. is nonincreasing with time .
Proof: Encode the sequence by a single point . This point is moved by the gradient flow of the convex function . Since the gradient of a convex function is monotone, we have . It follows that is nonincreasing.
By Lemma 2, holds for all until a collision occurs in either system. We may assume that -particles collide first. Then, at the time of their collision they form the set while the -particles form some set , with . Since has fewer than elements, . From (2) we obtain . Note that because our ODE system is autonomous. The final estimate is , which is (1).
Here is how a 20-point set gets retracted onto :
The plot was produced by a version of the familiar Scilab routine, modified to stop the computation at first collision. It was called with
function gravity3(vx,vy,Nsteps) Npoints = length(vx); h = 0.01/Npoints; tolerance = h*(Npoints-1)/3; collided = 0; x = zeros(Nsteps,Npoints); y = zeros(Nsteps,Npoints); x(1,:) = vx; y(1,:) = vy; m = 1; while (m<Nsteps & collided==0) do x(m+1,:)= x(m,:); y(m+1,:)= y(m,:); for i = 1:Npoints for j = (i+1):Npoints v = [x(m,j),y(m,j)]-[x(m,i),y(m,i)]; if norm(v) < tolerance then collided=1; else x(m+1,i) = x(m+1,i) + h*v(1)/norm(v); x(m+1,j) = x(m+1,j) - h*v(1)/norm(v); y(m+1,i) = y(m+1,i) + h*v(2)/norm(v); y(m+1,j) = y(m+1,j) - h*v(2)/norm(v); end end end m = m+1; end clf(); plot(x(:,:),y(:,:),'o'); endfunction