이런 용도로 적합한 자료 구조가 있을까요?(C++구현)

를 참고하세요.
http://en.wikipedia.org/wiki/Kd_tree

graphics 등에서 워낙 자주 사용되는 구조이므로 c++ 구현은 많이 있을 듯 싶습니다.

그런데 수만개라면 저라면 그냥 linear search (for문 돌리는 것)부터 해볼 것 같군요. 요즘 컴퓨터가 워낙 빨라서. :-)

그리고 2차원 데이터라고 해도 map 을 이중으로 써서 점들의 온도를 기록할 게 아니라, (x,y) -> T 로 기록하시는 게 좋을 듯 싶습니다.

거리를 구해야 하는 점의 갯수를 줄여야 한다는 것이로군요. 게임에 주로 사용하는 것들을 한번 적용해보시는 것은 어떨지요.

간단하게 해볼만 한 것은, 첫번째로 각 축별로 좌표를 정렬해서 검색하는 것입니다.

먼저, 모든 좌표를 각 축별로 정렬해 놓습니다. 측정된 좌표들이 고정이라면 한번만 해놓으면 되는 것이고요. (게임에서는 여러 객체들이 생기고 사라지지만, 정렬되어 있는 자료구조에 어떤 것을 넣는 빼는 것은 크게 문제될 것은 없습니다.)

입력되는 좌표값을 각 축별로 정렬되어 있는 자료구조에서 각각 검색하고, 이렇게 나온 좌표들의 교집합을 구합니다. 검색할 범위는 적절히 정하시면 될 듯 하고요.

이렇게 해서 나오는 좌표는 많아야 수십개정도일 것이므로, 이 점들과의 거리를 구해서 3개를 뽑아내시면 됩니다.

다른 방법으로는, 미리 좌표들을 격자로 구분해놓고 검색 범위를 줄일 수도 있습니다.

2D 게임에서는 보통 4등분으로 격자를 여러 단계로 미리 만들어 놓고 빠르게 검색하기도 합니다. 입력되는 좌표에 따라 처음 4등분 한 곳을 결정하고 그 한 곳의 4등분 된 격자에서 다시 찾는 과정을 반복하면, 최종적으로 검색할 양을 상당히 줄일 수 있습니다. 3차원이면 8등분으로 하게 됩니다. 어떤 응용에서는 이 등분의 크기를 객체의 밀도에 따라 다르게 하기도 하며, 등분 깊이의 레벨을 조절하기도 합니다. 격자의 경계를 약간 밀어서 경계선에 있는 물체 문제를 피하기도 합니다.

게임에 사용하는 트리 형태보다는 어느정도 한계를 정할 수 있는 상황이므로, 적절한 격자들을 미리 촘촘하게 배열해서 입력된 좌표가 어느 격자에 속하는지 구하고 주변 격자들의 점을 포함해서 점간 거리를 구하는 것도 크게 문제되지 않을 것으로 보입니다.

Quadtree, Octree로 검색하시면 되고, http://en.wikipedia.org/wiki/File:Point_quadtree.svg 이 그림 한장이면 바로 이해하실 수 있습니다.

좀 더 적극적으로 해볼만 한 것은 BSP 변형으로 고정된 구조물로 이루어진 공간에서 어떤 점이 어떤 공간에 있는지를 빠르게 검색할 수도 있습니다만, 배꼽이 커질 듯하고요.