Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Этот раздел не претендует на введение формальных определений геометрических понятий, используемых в данной книге; мы хотим только напомнить о понятиях, хорошо известных читателю, и ввести удобные обозначения.
Обозначим через Ed d-мерное евклидово пространство, т. е. пространство d-плексов (х\, ..., xd), состоящих из действитель-
ных чисел Xi, i = 1, ..., d, с расстоянием I 2j х\ ) ¦ Определим
теперь важнейшие объекты, рассматриваемые вычислительной геометрией.
Точка. Точкой р в пространстве Ей называется d-плекс {х\, ..., Xd). Эту точку можно интерпретировать также и как d-компонентный вектор, исходящий из начала координат в Ed, свободным концом которого является точка р.
Прямая, плоскость, линейное многообразие. Пусть даны две разные точки q\ и q2, принадлежащие Еа; тогда линейная комбинация
aq1 + (l—a)q2 (а е= R) называется прямой в Ed. В общем случае для заданных k линейно независимых точек qiz . . ., qk, принадлежащих Ed (k^Ld), линейная комбинация
«i<7i + o.2q2 + .. . + ctft_,^ft_i + (1 - a! - ... - a*_,) qk
(a/€=R, /=1, k-l) называется линейным многообразием размерности (k— 1) в Еа.
Отрезок. Пусть даны две разные точки qt и q2, принадлежащие Еа, тогда линейная комбинация aqi + (1 — a)q2 при условии 0 ^ a sg: 1 определит выпуклую комбинацию для qt и q2, т. е.
a<7, + (l -a)q2 (oeR, 0<а<1).
Эта выпуклая комбинация описывает прямолинейный отрезок, соединяющей две точки: q{ и q2. Обычно этот отрезок обозначают как qxq2 (неупорядоченная пара).
1.3. Геометрические предпосылки
31
Выпуклое многообразие. Область D, принадлежащая пространству Еа, называется выпуклой, если для любой пары точек qx и q2 из D отрезок qxq2 целиком принадлежит D.
Можно доказать, что пересечением выпуклых областей является выпуклая область.
Выпуклая оболочка. Выпуклой оболочкой множества точек S, принадлежащих пространству Ed, называется граница наименьшей выпуклой области в Ed, которая охватывает S.
Многоугольник. Многоугольником в пространстве Е2 называется конечное множество отрезков, в котором каждый конец отрезка принадлежит ровно двум отрезкам и никакое подмножество этих отрезков не обладает указанным свойством. Эти отрезки называются сторонами (иногда ребрами), а их концы — вершинами многоугольника. (Заметим, что число сторон и число вершин совпадают.) Многоугольник с /V вершинами называется iV-угольником.
Многоугольник называется простым, если никакая пара непоследовательных его ребер не имеет общих точек. Простой многоугольник разбивает плоскость на две непересекающиеся области — внутреннюю (конечную) и внешнюю (бесконечную), разделенные этим многоугольником (теорема Жордана). (Замечание: в обиходе термин «многоугольник» часто употребляется для обозначения объединения границы и внутренней области.)
Простой многоугольник Р называется выпуклым, если его внутренняя область является выпуклым множеством.
Простой многоугольник Р называется звездным1), если существует точка г, не внешняя для Р, такая, что для всех точек р, принадлежащих Р, отрезок гр полностью лежит внутри Р. (Итак, любой выпуклый многоугольник звездный.) Множество точек z, обладающих указанным выше свойством, называется ядром Р. (Очевидно, выпуклый многоугольник совпадает со своим ядром.)
Планарный граф. Граф G = (V, Е) (где У —множество вершин, Е—множество ребер) называется планарным, если его можно уложить на плоскости без самопересечений (см. разд. 1.2.3.2). Прямолинейная укладка ребер планарного графа определяет разбиение плоскости, называемое планарным подразбиением или картой. Пусть v — число вершин, е — число ребер и / — число граней (включая единственную бесконечную
') Следует отличать его от звездчатого многоугольника, т. е. от самопересекающегося многоугольника, все стороны которого ^конгруэнтны и все углы конгруэнтны. — Прим. ред.
Г а. 1. Введение
грань) такого подразбиения. Эти три параметра связаны классической формулой Эйлера [Bollobas (1979)]
v-e + f = 2. (1.1)
Если мы, кроме того, знаем, что степень каждой вершины ^3, то в качестве простого упражнения можно доказать следующие неравенства:
у <-|<?, е<3и-6,
е<3/-6, ,<|е, (I-2)
у<2/-4, /<2и-4,
которые показывают, что v, е и / попарно пропорциональны. (Заметим, что три правых неравенства верны при всех условиях.)
Триангуляция. Планарное подразбиение называется триангуляцией, если все его конечные грани являются треугольниками. Триангуляцией конечного множества точек S называется плоский граф S, имеющий наибольшее возможное число ребер (другими словами, триангуляция S получена путем соединения точек из S непересекающимися прямолинейными отрезками так, что любая грань, лежащая внутри выпуклой оболочки S, является треугольником).
Полиэдр. Полиэдром в пространстве Е3 называется такое конечное множество плоских многоугольников, когда каждая сторона любого многоугольника принадлежит еще ровно одному из остальных многоугольников (смежным многоугольникам) и никакое из подмножеств этого множества многоугольников не обладает указанным свойством. Вершины и стороны этих многоугольников являются вершинами и ребрами данного полиэдра; сами многоугольники называются гранями полиэдра.
