0
$\begingroup$

Suppose we have unit sphere in space $R^n$ which is inscribed sphere of a hypercube. Let we have epsilon-net on the facets of hypercube. For examle, in 3-D this epsilon-net is given as the set of points with coordinates:

$(-1,\hspace{2mm} -1+i*h,\hspace{2mm} -1+j*h)$

$(1,\hspace{2mm} -1+i*h,\hspace{2mm} -1+j*h)$

$(-1+i*h, \hspace{2mm} -1,\hspace{2mm} -1+j*h)$

$(-1+i*h, \hspace{2mm} 1,\hspace{2mm} -1+j*h)$

$(-1+i*h, \hspace{2mm} -1+j*h,\hspace{2mm} -1)$

$(-1+i*h, \hspace{2mm} -1+j*h,\hspace{2mm} 1)$

In R^n we form the set of points analogically.

Then we join every point from this set with the origin ( in 3-D - $(0,0,0)$) by straight line. This lines intersect with our unit sphere in some kind of points. So we have a set of points at sphere which ic called 'base of covering'.

It's need to find by analitycal way the radius of covering (or try to get up and low appreciations).

1 Answers 1

0

The sort of point you'll have most trouble covering will be at half distance between the projections of $(1,0,0,\dotsc,h,h)$ and $(1,h,h,\dotsc,0,0)$, where $\lfloor(n-1)/2\rfloor$ entries are $0$ in one vector and $h$ in the other and $\lceil(n-1)/2\rceil$ the other way around. The geodesic distance between those two points on the sphere is

$$\arccos\frac1{\sqrt{1+\lfloor(n-1)/2\rfloor h^2}\sqrt{1+\lceil(n-1)/2\rceil h^2}}\;,$$

and the covering radius is half of that. For odd $n$, this simplifies to

$$\arccos\frac1{1+(n-1)h^2/2}\;,$$

and for small $h$ this is approximately

$$\arccos\frac1{1+(n-1)h^2/2}\approx\arccos\left(1-(n-1)h^2/2\right)\approx\sqrt{n-1}h\;.$$

(Again the covering radius is half of that.)

  • 0
    Thks, this is my suggestion too. But I can't improve this for any dimension $n$. Can you help me?2012-05-15
  • 0
    @Sh.N.: I don't understand -- this is already for any dimension $n$; what is there to improve? Did you mean "prove"?2012-05-15
  • 0
    I want to say that this is only low appreciation of radius. For example, in 3-D the distance between projections of $(1, 0, 0)$ and $(1,h,h)$ less than the distance between projections of $(1, h, 0)$ and $(1,0, h)$. Besides that, the program which computes this radius automatically proves it.2012-05-16
  • 0
    @Sh.N.: I'm sorry, I thought I checked which of these has the greater distance, but I forgot to take into account that taking the arccosine reverses the order :-) I've corrected the answer.2012-05-16