[00:00:05]
>> Told you last time of the. Floating body algorithm and I told you basically how the idea goes and let me write down now the precise formulation of the theorem that we'll get with these of floating body algorithms so that's a theorem due to cost. And since the following.
[00:00:32]
So for all Delta. Smaller equal then the volume of k. divided by for you to do for so it's even precise constants varies. In n.. Such that. In is more equal than. The. $2.00 to $16.00 and. Then comes the volume of the difference of k. and the floating body k. Delta and real divide by Delta.
[00:01:16]
Times the volume of the you pleading unit or so there is in. That of that size. And there is. A polytope. P. n.. With at most and. They'd sit between k. delta time k. So we are here in Delta is contained in p. and is contained in k. and I was indicating a little bit last time on how this goes.
[00:02:00]
With the floating body I believe that we have this continuum. And. That it is really $2.00 and $2.00. Difference and now we have the precise constants so what I want to do now is I want to show. This relation can be you. Basic can be described as more precisely so in a sense here in bees and.
[00:02:34]
Claymation of the given corn export u.k. and now we want to kind of determine how to measure in the symmetric difference metric that's what we want to do so as I said I want to. Show you how from these. We can get. That approximation off with such a pollutant that most go to say yes and no we want to kind of measure how good these are books emission and I actually want to measuring the symmetry difference maker so let's assume.
[00:03:10]
So to do that I'll not so Hubie took a general Connex body. But now we assume that. Ok you see 2 plus. Because otherwise some things don't make sense so you're soon Casey 2 plus and then we recall right away these 1st theory that we finished showing last time which said that that they did meet.
[00:03:40]
Her goes to 0 of the boardroom difference of k. and it's floating body divided by Delta to the tool in plus one is equal to some constancy and which we know exactly time c.f. and surface area of k.. So that means for our. Small enough. We have the king without k. Delta this boy Hume difference devalued by Delta to the tool plus one behaves like c. n. times defined so if you say area of k. and for there I need to see 2 plus so that I have something that's not 0 in the right insight because I could potentially if I don't have c. 2 plus I could potentially have a party took which I don't want to know so I don't want these to be 0 on the right hand side so we have.
[00:04:36]
So don't are small enough given this relation holds so now we go to all Syrian So by these by this theory and here we know there exists so by all theory that doesn't work. By a buff theory. So by. Above. We know there exists n. Ricci's of the order and it's right $6.00 to $16.00.
[00:05:15]
E to the 16 n. volume difference came without k. doubt. Divided by volume of the 3 din unit ball and a party top. End. With a most and which is east side that protein bodysuits in the poll you took seats in the body so now as I said we want to compute the how the vote in the symmetry difference metric this polytope approximates case so here I am writing this imagery difference metric and I want to get these folks summation these in the dependence of the number of all.
[00:06:00]
Of those would be the word to seize all points chosen in one to this dependence and u. turns out that they will be the right power so that smaller e. will be course in seats between k. Delta and k. So this is smaller equal than came without Ok Delta volume of divided by now alone its right to the minus 2 will bring minus one and this is smaller equal now of use that the end of this order of magnitude Sylvio get k. beat out k. Delta and then comes he 16 and caveat out Kate Delta.
[00:06:41]
Boy you divided by Delta volume of the Euclidean you need everybody to the power to over and minus $10.00 so so now let's look at what we get so this is equal to cave without k. Delta volume difference and then. What I want to do is I are going to.
[00:07:06]
So here I have Dota 2 the power to over in line is one which I want to bring together with this one human difference and I write things like so. Very No Be course. Any So ordering the mind sees on the bottom so basically that the end is on top.
[00:07:27]
So I radiate like so and then you see all the ahead and plus one over in minus. So far and then comes easy to the $32.00 and over in minus one and. And then while I'm having we're having the volume of Euclidean unit ball race to the power to overturn minus one but you keep doing you need all rays to use power of the older one over in so real good effect to end in here.
[00:08:09]
Now. So we have these so be ahead that this is off the order a constant so I'm just writing a question for the expression times n. and then we'll have their guy here which we see from over there so that is of the order. C n f and surface area of came through the power in plus one over in minus one and that's what you get.
[00:08:39]
So b. c.. So so let's make it up more on. Let's think about it there need be more we know that this c n is one half in plus one over in minus one dimensional on you pleading you need Ball Boy are you in that race to the pole with 2 over in plus one so all so if you look at what we get from this c.n..
[00:09:06]
It actually shows us that the power of in comes in Soviet constant so that constant another power of that comes in so we get in square f. and surface area of King to the end plus one over and minus one. That but. And so b. c. that it's the f. and surface area that comes in in this approximation result so we showed that this polytope read this.
[00:09:39]
Approximates the k. in the symmetric difference metric. And that the dependence on the number of words you see comes in like so the dependence on the body comes in via the f. and surface and here we are half the dependence on the dimension and the question is of course because that only an upper bound question of course is how good is the system it and that's what you want to explore a little bit next is also in the context of random point.
[00:10:19]
Sure. I said but I'm 53. So polytope. Next. Off I even randomly chosen points in. With respect to the mission. Yeah it's. Like you think. Yes I am I Ok. Here Yeah there should be a constant so yeah yeah you feel sorry for us and yeah that's of course not the same quantity.
[00:11:28]
Year we have here of Post article also a concern because I stated the volume of you keeping you and your booking. In Quincy. So you like. Actually see that this is anyhow not even the optimal dependence on the convention so we don't really at that level we don't really care about the value of the concert really do care of all you've made by actually not even your dependence on if you mention real.
[00:12:01]
I don't care about the uphill considering that so I mean up to absolute good thing that. Ok so so we're looking at random quality told to so points let's give the names. Most of the time will call them x. one up to take care people and and then we'll get the random party talk which I don't most of the time you know like so p n So you're just a car next Hall of these randomly chosen point x. one up to x. And no the typical measures in that context the one you use so what are the polar bt measures that don't use these so for instance one could use the normalized.
[00:12:52]
As we want to do you agree that approximation of convex borders would be a use is known lies in the best measure. So Lenda in its new big measure normalised over a carton explored the where we're going to choose the points from so that's one option if we do these then if we choose the points like so and take the K'nex home then the potential disadvantage is that we have raised the points not every point that was pink becomes a word Ted maybe a wasteful so a better choice would be.
[00:13:30]
Choosing. Points so normalized that big measure and choosing points insight. Pay choosing points. On the boundary of k. say with a normalized surface area measure and then the picture becomes like so so we'll choose the points here and then we do not waste anybody everybody shows and becomes of wood pics of the pointy toe and then our other situations where one even can put points obvious rarity position and that has also been done and in each of these instances one measures how would be a book summation is in this ng that you difference matric and that brings me to on to these approximation questions they are all of course.
[00:14:30]
Many other metrics they can and have been used in various a whole ocean which amount of literature on this topic so. From now on view of basically concentrate on the 2nd part b 2 is the point on the boundary of k. and let me make more specific how exactly we want to look at these situations so this set up is choose.
[00:14:58]
X 12 x. and on the boundary of a can explore dk with respect to p f I call it the on. Usual So physicians measure that we always do don't like still of any real he did b. the probability density. So if. Positive on the boundary of he continues and a probability density and then.
[00:15:31]
And then as we once know to look at our whole range of party talk we want to approximate with this random polytope our given context buggy k. and we want to measure how good their proxy mation is in the symmetric difference metric in order to know that we have to know what's the expected value most like $2.42 so I'll do you know that I always like so expect to bore you Ok the expected value of choosing n. points on the boundary of came with respect to the school of view to measure p. f. that's nothing else but the end fall into go over the boundary Ok so here we'll take this end times and we have chosen our points x. one optics computer and and we'll take the volume of these intros and points and the points chosen with respect to these ball between measure.
[00:16:28]
P f So that is the expected value and then. And then we'll have a theory. That due to cost and myself. In this form that I'm going to present it there were other worsens. Under more restrictive assumptions. Due to one ts I it's not. But I'm going to mention the way we have proved it so under some regularity assumptions of the boundary of Katie.
[00:17:06]
Those So suppose there exists. Are that strictly positive and the care people are they speak with a little r. o.. More than infinity such that for all x. in the Bondi of cave we'll have a nice containment relation or for the small ball and containing relation for the larger bore well what do I mean we'll have a the ball centered it x. minus autonomic in x. and such autonomic see if you need be almost everybody on the boundary as I have showed last time so called be almost everywhere would be enough.
[00:17:57]
With this radius that's contained in k. and that is contained in the ball the big ball. So that's the regularity condition so I have a boundary point here then I have the small ball so that's my only point and the small ball with the radius little r. and I have this big ball with a radius capital r. that made the center tear and the body is some.
[00:18:27]
Where in between longer. The body somewhere in between so if we have these then. If we have these rather mild regularity assumption on the boundary they did meet and scapula and goes to infinity the volume of k. minus the expected going. Off Random point you talk where we have chosen the points on the boundary of cave with respect to the pole ability measure and be divided into the line a stool in the next one so the dependence on the number of points chosen is the same that we have gotten here so that's good so we have the same dependence on the number of points chosen as a result that was given to us by the floating body of them so this limit exists and is equal to a constant I call the d. and we know exactly what the quantities are going to.
[00:19:22]
Bother to write it down it's basic There you scum a function that there and then we'll have the interval over the boundary of k. and view it goes to the whole of one over in minus one over to the pole tool ring minus one and as usual with respect to the surface area mission.
[00:19:45]
I cannot say anything about the proof of this theory trust the proof of this theory is more than 200 pages long so it took us quite a while but I can mention one in 3 d. and they used for the proof so all. Amazing increase of one ingredient.
[00:20:06]
Used in the proving is a variant of the floating point. Namely something that be called Surface body. You know did it maybe like so if it's related to the function and if so let's put it up there and that's the parameter 3rd of. Of is what so like before let me draw a picture so you have Ok here and like before you look at type of planes 8 but no not type of planes they're cut of war you Delta type of planes cut off fixed surface area s. And actually if I use the function here then it's the surface area of weight with the function so it's the into these type of plane gives us to have spaces h. minus and h. plus so we intersect over all x. plus the into h. minus intersected with the boundary of pain.
[00:21:24]
Do you Ok it's more equal than Ace So that's one ingredient that you use and one can show again such a phenomenon. That this point you told them they'd be find. Is of course contained in k. but it's nice nice between. Know the body can. Serve his body with parameter roughly.
[00:21:58]
S. equals one over in so again such a phenomena that this approximating party talk gets greased in between a geometric object namely in this case the surface body in the board ek. The other thing that I want to mention is that here we are still rather general because we all have a general function f. that is.
[00:22:27]
Given to us as a poor ability density and. Of course a good thing would be. To detour mean rich f. we should use so that the right hand side becomes meaningless. So natural question is what makes the right times I mean evil that is for which f. for which probability density is to recruit the best.
[00:22:57]
And perhaps invasion so the x.. Right hand side becomes minimal right hand side I mean the right hand side this expression here becomes minimal. Minimal. For equals which are used to the car in plus one and then you have to normalize and so on we know that that is the expression that comes in when we look at defined surface area so it's defined surface area with which we have to normalize right so.
[00:23:35]
Because that's the intercultural recall this is the f. and surface area was the into a call over the coast coverture or generalized Gulf Coast neutral to be more precise over the boundary of k d n u. And it makes sense that that should give us the optimal right hand side course if so basically what we do if we put this f. we'll choose the points according to court which are right and that's really what we should do where we have more curvature is where the bodies local to get the same good at procreation in this imagery difference metric we should put more points more in the pot with a lead we should not waste any points to get the same good at the commission that's the increase in behind this so if we put this if then right hand side becomes.
[00:24:32]
What to do so we'll just put you in it's not hard to see that. Various but. Will come out on the right hand side is again the f. and surface area to the end plus one over in minus one so the same dependance that be going to hear from the dependence on the body because here bring we were using the floating boogie woogie So question and I only said what happens what's the order of magnitude of these constant the end being know what's the order of magnitude so.
[00:25:07]
Basically the order and so on we'll actually so this isn't as intended result not only well it's not like over there where we only had upper estimate we these and its entirety results along it's equal here and the d n a is actually trust of the order in and not like what we had here of the order in squared.
[00:25:33]
And another thing that bugged wants to do in this context is compare these random at book summation to best at books Imation which quickly. Because that's surprising. So that was done by Google. So it's a theorem that and mention that due to poor brain dimension and degree with and 3 and by McClure and Vitale.
[00:26:06]
In dimension and equals 2 and it says that if. You see 2 plus. Then. We look at this same thing so we'll look at k y m difference minus random another random. Meeting party took so I like Ok based this on so that's the best at booking meeting quality top with most and which is the speed look at the scene inside we look at the scene made tree difference metric the difference of the volumes and same dependence on any number of words this is and goes to infinity capital and goes to infinity it's like one how there are in minus one so for historical reasons the pendant of the dimension is.
[00:27:00]
Introduced with these. Planes leaving these one half in minus money simply for historical reasons that this constant is called in minus $1.00 it's related to do it in a tree and relations and what comes is also a fine so if you say to the power in plus one over in minus one and.
[00:27:24]
And the thing is that at the time when. Mature and we tell you when they prove this theory nothing was known of all the order of magnitude of this constant here so so to speak the dependence on Dimension was hidden in this constant and it was only later much later by monkey and should the order of magnitude of this constant was determined and it's actually on the order.
[00:27:56]
And. So order of which we had also appear when we were choosing the right probability density in our rendering result and then we can compare the random results with this best African nation result and we'll see thanks. Still in mind of course smaller than this we have in the range of result after all that's based at books Imation but not by much so the $100.00.
[00:28:28]
And minus one and then comes one plus. And over again so it gets better as the dimension increases and mission I'd like to from what I did this week is almost as good as space books and so what we want to retain from these. Here. Hard on of.
[00:28:56]
Proclamation results. When the body uses so then when. Choosing points. On deep on the boundary of a corner explored and Key is regular sufficiently regular. In the sense of these theorem here for instance or see 2 plus then their dependence. On the number of points chosen. Comes in into the minus tool when minus one and the dependence on the body.
[00:29:44]
Comes in my of the f. and surface area so that maybe but we want to retain from these considerations. So far. No let's move to. A different set up where we know not to still point on the boundary of the regular sufficiently regular body I've learned the points on the boundary or insights.
[00:30:19]
Into the a ponytail itself. I know this means. Spank. So you know. The points can you tell him points. Inside. A ponytail. And that had been done. And a lot has been done there are on the boundary. Of p. and that has not been done and had not been looked at before so.
[00:31:46]
So then what are the typical questions. I think one asks invent setting. Well typically questions are What is the expected number so again if we choose these care people in points. They get you know again by. Then to question is what is. Expected number of words of such a random polytope that Taim so that I would you know I f. 0 p. and will be the number of words on more generally of course try did it didn't but I'm going to see.
[00:32:38]
The number of points to either inside or on the boundary like before. Yeah. So like. Here is your point you talk. To people and points inside. Yes. Yeah you do get to the boundary We'll get to that one now. So. But nevertheless in both situations one can i was called the expected number of on one general for the expected number of l. dimensional so I said the expected number of.
[00:33:24]
Dimensional faces. And and of course also as always for the expected for you. So let me just write. The thank you we can all split the expected going with such arrangement but it still uses what and I are one to force some results concerning the inside situation. And.
[00:33:52]
Of course. The expected to. Give us again if we look at the volume difference with the original given give us again. Broke summation way to measure how would be the air book summation like increases this will give a broken amazement of the original polytope and if you look at the difference between the volume of the original and the expected volume we are measure again in the symmetric difference metric how good these African nations.
[00:34:27]
So what does one know in the. In the situation where be chilled to the point so if we choose the points inside we choose them with respect to normalized of big measure we will choose these and points capital and points and then so. We respect to. These probability measure really choose x. 12 x. and in p. and b. look at the only think and its Instapundit.
[00:35:02]
Of the skeptical and children points and then there is a result I saw on e. and. Which says that the volume difference seemed minus expected volume on the ring and when you told it behaves like it is and is large. And goes to infinity behaves like how it behaves like the number of flakes.
[00:35:34]
Of p. and I had said that do you say also denoted by t o p cardinality of to you p. the towers flake or towel is. The same expression owes the same quantity Sometimes it's called towers Sometimes it's called legs and then you have in over n. and located in gets raised to the power in minus one.
[00:36:00]
And in the. N. plus one it would be in minus one and in minus one. For Tori So that's what you gave and. Kees compare that to still compare these to a result that I mentioned earlier namely. To result of cost. Which said something about the. Difference between.
[00:36:38]
The volume difference between. Party top and it's floating on the top and that 1st behaving and stuff goes to 0 except to be in the same way a similar way so we also got the number of flakes of p. in then real gods so n. was replaced by replaced by one over Delta so we would go Delta l. and one over Delta to the inline this one so.
[00:37:08]
Anterior by dividing by in Victoria into the in minus one so it's a similar behavior. Corresponds to one over in and basically this is again due to the fact that this of. Random quality that we get here is a screen between the floating body and the quality. So there is the result for that one to 2 years the expected value in the inside case no Also these results about the expected number of dimensional of 1st faces so that.
[00:38:01]
They behave like how still again as in Ghost and if you or it is large behave like some constant d. and l. So you depends on in the dimension on dimensionality of the of the face sets their faces their rituals and then comes. Again. The number of flicks of the part you told in.
[00:38:28]
The log in to the end minus one. I should leave this. So would be $12.00 or maybe already at that point and note there when we choose so that was one thing when we choose. In cake. Piece of polytope. Then. The dependence on n t and. That is the points chosen.
[00:39:10]
Is. Long in. Here so it's long in comes in and the old in comes in here let me just mention. Log in to the in line us one or log in. To the in line this one over in. The point I want to make you stay local factors come in and their dependence on the body.
[00:39:44]
Of the public that itself comes in as. The number of likes of tea so that's a good indication that maybe you can get it corresponding to. The Case For put it towards might be the number of flakes. Now when one chooses the points inside of polytope key like so this is has a drawback so drawback.
[00:40:15]
When points are chosen. To listen inside the. Can So what's the drawback there p n. Is simply show. With probability one. And that is really a drawback because for education one necessarily needs to deal with Party types that not simply in particular when one wants to use them for like.
[00:40:54]
Trick I would go reasons or for all. Of 2 zation problems and whatnot so for education one wants to get away from this simplicial So that's why I really look at the next case which is when we choose the points on the boundary of the party so they become of course simply should be course mention that we have chosen x one of 2 x. needle in a fundie independent to.
[00:41:26]
X. one upticks region and points are chosen then you look at the f. and how of these A's say it's the f. 100. Of these low points chosen. Then like here on my points x. one x. 2 x. and believing these and find 8 and then we want to choose our next these f. and how it's n. minus one dimensional but we will choose with respect to the full.
[00:41:59]
Measure on our end so that means that p. probability that the next point. Is in a is 0 because you choose the points then we choose there in fact with respect to that measure so we want to get away from the situation that this party of top that of the approximate with simplicial So that's why we choose the points on the boundary.
[00:42:30]
On the boundary of a poor utopia. With respect to the normalized Sophy's area measure just because it's a poorly thought of idea as in minus one dimensional your very nature normalized so just write it like so and then be a good party Topes. Not necessarily simply say. Ok.
[00:43:05]
Right. Where to spend one to say. Yes. And so sometimes. In some of the things that I'm going to mention. We will need. Very. Nice. Unlike most general that they can imagine. So if for some results we need to talk to be simple so a. Team but you simple.
[00:43:49]
Each would take. Their all. In face it's that need it. Thank me there it is there can. I never know it's always seems like a wrong sentence. When I write. I never know if Should there be there. Or. Yes but I never know you know a sentence there shouldn't be there or not so but you guys know what I mean so here is a word takes so for instance the simple so this work takes me there and 1st it's meat and for instance this thing here is not.
[00:44:43]
It's not simple right so. Yes no. Ok so that real need. It's on for some of the results so then real what do we do so we'll have our partner told here and then really pick on the boundary peak but. I think we're just says we'll take the comics home and we'll get a good point you told and Ok we'll get it so here we have a chance to get facets that are not simple yet.
[00:45:25]
Real good fences that I'd like to research but then we'll get of course also all of those. I said mate of all these 2 adjacent faces or in 3 adjacent pheasants and so on I think that the party took all that. Approximating. And let me write down. 1st theory which.
[00:46:00]
Says something about the expected number of. These of such a party talk and the expected number of facets of such a point 0. 00. 0 have to mean. What about my 5 minutes. Or so then. I'm rushing so and. Mostly I said sure that I'll give credit to my cool authors so that 1st joint work with costume my Ts and myself so for the 1st theory since something along the expected number of.
[00:47:07]
This behaves like a constant in this one we know basically So let's see in zeros did this pretty much know how it looks like comes in again the. Number of flakes of p. and then in to the in line is to. 0 Ok let me write like so so that the 1st one.
[00:47:37]
3rd one the 2nd one we expected number so if n. minus one. Behaves like. This week on the c. and minus one game comes in the. No I write you differently now come in. The number of words is use of the original all you top and then we'll get.
[00:48:09]
In. To the in minus 2 and also one plus needle. And here for that one I should say we need the p. is simple. And then I write the 3rd point. In this one theory even though it claims to or I did separately let me write here. Tells us about the expected were you.
[00:48:42]
Where we also need to p. simple. Then derive the difference let's write the volume difference then you know see a box emission goes team minus p. n.. So these expected volume difference is c. in and it depends on the party took p. into the minus and over in minus $11.00 plus little 001.
[00:49:16]
And all those constants here they are strictly positive so this one this one and this one they all positive so. I guess you're going to actually pull do this 1st thing I think I don't have time. I wanted to indicate why we'll have this order of Make Me 2 in that room but I won't have time for that either so let me just remark some of the things that are a bit surprising here so the 1st surprising thing is that in vector expression here.
[00:49:54]
We don't have any luck factor that comes in. So that was surprising to us because in all the other results that we had. When we were picking these random polytope of on inside or on the boundary of the party talk we always had a lot faked respect here so that was a bit surprising to us.
[00:50:20]
What they want to say. Yeah I noticed that on the order of magnitude here in the. Difference is of this order which is. Smaller then what we got in this case but it was also a bit of a surprise to us that it is so much smaller and I guess I'm stuck here.
[00:50:50]
Thank. You. Right. Right. Which one. This one. Where. To control all I said the proof 200 pages so we need to control I mean but the inside I completely agree with you the inside case we have that there is an inside ball that we can control things we have seen already several times so that he said kind of move in a minute but it's of course you know when you have a c..
[00:51:40]
Plus body then you basically have the control from the inside and the outside and then through places that. It's. Not necessarily a no no not necessarily. Yeah. You you know they're the nearest exit. Spaces So question is behind you 000000. Some of them Rick Perry extend all of the results I'm not sure I can say that with a bit.
[00:52:35]
So. You know. I have not really looked at that yeah so that was kind of a yeah. Thank you to you know yes my question is what it was but the exactly Ok so like Ok I could have written you know I could take you by the by I guess they guy and look at the living desk editing goes to infinity so as I understand.
[00:53:14]
There's some questions Ok one did 1st of. All it is Absolutely yes yeah who would you like. But Absolutely. And here of course you always get. You know a scythe indicated the need to read in the picture you will get a menu potentially many many more Face it.
[00:53:45]
You know it right it's so. Interesting. It's no schools no that's. Yeah yeah yeah. Based on other results in this direction that. We had a long time ago with Casa and which was about. So yeah. It was not there at the Capitol and was prescribed which we want to approximate but we were having given up on you Tom keys same with n word.
[00:54:24]
And we wanted to approximate but how can you talk with fewer than in words and we did that by dropping a word takes so what do you mean we take away this what it takes and look at what remains and then measure this. Cement think differently and that we could do and actually be could not.
[00:54:49]
Actually it's so like you know depending on how the picture looks like so that was maybe a kind of choice to drop this would take it would have been stupid to drop this word takes right that would not have given us the same books Imation and this surprising thing to us then was that basically there were so I said.
[00:55:11]
It was set off because you know if we if we picked an index and drop they were Takes it would still work. So we have a control on you know how big they said Ok. Well it was. A war you metric argument. Were you metric argument on shoes being all.
[00:55:42]
Own choosing. Proper net somewhere so it was not completely deterministic. So the I that I should give created so that still lies not concentrate and myself. And I always believed that this really resolved tromping a word text or dropping a face that is potentially very useful and yeah.
[00:56:19]
Direct. Grants you might have said by $10000.00. You know that right now I'm going to print something you see. One week. For these things I don't know but for the thing we have so far this dropping a word takes out or being a 1st said we have because we can drop words from the original given point you talk with the n word to things and at the same time dropping facets of the call are all and things work nicely but.
[00:57:01]
I contrie call it the moment anything but that's also a good question.