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
    @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