Hacker News Reader

PR Quadtrees (https://opendsa-server.cs.vt.edu/OpenDSA/Books/CS3/html/PRqu...) got me my current job at Google. One of my interviewers asked basically "how would you design Google Maps?" and I based my answer on this data structure.

View on HN

Looked to see what these things were. Realised it might be the reason I made a career in IT: I used this structure (I called it a box) to calculate residues (https://en.wikipedia.org/wiki/Residue_(complex_analysis)), which I figured would be simpler using an object-oriented hence I learned myself C++. This was during my PhD (theoretical physics).

Off course, never used C++ again (learned object oriented language ‘properly’ using SmallTalk, which I also never used again in real life). Now, 25 years later, seeing the first time that I was using an (adaption of) PR Quadtrees.

Why subdivide so far? I find it better to have leaf nodes contain an array of up to some small number of points, e.g. 20. That reduces the pointer chasing significantly, and a linear search through such a small array is very fast.

Reply on news.ycombinator.com