Consider alternative R-tree build algorithm(s)

[bjornharrtell]

Current implementation uses the Packed Hilbert R-tree algorithm. I've had some recent discussions indicating that depending on data might produce trees that have significant overlaps and as such do not have optimal query performance.

Specifically the Overlap Minimizing Top-down (OMT) seem promising. See http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf.

For this to be interesting the resulting tree must work as is with current query implementation and I believe there is a good chance it could.

Note that OMT will likely make tree build time more expensive but since the intent of FlatGeobuf with spatial index is write once read many that is not a bad thing.

[kkdd]

Is priority R-tree promising also?
I found its c++ implementation in https://github.com/atksh/python_prtree .

• The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (SIGMOD '04), Paris, France, June 2004, 347-358. Journal version in ACM Transactions on Algorithms.

[bjornharrtell]

Not sure about priority R-tree.

The paper on OMT is a bit hard to interpret, in my opinion. But I found this implementation that could perhaps help in understanding - https://github.com/dhconnelly/rtreego/blob/master/rtree.go.