Граница - выпуклая оболочка
Cтраница 2
Один из способов построения выпуклой оболочки конечного набора точек S на плоскости напоминает вычерчивание при помощи карандаша и линейки. Вначале выбирается точка а е S, заведомо являющаяся вершиной границы выпуклой оболочки. [16]
Отложим пока вопросы про периметр и площадь и посмотрим, как меняется выпуклая оболочка при добавлении новой точки. Ясно, что если новая точка оказалась внутри или на границе старой выпуклой оболочки, то оболочка не меняется. Если же новая точка оказалась вне старой оболочки, то оболочка меняется так, как изображено на рис. 9.2. Если в новой точке расположить лампочку, то она осветит удаляемые ребра старой оболочки; поэтому будем называть эти ребра освещенными из новой точки или просто освещенными. [17]
Определим выпуклую оболочку множества допустимых целочисленных точек ( решений) как минимальное выпуклое множество, содержащее все эти точки. Допустимыми решениями будет не вся область допустимых решений, находящаяся внутри и на границе выпуклой оболочки, а лишь отдельные дискретные точки этой области, имеющие все целочисленные координаты. Целевая функция достигает оптимального значения в одной из вершин этой выпуклой оболочки, которая представляет собой одно из допустимых целочисленных решений. [18]
Внутренностью проекции выпуклой оболочки U на плоскость х, у будет некоторая выпуклая область О, ограниченная замкнутой выпуклой кривой у. Очевидно, что О - ( - уесть выпуклая оболочка множества Q на плоскости х, у. Граница выпуклой оболочки поверхности U состоит из трех частей: выпуклых поверхностей Ф, и Ф2, обращенных выпуклостями соответственно вверх и вниз, и замкнутого множества точек 5 на прямом цилиндре Z с образующими, параллельными оси г, и направляющей Y - Поверхности Ф1 и Ф2 над открытой областью О задаются выпуклыми функциями z ( х, у) и z ( х, у), первая из которых обращена выпуклостью вверх, а вторая - выпуклостью вниз. [19]
Выпуклая оболочка подмножества аффинного пространства - это пересечение всех содержащих его полупространств. Граница выпуклой оболочки компактной гладкой гиперповерхности без края может иметь особенности. Например, особенности границы выпуклой оболочки общей замкнутой кривой на плоскости исчерпываются разрывами второй производной. [20]
Простейшие особенности диффеоморфны под-графику квадрата расстояния от точки на плоскости до лежащей в ней полуплоскости. В окрестности типичной точки границы выпуклая оболочка общей компактной поверхности без края диффеоморфна замкнутому полупространству. Простейшие особенности возникают вдоль гладких кривых, а угловые - в отдельных точках границы выпуклой оболочки. [21]
Предположим противное, а именно что имеется вершина выпуклой оболочки р, не являющаяся максимумом ни при каком присваивании знаков координатам точек. Поместим начало системы координат в точку р и рассмотрим все 2d ортантов пространства Ed. Очевидно, что conv ( S) содержит внутри точку р и, следовательно, conv ( S) conv ( S), что противоречит предположению о принадлежности точки р границе выпуклой оболочки. [22]
 |
Ни одна точка треугольника не попадает внутрь заштрихованной области. [23] |
Тогда все три отрезка р р2, р рз и р2рз принадлежат одной и той же прямой /, а перпендикулярные этим отрезкам прямые, делящие их пополам, являются параллельными. Так как вершина v является точкой пересечения этих прямых, то и - бесконечно удаленная точка. Отсюда следует, что многоугольники V ( l), V ( 2) и 1 / ( 3) являются неограниченными. Согласно теореме 5.10, это значит, что точки pi, р2 и рз принадлежат границе выпуклой оболочки. Тем самым утверждение доказано. [24]
Страницы: 1 2