Skip to main content
added 4094 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

As I understand it (I was wrong...), You have the unit ball $\mathbf{B}$ ( in $\mathbb{R}^n$) and a given $\epsilon$ and you want to find sets $A_1,\cdots,A_n$ so the corresponding $T$ and $\epsilon$ cover the ball in such a way as to minimize $\sigma=\sum|A_i|.$

LATER Actually you wish to cover only the surface of $\mathbf{B}$. I will explain at the end why the answer might be slightly different, but not by much at least for $n \gt 2.$ For now like me stick to my first understanding.

As long as $\epsilon$ is pretty small I think that $\sigma=n(t+1)$ for an ineger $$\sqrt{n}(\frac2{\epsilon}-1) \lt t \lt \sqrt{n}\frac2{\epsilon}$$ With all the $A_i$ identical sets of size $t+1$ made of equally spaced points (say with $\Delta$ between adjacent points) symmetric around $0.$.

I won't justify that equal size and equally spacing assumption but I will analyze it. It is easier to start with the points, see what $\epsilon$\epsilon $ should be to avoid uncovered places in the interior, find the best ball we can fit in, and then rescale to get a unit ball. SO I will treat the question as

For which pairs $(t,\epsilon)$ Is there a collection of $(t+1)^n$ points of the form $T$ such that the $(t+1)^n$ balls of radius $\epsilon$ cover $\mathbb{B}?$ I will further require that $\epsilon$ is minimal for $T$ and that no other $T$ with that many points allows a smaller $\epsilon.$

So consider an array $T$ of $(t+1)^n$ points making an $n$-cube $\mathbf{C}$ of side $t\Delta$ divided into $t^n$ smaller cubes of some side length $\Delta.$ To get to the center ifof each little cube we need to use little balls of radius $r=\frac{\Delta\sqrt{n}}{2}.$ Now the exact enclosed body is the cube $\mathbf{C}$ covered with small overlapping bumps of maximum height $r$ . That body would fit snugly in the slightly larger cube $\mathbf{C}'$ of side $t\Delta+2r=(t+\sqrt{n})\Delta.$ The largest ball which could fit in $\mathbf{C}$ would have radius $\frac{t\Delta}{2}$ and the largest which could fit in $\mathbf{C}'$ would have radius $\frac{(t+\sqrt{n})\Delta}{2}.$

For a particular $n$ one could find $t$ more exactly but I didn't try to figure out what happens as $n$ increases.

LATER

If you only want to cover the surface of $\mathbf{B}$ is the answer the same? The upper bound is still (as) valid. I will first argue that changing the lower bound to $\sqrt{n-1}(\frac2{\epsilon})$ makes it valid for this problem.I don't think that lower bound is sufficient and as $n$ grows the difference is not very big. Let me explain my reasoning using $n=3$ although it generalizes easily: Given 3 sets $A_1,A_2,A_3$ which work for the surface covering problem consider only $A_1 \times A_2$ and the cylinders of radius $\epsilon$ based on these points (axis in the $z$ direction.) Since the balls cover the surface, these cylinders cover the entire ball. In particular the intersections with the $xy$ plane are a bunch of disks of radius $\epsilon$ which completely cover the unit disk or radius $1.$ SO, this gives a lower bound on $t$ achieved by the solid problem one dimension down. This changes the estimates by a factor of $\sqrt{\frac{n-1}{n}} \approx 1-\frac{1}{2n}$

Here are a few pictures for $n=2$ using $t=15.$ Each is limited to a bit more than the first quadrant.

enter image description here

The one on the left uses the $15^2$ points $(\frac{i}{7},\frac{j}7)$ with $-7 \le i,j \le 7$and $\epsilon=\frac1{14}\approx 0.0714.$ This is almost the minimum $\epsilon$ with this many points to cover the $x$-axis and $y$-axis. (In fact for that particular goal we could uses the $15^2$ points $(\frac{2i}{15},\frac{2j}{15})$ and $\epsilon=\frac1{15}\approx 0.0667.$) But in either case there would be uncovered zones in the interior and along the boundary.

The middle picture keeps the same points but increases to $\epsilon=\frac{\sqrt{2}}{14} \approx 0.1010.$ Now there are no gaps. The point circled in red is $(\frac1{14},\frac{15}{14})$ and we see that the unit circle could be expanded to radius $\frac{\sqrt{226}}{14} \approx 1.0738$

