Граница - выпуклая оболочка
Cтраница 1
Граница выпуклой оболочки локально является графиком непрерывно дифференцируемой функции ( см., например, [1]), типичные особенности которой - разрывы второй производной. В [4] показано, что множество таких разрывов в окрестности особенности УЗ является парусником. Парусник - это объединение оборванного ласточкина хвоста ( являющегося границей множества РЗ) и половины зонтика Уитни, линии самопересечений которых совпадают, а касательные конусы транс-версальны. Согласно [4], все парусники локально диффеоморфны друг Другу. [1]
Вначале живым является единственное ребро, принадлежащее границе выпуклой оболочки, а все остальные ребра - спящие. По мере работы алгоритма ребра из спящих становятся живыми, а затем мертвыми. [2]
Для определения того, какая именно точка должна быть включена в границу выпуклой оболочки после точки s, используется тот факт, что при обходе границы выпуклой оболочки в направлении по часовой стрелки каждая ее вершина должна соответствовать повороту влево. [3]
Временные затраты данного алгоритма равны O ( hn), где Л - число вершин в границе искомой выпуклой оболочки. [4]
 |
В оптимальной точке не существует опорной плоскости. [5] |
Таковыми являются векторы у, для которых ( w ( y), v) лежит в пересечении границы выпуклой оболочки R с границей R. Векторы у, не обладающие этим свойством, образуют зазоры. [6]
Если в многоугольнике освещенных ребер нет, то это означает, что новая точка попала внутрь или на границу старой выпуклой оболочки, и, значит, больше ничего делать не надо. [7]
Отметим здесь, что результатом решения задачи построения выпуклой оболочки на плоскости является упорядоченный список вершин, лежащих на границе выпуклой оболочки. [8]
В точности ту же самую функцию мы получили бы и в задаче без ограничений, в которой индикатрисой для L служит граница выпуклой оболочки нашей пары окружностей. [9]
Время работы предлагаемых алгоритмов равно либо O ( nlogrc), либо 0 ( пН), где Н - число точек на границе выпуклой оболочки. Исключение составляют работы [68, 310], в которых рассматривается построение выпуклой оболочки в пространствах более высокой размерности. [10]
Для определения того, какая именно точка должна быть включена в границу выпуклой оболочки после точки s, используется тот факт, что при обходе границы выпуклой оболочки в направлении по часовой стрелки каждая ее вершина должна соответствовать повороту влево. [11]
 |
К доказательству теоре мы. [12] |
Так как лишь неограниченные многоугольники могут иметь в качестве ребер лучи, то лучи диаграммы Вороного соответствуют парам смежных точек множества S, лежащих на границе выпуклой оболочки. [13]
Время работы предлагаемых алгоритмов равно либо О ( n log л), либо 0 ( пН), где / 7 - число точек на границе выпуклой оболочки. Исключение составляют работы [68, 310], в которых рассматривается построение выпуклой оболочки в пространствах более высокой размерности. [14]
Выпуклая оболочка подмножества аффинного пространства - это пересечение всех содержащих его полупространств. Граница выпуклой оболочки компактной гладкой гиперповерхности без края может иметь особенности. Например, особенности границы выпуклой оболочки общей замкнутой кривой на плоскости исчерпываются разрывами второй производной. [15]
Страницы: 1 2