Cтраница 2
Если А A, k - А и D - диаметр множества Л, то задача 1 превращается в известную задачу коммивояжера ( гл. [16]
Нормированное векторное пространство является метрическим пространством1), и нам можно определить диаметр множества. Диаметр множества в векторном пространстве равен диаметру замыкания этого множества. [17]
Если диаметр выпуклого многоугольника можно найти за время, меньшее чем 0 ( N2), то и диаметр множества можно будет найти быстрее, чем за 0 ( N2) операций. [18]
Теорему 6.2.1 можно вывести из теоремы 6.2.2, если воспользоваться равенством трансфинитного диаметра и конформного радиуса для односвязной области и заметить, что трансфинитный диаметр множества не меняется от добавления к этому множеству конечного числа изолированных точек. Полна [21] показал, что замкнутое ограниченное множество имеет тот же трансфинитный диаметр, что и его совершенное ядро. [19]
Как мы уже указывали, все это рассуждение опирается лишь на условия а), Ь) и с), которым удовлетворяют ФА - Малость диаметров множеств FJ, о которых шла речь в формулировке леммы, служила лишь для построения множеств ФА, обладающих свойствами, необходимыми в процессе доказательства. [20]
Поскольку равномерно непрерывна, существует подразделение Ю комплекса К, обладающее тем свойством, что cUcwn ( f ( 6 ty Ссх для любого 5 - с / (, где, через обозначен диаметр множества. [21]
Бросающееся в глаза различие в степени трудности задач 87 а) и б) создает плохие перспективы при попытках перенесения результатов этих задач на общий случай - мерного евклидова пространства1), И действительно, общая задача определения наибольшего возможного числа Nk ( n) диаметров п-точечного множества расположенного в k - мерном ( евклидовом) пространстве, не решена до сих пор, - и пока даже не видно никаких обнадеживающих подходов к решению этой задачи. [22]
Помимо формул N % ( n) n и Ns ( n) 2n - 2 ( результаты задачи 87), мы знаем лишь, что Ni ( n) 1 при всех п ( эта формула не представляет ни малейшего интереса, ибо оценивается здесь число диаметров множества точек одной прямой. [23]
Нормированное векторное пространство является метрическим пространством1), и нам можно определить диаметр множества. Диаметр множества в векторном пространстве равен диаметру замыкания этого множества. [24]
Положим se Л ( 31 ( с), 1 / 8) и Я К № ( с), 1 / 8), где А и К определены в лемме С. Поскольку диаметр множества U [ c ] ( se) не превосходит 2 - ЗД. [25]
Это преобразование эффективно отображает число из множества А в точку первого квадранта, лежащую на единичной окружности, и число из множества В в точку третьего квадранта. Отсюда немедленно следует, что диаметр множества точек на окружности равен 2 тогда и только тогда, когда множества А и В имеют непустое пересечение. [26]
Последовательность К - это последовательность множеств, вложенных одно в другое. Поэтому для сходимости последовательности х нам достаточно показать, что диаметр множеств АГ1пгг стремится к нулю при i - оо. [27]
Множества, для которых хаусдорфова размерность строго больше топологической размерности, называются фрактальными множествами, или фракталами. При этом предполагается, что множество принадлежит n - мерному евклидову пространству или многообразию, и диаметр покрывающего множества вычисляется в метрике этого пространства или многообразия. Поэтому определение фрактала требует фиксации метрики. [28]
Очевидно, что процесс оптимизации будет завершен за конечное число шагов. Из его описания видно, что он является процедурой локальной оптимизации, которая направлена на уменьшение максимального из диаметров множеств, полученных при разбиении. [29]
Хотя евклидово минимальное остовное дерево множества точек на плоскости может быть построено за оптимальное время, построение ЕМОД в пространствах более высокой размерности, вообще говоря, остается открытой задачей. Используя геометрическую природу задачи, Яо [ Yao ( 1982)) разработал алгоритм построения ЕМОД множества из N точек в d - мерном пространстве за время Т ( N, d) Q ( N2 - a ( d) ( logN) l - a ( d)), где a ( d) 2 - ( d 1), имеющий оценку 0 ( N ( logN) 1 - 8) для d 3 ( этот метод тесно связан с алгоритмом Яо для определения диаметра множества точек ( см. разд. [30]