That is actually the the picture on the right however we can imagine that it is still a picture of the unit circle but the points got pulled in toward the origin by a factor of $0.9313$ and the radius is $\frac{\sqrt{2}}{\sqrt{226}} \approx 0.0941.$

So what if I only cared about covering the circle and not the whole disk? At least in this picture I could not decrease $\epsilon$ at all lest the mentioned point just to the right of the top be uncovered.

However the first picture is more appropriate for covering the circle. We need to increase the radius but maybe not all the way to $0.094.$ There will be small uncovered areas inside but perhaps by shifting the sets $A$ we can manage to have all the gaps off the boundary. The last picture is an experiment using a radius of $0.9$ but only $13^2$ points instead of $15^2.$ The positions of the points was hand adjusted until I got bored. It does suggest that with $15^2$, or perhaps just $14^2$ points the boundary could be covered even with a slightly smaller $\epsilon.$ You can see that several points on the boundary just barely miss being uncovered. The point circled in green is ok but one would need to zoom in closer to confirm that. The empty pink area is relatively large and I don't see that one could shift to cover it without creating problems elsewhere. Certainly with two more horizontal and vertical rows we could get the four pink areas with lots of resulting overlap of little disks.
enter image description here

As I understand it, You have the unit ball $\mathbf{B}$ ( in $\mathbb{R}^n$) and a given $\epsilon$ and you want to find sets $A_1,\cdots,A_n$ so the corresponding $T$ and $\epsilon$ cover the ball in such a way as to minimize $\sigma=\sum|A_i|.$

As long as $\epsilon$ is pretty small I think that $\sigma=n(t+1)$ for an ineger $$\sqrt{n}(\frac2{\epsilon}-1) \lt t \lt \sqrt{n}\frac2{\epsilon}$$ With all the $A_i$ identical sets of size $t+1$ made of equally spaced points (say with $\Delta$ between adjacent points) symmetric around $0.$.

I won't justify that equal size and equally spacing assumption but I will analyze it. It is easier to start with the points, see what $\epsilon should be to avoid uncovered places in the interior, find the best ball we can fit in, and then rescale to get a unit ball.

So consider an array $T$ of $(t+1)^n$ points making an $n$-cube $\mathbf{C}$ of side $t\Delta$ divided into $t^n$ smaller cubes of some side length $\Delta.$ To get to the center if each little cube we need to use little balls of radius $r=\frac{\Delta\sqrt{n}}{2}.$ Now the exact enclosed body is the cube $\mathbf{C}$ covered with small overlapping bumps of maximum height $r$ . That body would fit snugly in the slightly larger cube $\mathbf{C}'$ of side $t\Delta+2r=(t+\sqrt{n})\Delta.$ The largest ball which could fit in $\mathbf{C}$ would have radius $\frac{t\Delta}{2}$ and the largest which could fit in $\mathbf{C}'$ would have radius $\frac{(t+\sqrt{n})\Delta}{2}.$

For a particular $n$ one could find $t$ more exactly but I didn't try to figure out what happens as $n$ increases.

As I understand it (I was wrong...), You have the unit ball $\mathbf{B}$ ( in $\mathbb{R}^n$) and a given $\epsilon$ and you want to find sets $A_1,\cdots,A_n$ so the corresponding $T$ and $\epsilon$ cover the ball in such a way as to minimize $\sigma=\sum|A_i|.$

LATER Actually you wish to cover only the surface of $\mathbf{B}$. I will explain at the end why the answer might be slightly different, but not by much at least for $n \gt 2.$ For now like me stick to my first understanding.

As long as $\epsilon$ is pretty small I think that $\sigma=n(t+1)$ for an ineger $$\sqrt{n}(\frac2{\epsilon}-1) \lt t \lt \sqrt{n}\frac2{\epsilon}$$ With all the $A_i$ identical sets of size $t+1$ made of equally spaced points (say with $\Delta$ between adjacent points) symmetric around $0.$

I won't justify that equal size and equally spacing assumption but I will analyze it. It is easier to start with the points, see what $\epsilon $ should be to avoid uncovered places in the interior, find the best ball we can fit in, and then rescale to get a unit ball. SO I will treat the question as

For which pairs $(t,\epsilon)$ Is there a collection of $(t+1)^n$ points of the form $T$ such that the $(t+1)^n$ balls of radius $\epsilon$ cover $\mathbb{B}?$ I will further require that $\epsilon$ is minimal for $T$ and that no other $T$ with that many points allows a smaller $\epsilon.$

