References
TODO
Prefix arrays
Convex hull
Arrays
Trees
Randomness
Example for [0.25, 0.3, 0.1, 0.2, 0.15]:
Another example:
Spatial / multidimensional indexing
R-trees
Inserting grows bboxes of all ancestors
Also, balanced tree. Split/merge to maintain between M/2 and M items per node. Splits try to minimize empty space / “false hits” that would be incurred by intersection queries. Optimal algo is O(2^n). Instead O(n^2) approximation.
R* tree: improvement of R tree with better splitting algo that considers degree of overlap (as well as area increase)
K-D trees: can query for nearest points. recursively split at median point along a single dimension
Must traverse other cells as long as they may contain something closer than best (on “this” side of the split)
Quadtrees
Cell method
KDB trees
Corner stitching
Grid files
Octrees
Shortest paths
Trees
Tree algos
((()())())
Graphs
Algo: compute degrees, then DFS with backtracking and tracking remaining outdeg of any node, prepending to solution path when no more outdeg.
Conditions:
For undirected
Numerical computation
Probabilistic