Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Если исходные данные уже упорядочены, то, используя метод Грэхема, можно найти нижнюю оболочку за линейное время. Если же точки не упорядочены, то в худшем случае потребуется время 0(N log N).
4.2.3. Выделение кластеров (диаметр множества точек)
Следуя работе Хартигана [Hartigan (1975)], кластеризация—это выделение групп схожих объектов (кластеров). Кластеризация множества заключается в разбиении его на части таким образом, чтобы минимизировать некоторую меру различия. В книге Хартигана приведен целый ряд таких мер и процедур кластеризации с их использованием. Мы рассмотрим двумерный случай, предполагая, что координаты х и у выбраны таким образом, что мерой различия является обычная метрика евклидова пространства. Мерой «разброса» в кластере является максимальное расстояние между двумя его произвольными точками, называемое диаметром кластера. Интуитивно понятно, что кластер с небольшим диаметром содержит элементы, довольно тесно связанные друг с другом, чего нельзя сказать о кластерах с большим диаметром. Приведем формулировку одной из задач кластеризации.
Задача В09 (^-КЛАСТЕРИЗАЦИЯ С МИНИМАЛЬНЫМ ДИАМЕТРОМ). На плоскости заданы N точек. Требуется разбить их на К кластеров Сь Ск таким образом, чтобы максимальный из диаметров кластеров был минимальным.
Трудно представить, как можно решить эту задачу, не имея по крайней мере алгоритма определения диаметра кластера. Это приводит к следующей задаче:
Задача ВОЮ (ДИАМЕТР МНОЖЕСТВА). На плоскости заданы N точек. Найти две наиболее удаленные друг от друга точки.
Эта задача кажется настолько элементарной, что даже трудно представить, что с ней связаны какие-то проблемы. В конце
4.2. Приложения в статистике
217
г/
Образ А
V /
>х /
Образ В
концов, можно непосредственно вычислить расстояние между каждой из N(N—1)/2 пар точек и выбрать максимальное из них, определяющее диаметр множества. Что же здесь еще изучать? Несомненно, следует задать вопрос, является ли эта процедура, имеющая сложность 0(N2), наилучшим из возможных алгоритмов. Вопрос о вычислительной сложности задач такого сорта является основным в вычислительной геометрии, который мы обязаны ставить даже в случае отсутствия в нем практической надобности.
Метод получения нетривиальной нижней оценки для задачи ДИАМЕТР МНОЖЕСТВА был разработан совсем недавно1). Он основан на сведении задачи РАЗДЕЛИМОСТЬ МНОЖЕСТВ, для которой известна нетривиальная нижняя оценка, к задаче ДИАМЕТР МНОЖЕСТВА.
Пусть А={аи aN} и ? = = {йь bN}—два множества действительных неотрицательных чисел. Для проверки того, что множества А и В не содержат одинаковых элементов (т. е. разделимость множеств А и В), требуется выполнить Q(AMogiV) сравнений [Reingold (1972)]. Сведем задачу РАЗДЕЛИМОСТЬ МНОЖЕСТВ к ДИАМЕТР МНОЖЕСТВА, отобразив множества Л и В на единичную окружность С, при этом элементы множества А отображаются в первый квадрант, а элементы множества В — в третий. Отображение устроено следующим образом: а,- отображается в точку пересечения окружности С с прямой у = а,х, находящуюся в первом квадранте, а ft; отображается аналогичным образом, но только в точку, находящуюся в третьем квадранте (рис. 4.18). Обозначим через 5 множество, содержащее 2/V построенных таким образом точек пересечения. Нетрудно понять, что множество S имеет диаметр, равный 2, тогда и только тогда, когда оно содержит две диаметрально противоположные точки окружности С, т. е. когда А П В Ф 0. Таким образом, имеет место следующая теорема, справедливость которой для пространств более высокой размерности очевидна:
Рис. 4.18. Отображен А и В на единичную окружность С.
') Исходную идею преобразования можно найти в [Brown (1979а)]. Очевидно, Добкин и Манро независимо придумали одно и то же отображение.
218 Гл. 4. Выпуклые оболочки: расширения и приложения
Теорема 4.16. В рамках модели алгебраических деревьев вычислений для вычисления диаметра конечного множества из N точек в Ed (d^z2) требуется Q{N\ogN) операций.
Вернемся к разработке алгоритма решения задачи ДИАМЕТР МНОЖЕСТВА. Теорема 4.17 дает ключевую идею, позволяющую избежать вычисления расстояния для каждой пары точек:
Теорема 4.17 [Hocking, Young (1961)]. Диаметр множества равен диаметру его выпуклой оболочки. (См. рис. 4.19.)
Конечно, в худшем случае может получиться так, что все исходные точки множества окажутся вершинами выпуклой оболочки, так что, затратив 0(N\ogN) времени, не удастся удалить ни одной точки.
Далее, если не оговорено иное, будем рассматривать двумерный случай задачи. В этом случае выпуклая оболочка множества точек является выпуклым многоугольником, а вовсе не конечным множеством точек. Так что имеет Рис. 4.19. Diam(S)= Diam(CH(5)). место несколько иная задача.
Задача ВОН (ДИАМЕТР ВЫПУКЛОГО МНОГОУГОЛЬНИКА). Дан выпуклый многоугольник. Найти его диаметр. Сразу же получаем
ДИАМЕТР МНОЖЕСТВА ozNlogN ДИАМЕТР ВЫПУКЛОГО МНОГОУГОЛЬНИКА
Если диаметр выпуклого многоугольника можно найти за время, меньшее чем 0(N2), то и диаметр множества можно будет найти быстрее, чем за 0(N2) операций.
