Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
3.1. Предварительные сведения
Считая, что точки располагаются в d-мерном пространстве, будем использовать общепринятые обозначения для точек и ^-мерных векторов, выходящих из начала системы координат в Ed.
Начнем с рассмотрения понятия аффинного множества.
Определение 3.1. Пусть в Ed заданы k различных точек pi, Р2, ... , pk- Множество точек р таких, что р = щр1 + а2р2 + . . . + akpk
(a,eR, cti + a24- ... + ak=l), ( ' '
называются аффинным множеством, порожденным точками pi, р2, Pk, а р является аффинной комбинацией точек р\,р2, ¦ ¦¦ Pk.
Заметим, что аффинная комбинация представляет частный случай понятия линейной комбинации, возникающий при введении дополнительного условия ai + ... + a* = 1. В случае k=2 аффинное множество — это прямая, проходящая через две заданные точки. Очевидно, что аффинными множествами являются точки, прямые линии, плоскости, гиперплоскости и т. п., т. е. все объекты, с которыми связано интуитивное представление о «прямолинейности». В действительности термин прямолинейный объект является синонимом аффинного множества (наряду с термином «аффинное многообразие»). Между векторными подпространствами и аффинными множествами имеется взаимосвязь, состоящая в том, что каждое аффинное множество получается из некоторого векторного подпространства (линейного множества) в результате преобразования переноса (на некоторый фиксированный вектор). Например, в пространстве Е3 линейными множествами являются прямые линии и плоскости, проходящие через начало координат, и сама точка начала координат, в то время как аффинными множествами являются произвольные точки, прямые линии и плоскости.
Пусть в Ей заданы k точек ри р2, ..., Pk. Если (k — 1) векторов р2 — pi, ..., pk — Pi являются линейно независимыми, то эти точки называются аффинно независимыми. Интуитивно по-
116
Гл. 3. Выпуклые оболочки: основные алгоритмы
нятный смысл этого определения состоит в том, что мы выполняем параллельный перенос множества точек так, что одна из точек (в нашем случае р\) перемещается в начало координат, и проверяем линейную независимость получившегося множества векторов. Очевидно, что выбор точки, перемещаемой в начало координат, является несущественным. Если заданы k аффинно независимых точек р\,р2, Р>„ то они образуют аффинный базис (k—1)-мерного аффинного множества (т. е. размерность аффинного множества равна размерности линейного множества, из которого оно получается в результате переноса).
Определение 3.2. Пусть в пространстве Еа задано подмножество L. Аффинной оболочкой aff(L) множества L называется наименьшее аффинное множество, содержащее L.
Другими словами, для любой пары точек из L прямая, определяемая этими точками, целиком принадлежит aff(L). Так, например, аффинной оболочкой отрезка является прямая, аффинной оболочкой плоского многоугольника — плоскость и т. д.
Теперь перейдем к рассмотрению понятия выпуклого множества, порожденного конечным числом точек.
Определение 3.3. Пусть в пространстве Ed заданы k различных точек рь р2, . .., pk. Множество точек р = а,р, + а2р2 + ... ~\~ QfrPk
(а, eR, а7 > 0, а! + а2 + ... + ak = 1) { '
называется выпуклым множеством, порожденным точками pi, р2, ..., pk, а р называется выпуклой комбинацией р\, р2, ... , • •, Pk.
Вновь заметим, что понятие выпуклой комбинации является сужением понятия аффинной комбинации, получающимся в результате введения дополнительного условия а,- ^ 0, / = 1, 2, .. . ..., k. В случае k = 2 результирующим выпуклым множеством является отрезок, соединяющий заданные точки. Размерность выпуклого множества равна размерности его аффинной оболочки. Например, размерность плоского выпуклого многоугольника равна двум, так как его аффинной оболочкой является плоскость. Теперь можно ввести следующее важное понятие.
Определение 3.4. Пусть в пространстве Ed задано произвольное подмножество L точек этого пространства. Выпуклой оболочкой conv(L) подмножества L называется наименьшее выпуклое множество, содержащее L.
Далее мы будем иметь дело лишь со случаем, когда L содержит конечное число точек (что соответствует выпуклому множе-
3.1. Предварительные сведения
117
ству, порожденному конечным числом точек). Чтобы охарактеризовать структуру conv(L) конечного множества точек L, необходимо обобщить понятия выпуклого многоугольника и выпуклого многогранника.
Определение 3.5. Полиэдральным множеством в Ей называется пересечение конечного множества замкнутых полупространств (полупространство — это часть ЕЛ, расположенная по одну сторону некоторой гиперплоскости).
Заметим, что полиэдральное множество является выпуклым, так как полупространство является выпуклым и пересечение выпуклых множеств также является выпуклым множеством. В частности, выпуклые плоские многоугольники и трехмерные многогранники — как они определены в разд. 1.3.1 — являются примерами (конечных) полиэдральных множеств. В общем случае мы будем называть конечное rf-мерное полиэдральное множество выпуклым d-политопом (или, коротко, d-политопом, или просто политопом).
