Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Рг
3.3. Алгоритм построения выпуклой оболочки 127
Теорема 3.5. Луч, выходящий из внутренней точки ограниченной выпуклой фигуры F, пересекает границу F в точности в одной точке ').
Теорема 3.6. Последовательные вершины выпуклого многоугольника располагаются в порядке, соответствующем изменению угла относительно любой внутренней точки.
Представьте луч, выходящий из некоторой внутренней точки q многоугольника Р и заметающий вершины многоугольника Р в порядке движения против часовой стрелки, начиная из положения, совпадающего по направлению с положительным на-
Лорядок обхода^
Рв
Рис. 3.4. Вершины многоугольника Р упорядочены относительно точки q.
правлением оси х системы координат. По мере движения от вершины к вершине полярный угол2) луча монотонно увеличивается. Именно это имелось в виду, когда говорилось о том, что вершины многоугольника Р «упорядочены» («располагаются в порядке») (рис. 3.4).
Если даны крайние точки некоторого множества, то его выпуклую оболочку можно найти, выбрав точку q, про которую известно, что она является внутренней точкой оболочки, и упорядочив затем крайние точки в соответствии с полярным углом относительно q. В качестве точки q можно взять центроид множества крайних точек: хорошо известно, что центроид множества точек является внутренней точкой выпуклой оболочки3).
') Эта теорема является следствием теоремы 1.10 из [Valentine (1964)] и теоремы Жордана.
2) Полярный угол измеряется обычным способом в направлении против часовой стрелки от положительного направления оси х.
3) При условии что внутренность не пуста. В книге [Benson (1966), упр. 25.15] «внутренность» понимается в смысле относительной (индуцированной) топологии. В Е3 выпуклая оболочка двух различных точек представляет отрезок, внутренность которого является пустой в метрической топологии ?3, но не пустой в относительной топологии.
128
Гл. 3. Выпуклые оболочки: основные алгоритмы
Центроид множества из N точек в ^-мерном пространстве может быть тривиально вычислен за O(Nk) арифметических операций.
Грэхем предложил иной метод нахождения внутренней точки, заметив, что вполне достаточно взять центроид любых трех неколлинеарных точек [Graham (1972)]. Он начинает с двух произвольных точек и по очереди исследует оставшиеся N — 2 точек, ища среди них одну, которая не лежит на прямой, определяемой первыми двумя точками. В худшем случае для этого требуется время O(N), но почти всегда процесс заканчивается через некоторое фиксированное вре-р мя: если точки выбираются из абсо-
А лютно непрерывного распределения,
/ \ то с вероятностью единица первые
/ \ три точки являются неколлинеарными
/ \ [Efron (1965)].
/ \Рг Найдя крайние точки множества S,
можно за время 0(N) найти некото-рую точку q, являющуюся внутренней
[_Р_5 точкой оболочки. Остается только от-
* *" сортировать (упорядочить) крайние Рис. 3.5. Сравнение поляр- ™чки в соответствии со значением по-ных углов путем вычисле- лярного угла, используя точку q в ка-ния ориентированной площа- честве начала системы координат. Это ди треугольника (0,р2,р,). можно сделать, преобразуя точки в полярную систему координат за время O(N), а затем отсортировав их за время 0(N\ogN), но на самом деле не требуется явного вычисления полярных координат. Так как сортировка может быть выполнена путем попарных сравнений, то необходимо лишь определять, какой из двух заданных углов больше; нам не требуются их численные значения. Давайте рассмотрим этот вопрос более подробно, так как он иллюстрирует простой, но важный геометрический «трюк», оказывающийся полезным во многих приложениях. Пусть на плоскости заданы две точки pi и р?. Какая из них имеет больший полярный угол? На этот вопрос можно без труда ответить, если рассмотреть ориентированную (с учетом знака) площадь некоторого треугольника. Действительно, если даны две точки pi и р2, то рг образует с осью х строго меньший полярный угол, чем Рь тогда и только тогда, когда треугольник (О, рг, Pi) имеет строго положительную площадь (рис. 3.5).
На этом заканчивается подробное обсуждение нашего первого алгоритма построения выпуклой оболочки. Было показано, что эта задача может быть решена за время О (TV4) с использованием только арифметических операций и сравнений.
3.3. Алгоритм построения выпуклой оболочки
129
3.3.2. Метод обхода Грэхема
Алгоритм со временем выполнения 0(N4) не позволит обрабатывать очень большие наборы данных. Если временные характеристики должны быть улучшены, то это можно сделать, либо устранив избыточные вычисления в имеющемся алгоритме, либо выбрав иной теоретический подход. В этом разделе мы исследуем наш алгоритм с точки зрения наличия в нем ненужных вычислений.
Так ли необходимо проверять все треугольники, определяемые множеством из N точек, чтобы узнать, лежит ли некоторая точка в каком-либо из них? Если нет, то имеется некоторая надежда, что крайние точки можно найти за время, меньшее чем О (N*). Грэхем в одной из первых работ, специально посвященных вопросу разработки эффективных геометрических алгоритмов [Graham (1972)], показал, что, выполнив предварительно сортировку точек, крайние точки можно найти за линейное время. Использованный им метод стал очень мощным средством в области вычислительной геометрии.
