How quadtrees would work? Genuinely curious, that's not a trap
Explain as if I'm not too good in maths also!
Think about a fractal checkerboard: take a single square, and subdivide into a 2x2 "quad" of sub-squares. (For 3D, this is a cube divided into a 2x2x2 "oct" of sub-cubes hence "octree" for 3D.) Take each of those sub-squares and subdivide them, so now you've got a 4x4 checkerboard divided up into 4 2x2 quadrants (the original level-1 sub-squares). Rinse and repeat to get 8x8, 16x16 etc.
Let's say max sensor range is roughly 1/128 of the board size (the original square). You can think of the region of the board that needs to be checked for a particular ship as a disk with diameter 1/64 (of the board size) - think of putting a penny down on the checkerboard. So you only need to check enemy ships that lie within the disk. If you think about cells (sub-sub-...squares) that are 1/32 the board size, then most (75%) of the time the disk is completely within the cell and you only need to check enemy ships that are in the same cell as you. So if you pre-sort all enemy ships into bins corresponding to the cells, then 75% of the time you only need to check the enemy ships in the bin/cell you're in. If the ships are uniformly distributed over the board, this will give you roughly a 1 million-fold speed up since there are 1/32*1/32 = 1/1K cells of that size on the board.
The algorithm is more subtle when the ship is near a cell boundary (the other 25%) - you have to identify and check all the neighboring cells that the disk overlaps - but that's a rough flavor of how quadtrees (and octrees) work to speed up searches. In 1D this is very closely related to the "divide and conquer" logarithmic search and sort algorithms, where you recursively take the region of interest, divide it in two, and ask if you're interested in the upper or lower half.
[EDIT] This is also intimately related to a really cool sorting algorithm for points in 2D, 3D etc space that is (logarithmically) good at keeping points that are close to each other in space close to each other in the sorted sequence: it's called Morton order (or Z-order):
https://en.wikipedia.org/wiki/Z-order_curve As I write this the Wikipedia page has a good picture of this fractal subdivision (unfortunately it doesn't have the cell boundary lines themselves), but since reality is malleable and retcon happens in Wikipedia land I can't guarantee it's still there
This is the technical way that you would use quadtree ideas to find nearest neighbors - a nifty property of Morton ordering is that if you look at the first an last points on an interval of the sorted set, then the smallest quadtree cell that contains both start and end guaranteed to contain all the points between in the sorted list, so those are the only points you need to check. So if you think about your penny of the (hierarchically subdivided) checkerboard, then you just need to find the smallest cell that the disk lies completely in in order to find the points you need to check. [/EDIT]
John