Przyjrzałbym się na początku co się dzieje w przypadku 2d. Wtedy wydaje mi się, że wystarczy policzyć coś w stylu minimum bounding rectangle (tylko ten prostokąt będzie obrócony o 45 stopni) i punkty najbardziej od dowolnego punktu zawsze będą na krawędzi tego prostokąta:
Tutaj czarne to punkty, czerwone to minimum bounding rectangle. Spójrzmy na ten czarny punkt w środku. Wszystkie punkty jasno zielone są w odległości 1 od tego punktu, ciemniej zielone w odległości 2, a jeszcze ciemniej w 3. Zatem widać, że ten najbardziej oddalony będzie gdzieś na krawędzi tego bounding rectangle. Zatem wystarczy znaleźć krawędzi i wziąć chyba 2 najbardziej skrajne punkty z tej krawędzi i sprawdzić odległość od punktu dla którego szukamy odpowiedzi. Jeśli rozumowanie jest poprawne to o dziwo odpowiedź na zapytanie działa w czasie stałym.
W przypadku 3d prawdopodobnie jest tak samo tylko trzeba uogólnić ten bounding rectanle na 3 wymiary