3 ms·
> quad-trees have pathological space complexity for geometries like polygons Any idea what is used in the wild for closest point queries against non-point data
by santaclaus 10y ago
> quad-trees have pathological space complexity for geometries like polygons
Any idea what is used in the wild for closest point queries against non-point data (triangle meshes or otherwise)?
- geophile 10y agoQuadtrees are fine. Just don't approximate the polygon to the limit of resolution of the space. I wrote a paper many years ago on a related problem. The conclusion was that a very small number of quads would be optimal. Too many is obviously a problem; too few and you have to filter out a lot of false negatives. The paper was in ACM SIGMOD 89, Redundancy in Spatial Databases.