So consider an array $T$ of $(t+1)^n$ points making an $n$-cube $\mathbf{C}$ of side $t\Delta$ divided into $t^n$ smaller cubes of some side length $\Delta.$ To get to the center of each little cube we need to use little balls of radius $r=\frac{\Delta\sqrt{n}}{2}.$ Now the exact enclosed body is the cube $\mathbf{C}$ covered with small overlapping bumps of maximum height $r$ . That body would fit snugly in the slightly larger cube $\mathbf{C}'$ of side $t\Delta+2r=(t+\sqrt{n})\Delta.$ The largest ball which could fit in $\mathbf{C}$ would have radius $\frac{t\Delta}{2}$ and the largest which could fit in $\mathbf{C}'$ would have radius $\frac{(t+\sqrt{n})\Delta}{2}.$

For a particular $n$ one could find $t$ more exactly but I didn't try to figure out what happens as $n$ increases.

LATER

If you only want to cover the surface of $\mathbf{B}$ is the answer the same? The upper bound is still (as) valid. I will first argue that changing the lower bound to $\sqrt{n-1}(\frac2{\epsilon})$ makes it valid for this problem.I don't think that lower bound is sufficient and as $n$ grows the difference is not very big. Let me explain my reasoning using $n=3$ although it generalizes easily: Given 3 sets $A_1,A_2,A_3$ which work for the surface covering problem consider only $A_1 \times A_2$ and the cylinders of radius $\epsilon$ based on these points (axis in the $z$ direction.) Since the balls cover the surface, these cylinders cover the entire ball. In particular the intersections with the $xy$ plane are a bunch of disks of radius $\epsilon$ which completely cover the unit disk or radius $1.$ SO, this gives a lower bound on $t$ achieved by the solid problem one dimension down. This changes the estimates by a factor of $\sqrt{\frac{n-1}{n}} \approx 1-\frac{1}{2n}$

Here are a few pictures for $n=2$ using $t=15.$ Each is limited to a bit more than the first quadrant.

enter image description here

The one on the left uses the $15^2$ points $(\frac{i}{7},\frac{j}7)$ with $-7 \le i,j \le 7$and $\epsilon=\frac1{14}\approx 0.0714.$ This is almost the minimum $\epsilon$ with this many points to cover the $x$-axis and $y$-axis. (In fact for that particular goal we could uses the $15^2$ points $(\frac{2i}{15},\frac{2j}{15})$ and $\epsilon=\frac1{15}\approx 0.0667.$) But in either case there would be uncovered zones in the interior and along the boundary.

The middle picture keeps the same points but increases to $\epsilon=\frac{\sqrt{2}}{14} \approx 0.1010.$ Now there are no gaps. The point circled in red is $(\frac1{14},\frac{15}{14})$ and we see that the unit circle could be expanded to radius $\frac{\sqrt{226}}{14} \approx 1.0738$

That is actually the the picture on the right however we can imagine that it is still a picture of the unit circle but the points got pulled in toward the origin by a factor of $0.9313$ and the radius is $\frac{\sqrt{2}}{\sqrt{226}} \approx 0.0941.$

So what if I only cared about covering the circle and not the whole disk? At least in this picture I could not decrease $\epsilon$ at all lest the mentioned point just to the right of the top be uncovered.

However the first picture is more appropriate for covering the circle. We need to increase the radius but maybe not all the way to $0.094.$ There will be small uncovered areas inside but perhaps by shifting the sets $A$ we can manage to have all the gaps off the boundary. The last picture is an experiment using a radius of $0.9$ but only $13^2$ points instead of $15^2.$ The positions of the points was hand adjusted until I got bored. It does suggest that with $15^2$, or perhaps just $14^2$ points the boundary could be covered even with a slightly smaller $\epsilon.$ You can see that several points on the boundary just barely miss being uncovered. The point circled in green is ok but one would need to zoom in closer to confirm that. The empty pink area is relatively large and I don't see that one could shift to cover it without creating problems elsewhere. Certainly with two more horizontal and vertical rows we could get the four pink areas with lots of resulting overlap of little disks.
enter image description here

Post Undeleted by Aaron Meyerowitz
added 1872 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

IfAs I understand the question correctlyit, You have the unit ball $\mathbf{B}$ ( in $\mathbb{R}^n$) and a given $\epsilon$ and you want to find sets $A_1,\cdots,A_n$ so the corresponding $T$ and $\epsilon$ cover the ball in such a way as to minimize $\sigma=\sum|A_i|.$

