Тема данной курсовой работы

Скачать 257.85 Kb.

Название	Тема данной курсовой работы
страница	3/5
Дата публикации	30.04.2015
Размер	257.85 Kb.
Тип	Документы

100-bal.ru > Право > Документы

1 2 3 4 5

Быстрые методы построения выпуклой оболочки.

Для построения выпуклой оболочки можно создать алгоритмы построения выпуклой оболочки, напоминающие быструю сортировку. Такие алгоритмы называются быстрыми методами построения оболочки.

Рис. 1: h – самая удаленная от bl точка.

Суть алгоритма состоит в том, что исходное множество S из N точек разбивается на два подмножества, каждое из которых будет содержать одну из двух ломаных, которые при соединении образуют выпуклую оболочку. Для начала нужно определить две точки, которые будут являться соседними вершинами выпуклой оболочки. Можно взять самую левую вершину, пусть это будет b, и самую левую относительно b из оставшихся, пусть это будет e. После чего нужно найти точку h максимально удаленную от прямой be. Все точки, лежащие в треугольнике bel исключаются из дальнейшего рассмотрения. Остальные точки будут делиться на два подмножества: точки, которые лежать левее bh и eh, и точки, которые лежат правее и bh, и eh. Каждое из них содержит ломаные которые в сочетании с e, b и h дают выпуклую оболочку. С каждым из них проделываем то же самое. В подмножестве точек S’, лежащих левее bh и eh выбираем h’, максимально удаленную от eh, которая делит его на три части. Из них одна выбрасывается, а остальные делятся опять. Это реализуется рекурсивной процедурой, которая для данного ей множества возвращает соответствующую часть выпуклой оболочки.

В случае, когда мощность каждого, из подмножеств, на которое делится множество, не превосходит некоторой константы умноженной на мощность множества, получаем сложность алгоритма, как и в быстрой сортировке O(N log N). Но в худшем случае может потребоваться время O(N ²).

Алгоритмы типа “разделяй и властвуй”.

В данном алгоритме, в отличие от предыдущего, множество S разбивается на два равномощных подмножества S’ и S’’, а затем рекурсивно строятся отдельно оболочки для каждого из них и объединяются.
CH(S) = CH(S’  S’’) = CH(CH(S’)  CH (S’’))
Сложность этого метода состоит в эффективном нахождении слияния двух выпуклых оболочек. Следующий алгоритм слияния был предложен Шеймосом^⁷:

Пусть у нас есть выпуклые многоугольники P’ и P’’. Нам требуется найти P – их слияние. Этого берется любая внутренняя точка p для P’ и проверяется на принадлежность P’’. Если она принадлежит, то по теореме 4 мы имеем два упорядоченных относительно полярного угла к p множества. За время равное сумме точек в них мы можем из них получить один упорядоченный список. После чего, используя обход Грэхема за такое же время получить требуемый выпуклый многоугольник.

Рис. 2: Так как точка p внутри обоих многоугольников, то вершины, как одного, так и второго, упорядочены относительно полярного угла к p.
В случае, когда p не принадлежит P’’, придется найти левую и правую опорные прямые из p к P’’, pl и pr соответственно. Опорной прямой к выпуклому многоугольнику P будем называть прямую l, проходящую через некоторую вершину этого многоугольника, таким образом, что внутренность P находится по одну сторону от l. Для этого нам достаточно время O(N). Все вершины P’’ между l и r, при движении от l к r против часовой стрелки, убираем из рассмотрения и выполняем те действия, которые выполняли в случае принадлежности.

Рис. 3: Так как точка p внутри одного многоугольника, то удаляем все видимые из p вершины второго многоугольника.
Как видно, и в этом случае на слияние требуется время O(N), где N – это общее количество точек в многоугольниках. Отсюда следует теорема:
Теорема 6. Выпуклая оболочка объединения двух выпуклых многоугольников может быть найдена за время, пропорциональное суммарному числу их вершин.

1 2 3 4 5

Похожие:

	Рекомендации по написанию курсовой работы При подготовке курсовой... Затем студент приступает к сбору информации. Первоначальное представление о теме и структуре работы можно составить по учебникам,...		Рекомендации студенту по выполнению рефератА (курсовой работы) Процесс... Выбор темы является весьма ответственным этапом выполнения реферата (курсовой работы), тема выбирается студентами самостоятельно...
	Отчетной работы) Курсовой проект (вид работы) По дисциплине «Теория антикризисного управления» Титульный лист курсовой работы (проекта), контрольной работы, домашнего задания, реферата, отчета о практике		Методические указания к выполнению курсовой работы по дисциплине... Рассматриваются вопросы, связанные с условиями и порядком выполнения курсовой работы. Даны общие требования к курсовой работе, выбору...
	Методические указания по выполнению курсовой работы 1 Содержание и структура работы Задание на выполнение курсовой работы по дисциплине «стратегический менеджмент», тематика курсвых работ		Выдержки из курсовой работы ...
	Методические указания по самостоятельной подготовке к практическим... Представлены методические указания по дисциплине «Маркетинг» к выполнению курсовой работы, проведению практических занятий, библиографический...		Каково целевое назначение курсовой работы как вида учебного процесса? В какой последовательности следует осуществлять подготовку дипломной (курсовой) работы?
	Методические указания к выполнению курсовой работы по дисциплине... Основными задачами, решаемыми студентами при выполнении курсовой работы являются		1. Экономическая сущность амортизации ос Темой данной курсовой работы является учет амортизации и методы ее начисления в условиях рынка
	Методические рекомендации по написанию курсовой работы по дисциплине... Цель курсовой работы состоит в том, чтобы развить у студентов навыки самостоятельной творческой работы, углубленно изучить какую-либо...		Методические указания к выполнению курсовой работы по дисциплине... Целью курсовой работы является закрепление теоретических знаний и выработка у студентов практических навыков по калькулированию себестоимости...
	Курсовая работа По курсу “Теория управления” Тема курсовой работы:... Тема курсовой работы: «Анализ и синтез оптимальной одноконтурной сау при использовании непрерывного и цифрового регуляторов»		Указания по оформлению курсовой работы по «Технологии профессиональной деятельности» Курсовая работа оформляется в виде электронного файла и пересылается преподавателю на электронную почту не позднее чем за 2 дня до...
	Рекомендации по выполнению курсовой работы Цель и значение курсовой... При разработке учебно – методического комплекса учебной дисциплины в основу положены		Методические указания по выполнению курсовой работы для студентов... Целью курсовой работы является систематизация, углубление и закрепление теоретических знаний по дисциплине, развитие навыков самостоятельной...

Школьные материалы