Вершина - выпуклая оболочка
Cтраница 1
Вершины выпуклой оболочки и опорные прямые тоже являются в некотором смысле крайними элементами; эти понятия используются в § 5, там приведены их определения и свойства. [1]
Оценки числа вершин выпуклой оболочки целочисленных точек многогранника нужны при анализе эффективности алгоритмов решения соответствующих задач оптимизации. [2]
Если в действительности число вершин выпуклой оболочки равно h, то время выполнения алгоритма Джарвиса будет 0 ( hN), и он очень эффективен, когда заранее известно, что значение h мало. Например, если оболочка заданного множества является многоугольником с произвольным постоянным числом сторон, то ее можно найти за линейное относительно числа точек время. Этот факт чрезвычайно важен в свете анализа сложности алгоритмов построения выпуклой оболочки в среднем, который будет представлен в следующей главе. [4]
Предположим противное, а именно что имеется вершина выпуклой оболочки р, не являющаяся максимумом ни при каком присваивании знаков координатам точек. Поместим начало системы координат в точку р и рассмотрим все 2d ортантов пространства Ed. Очевидно, что conv ( S) содержит внутри точку р и, следовательно, conv ( S) conv ( S), что противоречит предположению о принадлежности точки р границе выпуклой оболочки. [5]
Обратите внимание: если точка не является вершиной выпуклой оболочки, то она является внутренней точкой для некоторого треугольника ( Opq), где р и q - последовательные вершины выпуклой оболочки. Суть алгоритма Грэхема состоит в однократном просмотре упорядоченной последовательности точек, в процессе которого удаляются внутренние точки. Оставшиеся точки являются вершинами выпуклой оболочки, представленными в требуемом порядке. [6]
Основная идея состоит в том, чтобы организовать вершины текущей выпуклой оболочки в виде бинарного дерева определенного вида и для каждой новой точки р, прежде всего определить, находится ли она внутри текущей выпуклой оболочки. Если это так, то точка игнорируется. В противоположном случае ищутся две опорные прямые из точки р к текущей выпуклой оболочке. Затем выпуклая оболочка изменяется путем удаления соответствующего множества вершин, заключенных между опорными прямыми, и включения точки pi в качестве новой вершины. [7]
Основная идея состоит в том, чтобы организовать вершины текущей выпуклой оболочки в виде бинарного дерева определенного вида и для каждой новой точки р, прежде всего определить, находится ли она внутри текущей выпуклой оболочки. Если это так, то точка игнорируется. В противоположном случае ищутся две опорные прямые из точки р / к текущей выпуклой оболочке. Затем выпуклая оболочка изменяется путем удаления соответствующего множества вершин, заключенных между опорными прямыми, и включения точки pi в качестве новой вершины. [8]
Это соотношение, очевидно, справедливо для всех вершин выпуклой оболочки спектра S. [9]
Как отмечалось выше, решение этой задачи будет достигаться в вершинах выпуклой оболочки - точках статистики, а кроме того, обе процедуры, и огибание множества статистики выпуклой оболочкой, и симплекс - метод представляют определенные вычислительные трудности. [10]
Примером такого ограничения служит ситуация, когда все N точек множества 5 являются вершинами выпуклой оболочки. [11]
Конечно, в худшем случае может получиться так, что все исходные точки множества окажутся вершинами выпуклой оболочки, так что, затратив О ( A / log Л /) времени, не удастся удалить ни одной точки. [12]
Даны п точек на плоскости. Все ли п точек являются вершинами выпуклой оболочки. [13]
Можно было бы предположить, что алгоритм поиска двух ближайших друг к другу точек множества можно получить простым обобщением указанного алгоритма, но это не так. Две наиболее удаленные точки множества с необходимостью являются вершинами выпуклой оболочки этого множества, и для разработки быстрого алгоритма можно использовать свойство выпуклости. Две ближайшие точки совсем не обязательно имеют какое-либо отношение к выпуклой оболочке, так что для решения этой задачи должен быть разработан новый метод. Этому и будет посвящена данная глава. Мы рассмотрим большой класс задач, связанных с определением близости точек на плоскости. Наша цель будет состоять в том, чтобы решать все эти не связанные на первый взгляд между собой задачи, используя единый алгоритм, который выявляет, обрабатывает и запоминает компактным образом всю информацию относительно близости точек. Чтобы добиться этого, мы возродим классический математический объект, называемый диаграммой Вороного, представив ее в виде эффективной вычислительной структуры, позволяющей добиться огромного преимущества по сравнению с лучшими из ранее известных алгоритмов. В этой главе для штурма этого большого и трудного класса задач - задач нахождения ближайших точек или, иначе говоря, задач определения близости - будут использованы некоторые обсуждавшиеся ранее методы решения геометрических задач, такие как построение выпуклой оболочки и геометрический поиск. [14]
 |
Верхняя оболочка простого многоугольника.| Карман и его крышка. [15] |
Страницы: 1 2