Поиск по сайту
Рефераты / Математика /Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ реферат на тему: Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости Задача ВО1. (Выпуклая оболочка). В E2 задано множество S, содержащее N точек. Требуется построить их выпуклую оболочку (т.е. полное описание границы CH(S)). Задача ВО2. (Открытый алгоритм для выпуклой оболочки). На плоскости задана последовательность из N точек p1, …, pN. Требуется найти выпуклую оболочку таким образом, чтобы, после обработки точки pi имелась CH({p1, …, pi}). Рассмотрим ВО1. То, что вершины многоугольника, являющегося выпуклой оболочкой, следуют в определенном порядке, указывает на связь с задачей сортировки. В самом деле, следующая теорема показывает то, что решение ВО1 должно быть в состоянии выполнить сортировку. Теорема 2. Задача сортировки за линейное время сводится к задаче построения выпуклой оболочки, и, следовательно, для нахождения упорядоченной выпуклой оболочки для N точек на плоскости требуется время (N log N). Доказательство. Сведем задачу сортировки N положительных действительных чисел x1,.., xN к задаче ВО1. Поставим в соответствие числу xi точку (xi, xi2) и присвоим ей номер i. Выпуклая оболочка этого множества, представленная в стандартном виде будет представлять собой упорядоченное относительно значения абсциссы множество всех точек из исходного. Из него за линейное время можно получить отсортированный список. Очевидно, что если мы можем решать ВО2, то мы можем решить и ВО1, по-этому задача ВО1 может быть сведена к ВО2 за линейное время. Следовательно, нижняя оценка для ВО2 не ниже (N log N). Предварительная разработка алгоритма построения выпуклой оболочки Для начала рассмотрим несколько малопродуктивных алгоритмов построения выпуклой оболочки. Определение 3. Точка p выпуклого множества S называется крайней, если не существует пары точек a, b S таких, что p лежит на открытом отрезке ab. Очевидно, что подмножество крайних точек E является наименьшим подмножеством S, выпуклая оболочка которого, является выпуклой оболочкой множества S, или conv(E)=conv(S). Поэтому нам необходимо для нахождения выпуклой оболочки выполнить два шага: Определить крайние точки. Упорядочить эти точки так, чтобы они образовали выпуклый многоугольник. Теорема 3. Точка p не является крайней точкой множества S только тогда когда она лежит в некотором треугольнике, вершинами которого принадлежат S, но сама она не является вершиной этого треугольника. Эта теорема дает возможность построить алгоритм проверки крайности точки. Если мы имеем дело с множеством S мощности N, то можно построить O(N3) треугольников. Проверка принадлежности точки треугольнику выполняется за постоянное количество операций. Следовательно, за время O(N3) можно определить, является ли точка крайней, а за O(N4) и для всех точек. Следующая теорема показывает, в каком порядке должны быть точки в конечном множестве. Теорема 4. Последовательные вершины выпуклого многоугольника располагаются в порядке, соответствующем изменению угла относительно любой внутренней точки. Упорядочить крайние точки множества можно относительно их центроида. Центроид множества для N точек вычисляется за время O(N) арифметических операций. Грэхем предложил использовать для этого только три любые неколлинеарные точки множества S. В худшем случае это требует время O(N), но почти всегда это первые три точки. Упорядочить их можно за время O(N log скачать реферат 1 2 3 4 ... последняя Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ Внимание! Студенческий отдых и мегатусовка после сессии!
Рефераты и/или содержимое рефератов предназначено исключительно для ознакомления, без целей коммерческого использования. Все права в отношении рефератов и/или содержимого рефератов принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие или полученные в связи с использованием рефератов и/или содержимого рефератов.
|
Обратная связь. |