Köszi. Ez tetszik heurisztikus szempontból. Kicsit mást csinálok, mindjárt leírom.
Viszont az egzakt megoldást nagyon szeretem, mert maximálisan elérhető "minőséget" ad a válaszban. Nem marad ki semmi, nem torzul semmilyen statisztikai és matematikai "arány". És a limit kiértékeléséhez szükséges infó is teljes. Tehát tökéletes a megoldás.
Sajnos gyorsítani kell. Én több dolognál egy olyan heurisztikát dolgoztam ki, melynél összekeverem a pontokat, és egyszer megyek végig az egymás mellé esőkön. Másképp fogalmazva, véletlen mintavételezek egyenként és a szomszédosak távolságát vizsgálom.
Ez egy olyan statisztikát segít előállítani, mely "erősen" fog hasonlítani arra, amit akkor kapnánk, ha végig megyünk az összes négyzetes kombináción. Ez nem más, mint a távolságok átlaga és szórása. Természetesen adott mértékben torzul ez is, de van egy alap "gravitációja". És ha sikerül tovább vinni a megoldást úgy, hogy elégséges legyen az ezzel járó bizonytalanság (még mindig egy kívánt szintű megbízhatóságon belül maradva), akkor egy "elégséges" minőségű heurisztikát kaphatunk.
Az általad ajánlott bin-ezésnél - ha jól gondolom - fordított az igény. Nekem nem a nagyon közelieket kell azonosítanom, hanem a nagyon távoliakat. De ráadául nem csak a globális tömegtől távoliakat, hanem a lokális tömegtől is. Tehát belső struktúrákban lévő leszakadókat is ki kell tudnia emelnie a megoldásnak.
Jól gondolom, hogy a belső leszakadás detektálására túl torz a spatial hash?
Belső leszakadás például egy tórusz felső belsejében, arányaiban túl távoli pont, mely arányosan sokkal távolabb van a körülötte lévőktől, mint a körülötte lévők egymástól.