Timeline for Matrix approximation
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2010 at 16:51 | comment | added | Danu | I found the following paper. Hausdorff Approximation of 3D Convex Polytopes, Lopez and Reisner. citeseerx.ist.psu.edu/viewdoc/… Among other things, it shows that for any polytope Q there is a polytope P of k vertices, whose vertices are also vertices of Q, such that the Hausdorff distance is bounded by $c(m) R/k^{2/(m-1)}$ where R is the minimal radius of a ball containing P. (In our case, $R\leq 1$.) So I think this implies that we can bound $\epsilon$ by (roughly) $R/k^{2/(m-1)}$ which makes the bound tight! | |
| Mar 31, 2010 at 15:46 | comment | added | Sergei Ivanov | No, you generally cannot find an $\epsilon$-net that small. But the subset does not have to be an $\epsilon$-net. On the sphere, being a $\sqrt\epsilon$-net is sufficient, and I believe there is something similar on any convex surface. | |
| Mar 31, 2010 at 15:00 | comment | added | Danu | Thank you for clarification. Now I understand the whole argument. So I guess if one can show that the size of $\epsilon$-net is (roughly) $(1+2/\epsilon)^{(m-1)/2}$ instead of $(1+2/\epsilon)^{m-1}$ then one can show the upper bound $k^{-2/(m-1)}$ which matches the lower bound? (Note: I ignore the constants.) Is this possible? | |
| Mar 31, 2010 at 10:10 | history | edited | Sergei Ivanov | CC BY-SA 2.5 |
added details about convex geometry
|
| Mar 31, 2010 at 9:53 | vote | accept | Danu | ||
| Mar 31, 2010 at 9:04 | comment | added | Sergei Ivanov | Yes $C(m)$ and $c(m)$ are constants depending on $m$ that I did not bother to compute. The proof assumes some background in convex geometry. I'll add some explanations so you can dig it out. | |
| Mar 31, 2010 at 4:30 | comment | added | Yemon Choi | Just regarding Q2: typing "Fritz John theorem" turns up plenty of results. That theorem is a well-established part of convex geometry. It might help your question to get fuller answers if you say something about your mathematical background/experience, so that they don't talk past you or vice versa | |
| Mar 31, 2010 at 4:16 | comment | added | Danu | Thank you for you answer! Quick questions for now: 1. What is $c(m)$ and $C(m)$? Are they some constants that depend on $m$? 2. Could you recommend a place where I can find out more about Fritz John's theorem? The argument seems to be correct to me but I will have to digest and work out some parts more before asking you some questions. (I don't know anything about $\epsilon/\sqrt m$ net and what the "standard packing argument" actually is.) Hope you don't mind answering some questions after that. Thank you! | |
| Mar 31, 2010 at 4:05 | vote | accept | Danu | ||
| Mar 31, 2010 at 9:52 | |||||
| Mar 30, 2010 at 20:49 | history | answered | Sergei Ivanov | CC BY-SA 2.5 |