$ Spatial indexes

Rectangle list

O(n³)

R-tree

O(n log n)
  • 5 elements 9x speedup
  • 10 elements 18x speedup
  • 20 elements (typical) 37x speedup