On Monday 06 November 2006 22:12, Victor S. Miller wrote:
Now use the fact that (1-2/n)^n is approximately e^-2. You find that in no more than n (log 4n)/2 steps that the radius (i.e the largest of the |v_i|) is at least halved. Note that this doesn't make any use of the fact that the points are in the plane. Mackay, in his post also mentions an "obvious lower bound" of c n for some c (but, it's not so obvious to me -- perhaps someone can enlighten me).
Let's suppose we begin with the vertices of a regular 6n-gon inscribed in the half-unit circle. Divide them into 6 contiguous blocks of size n. Suppose that at each stage we take two points and just throw them away (which of course reduces the diameter at least as effectively as replacing them with the midpoint). After we've removed 3n points (no matter how), at least three of the blocks are still represented, therefore at least two noncontiguous blocks are still represented, therefore two points remain at distance at least 1/2. So it takes at least 3n/2 steps to get the diameter down below 1/2. -- g