Мы поможем в написании ваших работ!
ЗНАЕТЕ ЛИ ВЫ?
|
Метод построения пустого шара Делоне. Симплекс Делоне.
10.2 Разбиение Делоне
Воспользуемся пустым шаром, который мы будем перемещать, изменяя его размер так, чтобы он мог касаться точек системы {А}, но всегда оставался пустым. Этот мысленный образ, предложенный Делоне, помогает увидеть проблему с новой стороны и яснее понять взаимосвязь и единство разбиений Вороного и Делоне.
Итак, поместим в систему точек {А} пустой шар Делоне. Это всегда возможно, если выбрать шар достаточно малым. Начнем увеличивать его радиус, оставляя центр шара на месте. В какой-то момент поверхность шара встретит некоторую точку i системы {А}. Это обязательно произойдет, ибо в нашей системе нет неограниченно больших пустот. (Мы видим, что условия, наложенные ранее на систему {А}, действительно являются нужными.) Будем продолжать увеличивать радиус пустого шара так, чтобы точка i оставалась на его
Рис. 10.1 Разбиение Делоне двумерной системы точек. Симплексы Делоне заполняют пространство без щелей и наложений. Описанная сфера любого симплекса не содержит внутри себя других точек системы.
поверхности. Для этого придется двигать центр шара от точки i. Неважно, по какой траектории мы будем перемещать центр шара, рано или поздно шар достигнет
своей поверхностью другой точки системы {А}. Пусть это будет точка j. Продолжим увеличивать радиус нашего шара, сохраняя уже обе точки на его поверхности. Увеличиваясь, шар достигнет какой-то третьей точки системы, точки k. В двумерном случае наш "пустой круг" в этот момент зафиксируется, т.е. станет невозможным дальнейшее увеличение его радиуса при сохранении круга пустым. При этом мы выявляем элементарную двумерную конфигурацию трех точек (i,jk), определяющую некий треугольник, особенностью которого является то, что внутри его описанной окружности нет других точек системы {А}. В трехмерном пространстве шар не определяется тремя точками. Продолжим увеличивать его радиус, сохраняя все три найденные точки на его поверхности. Это будет возможно до тех пор, пока поверхность шара не встретится с четвертой точкой l системы. После этого движение и рост пустого шара станут невозможными. Найденные четыре точки (i,j,k,l) определяют вершины тетраэдра, который характерен тем, что внутри его описанной сферы нет других точек системы {А}. Такой тетраэдр называется симплексом Делоне.
Напомним, что симплексом в математике называют простейшую фигуру в пространстве данной размерности: тетраэдр — в трехмерном пространстве, треугольник — в двумерном. Во избежание недоразумений подчеркнем еще раз, что произвольная четверка точек системы, не лежащих в одной плоскости, всегда определяет некий симплекс. Однако он будет симплексом Делоне только в том случае, если его описанная сфера пуста. Другими словами, симплексы Делоне определяются особым выбором четверок точек в системе {А}.
|
