3 ms·
FYI, searching the R-tree also has runtime complexity of O(N) in the worst case. I believe there is some R-tree variant which actually provides asymptotically b
by openasocket 11y ago
FYI, searching the R-tree also has runtime complexity of O(N) in the worst case. I believe there is some R-tree variant which actually provides asymptotically better performance than the naive case, but it is very complicated and tends to perform worse on average in practice.
Source: just spent two months implementing R-trees in Rust
- urschrei 11y agoWas just looking for an implementation last week. Is it public?
- openasocket 11y agoNot yet, but it will probably be open sourced sometime soon.
- rosshemsley 11y agoYes, but the O(N) is generally only for pathological inputs. Geo data is generally nicely distributed. R-tree (or similar) is the correct solution here.