Aaaaaaaaargh... mijn respect voor "echte" wiskundigen is serieus tot een dieptepunt gezakt. Ik moet maandag namelijk een presentatie geven in een vak dat gaat over geometrische algoritmes en meer specifiek over algoritmes die dichtste buur problemen oplossen voor hoge dimensies.
De bewijzen in het paper gaan als volgt (en ik overdrijf echt niet):
Het kan gemakkelijk (aaargh) ingezien worden dat dit leidt tot een 1+epsilon/log(n)+alpha tijdscomplexiteit. We weten dan ook dat er kans is, voor voldoende grote A dat A/e log t d(p,q) < r (aaargh). Het is niet moeilijk om in te zien (tweemaal aaargh) dat dit geldt voor alle mogelijke dimensies d/a. Maar voor simpliciteit laten we a weg (we veronderstellen a=0) (aaaargh?).
We geven het bewijs in de finale versie van het paper (aaargh, dit is de finale versie van het paper!), maar uit het feit dat C = poly(sigma) en sigma = O(n), weten we dat C = O(log n) (nog is aaargh)...
Frustrerend dus, en ik die dacht dat wiskunde zwart op wit is, blijkbaar niet dus...
Niet te snappen...
(een moegetergde Bart)
De bewijzen in het paper gaan als volgt (en ik overdrijf echt niet):
Het kan gemakkelijk (aaargh) ingezien worden dat dit leidt tot een 1+epsilon/log(n)+alpha tijdscomplexiteit. We weten dan ook dat er kans is, voor voldoende grote A dat A/e log t d(p,q) < r (aaargh). Het is niet moeilijk om in te zien (tweemaal aaargh) dat dit geldt voor alle mogelijke dimensies d/a. Maar voor simpliciteit laten we a weg (we veronderstellen a=0) (aaaargh?).
We geven het bewijs in de finale versie van het paper (aaargh, dit is de finale versie van het paper!), maar uit het feit dat C = poly(sigma) en sigma = O(n), weten we dat C = O(log n) (nog is aaargh)...
Frustrerend dus, en ik die dacht dat wiskunde zwart op wit is, blijkbaar niet dus...
Niet te snappen...
(een moegetergde Bart)
3 opmerkingen:
lol :) Wiskunde op het hoogste niveau :)
(PS het bewijs van deze uitspraak laat ik over aan de lezer als oefening).
Miserie is het ja. Maar ben er nu toch van af. Terug wat tijd voor siggraph...
Ligt eens een tipje van de SIGGRAPH sluier op ... ;-)
Een reactie posten