As long as $\epsilon$ is pretty small I think that $\sigma=n(t+1)$ for an ineger $$\sqrt{n}(\frac2{\epsilon}-1) \lt t \lt \sqrt{n}\frac2{\epsilon}$$ With all the $A_i$ identical sets of size $t+1$ made of equally spaced points (say with $\Delta$ between adjacent points) symmetric around $0.$.

I won't justify that equal size and equally spacing assumption but I will analyze it. It is easier to start with the points, see what $\epsilon should be to avoid uncovered places in the interior, find the best ball we can fit in, and then rescale to get a good ideaunit ball.

So consider an array $T$ of $(t+1)^n$ points making an $n$-cube $\mathbf{C}$ of side $t\Delta$ divided into $t^n$ smaller cubes of some side length $\Delta.$ To get to the situation from thinking aboutcenter if each little cube we need to use little balls of radius $n=1,2.$$r=\frac{\Delta\sqrt{n}}{2}.$ Now the exact enclosed body is the cube $\mathbf{C}$ covered with small overlapping bumps of maximum height $r$ . That body would fit snugly in the slightly larger cube $\mathbf{C}'$ of side $t\Delta+2r=(t+\sqrt{n})\Delta.$ The largest ball which could fit in $\mathbf{C}$ would have radius $\frac{t\Delta}{2}$ and the largest which could fit in $\mathbf{C}'$ would have radius $\frac{(t+\sqrt{n})\Delta}{2}.$

For that ball to be the unit ball we would need (for $\mathbf{C}$) to have $\frac{t\Delta}{2}=2.$ Meaning that $\Delta=\frac4t$ and this would require $\epsilon=\frac{\Delta\sqrt{n}}{2}=\frac{2\sqrt{n}}t$ leading to $t=\sqrt{n}\frac2{\epsilon}.$ This is an upper bound. The same analysis for $\mathbf{C'}$ gives a lower bound of $t=\sqrt{n}(\frac2{\epsilon}-1).$

For a particular $n$ one could find $t$ more exactly but I didn't try to figure out what happens as $n$ increases.

If I understand the question correctly, you can get a good idea of the situation from thinking about $n=1,2.$

As I understand it, You have the unit ball $\mathbf{B}$ ( in $\mathbb{R}^n$) and a given $\epsilon$ and you want to find sets $A_1,\cdots,A_n$ so the corresponding $T$ and $\epsilon$ cover the ball in such a way as to minimize $\sigma=\sum|A_i|.$

As long as $\epsilon$ is pretty small I think that $\sigma=n(t+1)$ for an ineger $$\sqrt{n}(\frac2{\epsilon}-1) \lt t \lt \sqrt{n}\frac2{\epsilon}$$ With all the $A_i$ identical sets of size $t+1$ made of equally spaced points (say with $\Delta$ between adjacent points) symmetric around $0.$.

I won't justify that equal size and equally spacing assumption but I will analyze it. It is easier to start with the points, see what $\epsilon should be to avoid uncovered places in the interior, find the best ball we can fit in, and then rescale to get a unit ball.

So consider an array $T$ of $(t+1)^n$ points making an $n$-cube $\mathbf{C}$ of side $t\Delta$ divided into $t^n$ smaller cubes of some side length $\Delta.$ To get to the center if each little cube we need to use little balls of radius $r=\frac{\Delta\sqrt{n}}{2}.$ Now the exact enclosed body is the cube $\mathbf{C}$ covered with small overlapping bumps of maximum height $r$ . That body would fit snugly in the slightly larger cube $\mathbf{C}'$ of side $t\Delta+2r=(t+\sqrt{n})\Delta.$ The largest ball which could fit in $\mathbf{C}$ would have radius $\frac{t\Delta}{2}$ and the largest which could fit in $\mathbf{C}'$ would have radius $\frac{(t+\sqrt{n})\Delta}{2}.$

For that ball to be the unit ball we would need (for $\mathbf{C}$) to have $\frac{t\Delta}{2}=2.$ Meaning that $\Delta=\frac4t$ and this would require $\epsilon=\frac{\Delta\sqrt{n}}{2}=\frac{2\sqrt{n}}t$ leading to $t=\sqrt{n}\frac2{\epsilon}.$ This is an upper bound. The same analysis for $\mathbf{C'}$ gives a lower bound of $t=\sqrt{n}(\frac2{\epsilon}-1).$

For a particular $n$ one could find $t$ more exactly but I didn't try to figure out what happens as $n$ increases.

Post Deleted by Aaron Meyerowitz
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

If I understand the question correctly, you can get a good idea of the situation from thinking about $n=1,2.$