[bilytur]

Если Входная точка А меняется то любая сортировка будет работать медленнее даже простого линейного поиска Greyman, надо признать прав.

Могу предложить следующее. Если памяти хватает создать 3 индекса на каждую координату. (Индексы упорядочены)
Бинарным поиском (очень быстрым) отсечь явно не нужные точки лежащие за описанным кубом. И принять все во вписанном кубе.
При наличии индексов это пройдет практически моментально. А вот дальше остается небольшой кубический слой.
И в нем уже вести поиск.