3 ms·
Indeed. And you don't even need square roots for identifying the three closest, since squared distances are just as good for that. So it's, what, a few instance
by BugsJustFindMe 8y ago
Indeed. And you don't even need square roots for identifying the three closest, since squared distances are just as good for that. So it's, what, a few instances of very basic arithmetic and then three roots? I don't see the complication either. It would be nice to know which part of their process introduced the difficulty. Was it the update frequency?
- simcop2387 8y agoI might even avoid the squares and use a manhattan distance metric instead. No multiplication at all, just absolute value and addition.
- viggity 8y agofinding an approximate root for these purposes can be really quite fast, as was demonstrated in Quake III. https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root