Часть 5. Алгоритмы на графах. Точные интерпретации этой нижней границы достаточно сложны, поскольку базовые операции, используемые для решения этих двух задач (сравнение координат в

Точные интерпретации этой нижней границы достаточно сложны, поскольку базовые операции, используемые для решения этих двух задач (сравнение координат в задаче сор­тировки и сравнение расстояний в задаче построения дерева MST), различны и ввиду того, что существует возможность использования методов, таких как поразрядная сорти­ровка и метод перспективных сеток. Тем не менее, мы можем интерпретировать эту границу следующим образом: по мере выполнения сортировки мы должны следить за тем, чтобы алгоритм вычисления эвклидова дерева MST, который использует N lgN операций сравнения, был оптимальным, пока мы не используем числовые свойства координат; в этом случае мы можем надеяться, что он будет выполняться за линейное время (см. раздел ссылок).

Интересно поразмышлять над отношениями, связывающими графы и геометрические алгоритмы, которая обусловлена решением задачи вычисления эвклидова дерева MST. Многие практические задачи, с которыми нам, возможно, придется столкнуться, могут быть сформулированы либо как геометрические задачи, либо как задачи на графах. Если преобладающим свойством является физическое расположение объектов, то можно обра­щаться к помощи геометрических алгоритмов, описанных в части 7; однако если фунда­ментальное значение приобретают взаимосвязи между объектами, алгоритмы на графах, рассмотренные в данном разделе, скорее всего, окажутся более предпочтительными.

Эвклидово дерево MST, по-видимому, приходится на интерфейс между двумя этими подходами (входные данные обладают геометрическими свойствами, а элементы выход­ных данных взаимосвязаны), и в силу этого обстоятельства разработка простых методов вычисления эвклидова дерева MST остается труднодостижимой целью. В главе 21 мы стол­кнемся с подобного рода задачей, которая также приходится на этот интерфейс, но там эвклидов подход реализуется через алгоритмы, обладающие куда большим быстродействи­ем, чем соответствующие задачи на графах.