Следующее может помочь поставить алгоритмы линейного времени среднего случая (для диаметра конечного множества) в более ясном свете, а также контрастировать проблемы многомерной и плоской геометрии.
В 1983Мегиддо дал детерминированный алгоритм линейного времени для наименьшего вмещающего круга (или сферы в более высоких измерениях).
В общем случае вмещающий круг будет иметь две или три точки на своей границе, итаким образом, нахождение двух наиболее удаленных друг от друга может быть выполнено «в среднем» за постоянное время, когда известен ограничивающий круг.В более высоких измерениях число точек общего положения, необходимых на границе сферы, увеличивается (D + 1 балл для измерения D), и действительно стоимость вычисления расстояния между одной парой точек возрастает линейно с измерением.
Подмножество точек, лежащих на ограничивающем круге или сфере, также находится за линейное время.В теоретическом наихудшем случае все точки будут лежать на ограничивающей окружности или сфере, но это, по крайней мере, более строго, чем просто наличие всех точек на выпуклой оболочке.Если точки на сфере независимо возмущены, скажем, вдоль радиальных линий, то общее положение гарантируется с вероятностью 1, и приблизительный диаметр можно найти только из точек D + 1 на пересмотренной вмещающей сфере.Это рандомизированное приближение имеет квадратичную зависимость от размерности, но имеет только линейную сложность по количеству точек.
Если точки, лежащие на ограничивающем круге, «отсортированы» (циклически, конечно), можно найти самую дальнюю парув линейном времени, полагаясь на «унимодальность» круга (это означает, что расстояния от фиксированной точки монотонно растут до антипода, а затем падают) , чтобы амортизировать стоимость вычисления расстояний .К сожалению, такая сортировка привела бы к шагу с O (n log n) временной сложностью, и это оказалось оптимальным в худшем случае для точных детерминированных методов в плоском случае.
В 2001 году Рамосу удалось показать O (n log n) детерминированный алгоритм для трехмерных наборов , но метод настолько сложен, что реализация может быть непрактичной или медленнойчем поиск всех пар методом перебора до очень больших наборов данных .
Для более высоких измерений многие авторы рассмотрели рандомизированные или приближенные алгоритмы.См. тезис Петра Индика (2000) для приближенных методов только с полиномиальной зависимостью от размерности для различных задач близости.