Таблица 1. Локальные числа, их предельные значения и соответствующие им локальные векторы у(^)
Локальное число s 2 4 6 7 9 11 13 17 20
Предельное значение ?4 ?3 ?3+?4 ?2 ?2 + ?4 ?2 + ?3 ? ? + ?3 ? + ?2
Вектор у^) / \ 1 1 / \ I ? 2 V ? / \ I ? 1? 2-1J Г?-1 1 2 V ? / \ I ?-1 1 1? 2-1 J (2?-11 1 2 ?2 J 2 ?-1 1 V 2 ?2 - 1 J з ?-1 1 V 3 ?2-1 J / \ з ?-2 ч 3?2-1 ,
С помощью локальных правил Ь можно задать послойный рост. Выберем в качестве затравки конечное множество Т фигур разбиения Я. Фигуры, Ь-соседние к фигурам из Т, но не входящие в Т, образуют первое окружение £%Ь(Т, 1). Саму затравку будем считать нулевым окружением ShL(T, 0). Фигуры, Ь-соседние к фигурам из £ЛЬ(Т, 1), но не входящие в 8кЬ(Т, 1) и &кЬ(Т, 0), образуют второе окружение £\(Т, 2). Повторяя этот процесс несколько раз, можем получить п-е окружение ShL(T, п). Заметим, что по определению окружения разных уровней п = 0, 1, 2, ... попарно не пересекаются.
На множестве фигур разбиения Рози можно ввести Ь-метрику dL(T1, Т2) - число фигур геодезической цепи из Ь-соседних фигур, т.е. цепи из наименьшего числа фигур, соединяющих Т1 и Т2. В терминах Ь-метрики п-е окружение ShL(T, п) можно записать в виде 5%Ь(Т, п) = {Т г е Я; dL(T, Т) = п}.
Введем еще понятие п-кластера С1Ь(Т, п) = {Тг е е Я; dL(T, Т) < п}, который, согласно определению, разлагается на содержащиеся в нем окружения С1Ь(Т, п) = ShL(T, 0) и ShL(T, 1) и ... и ShL(T, п). Число фигур в п-кластере С1Ь(Т, п) обозначим с1ь(Т, п).
Функцией Ь-сложности сЬ(п) разбиения Я, на котором заданы локальные правила Ь, называется количество различных, с точностью до параллельного переноса, п-кластеров С1Ь(Т, п), где Т пробегает множество всех фигур разбиения Я.
Локальные правила разбиения Я удобно задавать не на самих фигурах разбиения, а на множестве их параметров Р. Тогда локальные правила Ь можно представить как множество пар Ь = {(I, 8г); I = 1, 2, ..., /}, где I = [г, ^) - приложенные друг к другу такие полуинтервалы, что 11 и 12 и ... и I = = Р и любой полуинтервал I содержится в одном из трех полуинтервалов 1(Я) = [0, ?2), 1(0) = [?2, ?), 1(В) = [? + ?2, 1); 8 г = {^ п, sа, ...} - конечный набор локальных сдвигов s у из параметризации, определенной табл. 2. Если окажется, что 8 г пусто, то фигуры Т(г) с параметрами г из I не имеют Ь-соседних фигур. Далее, когда целесообразно, будем считать пары (I , 8 г), определяющие локальные правила Ь, разбитыми на пары (I, s где s у е 8г.
Локальные правила Ь назовем сепарабельны-ми, если различные пары (I, 8) и (Т/-, 8у), IФу, задают разные, с точностью до параллельного переноса, 1-кластеры. Из определения следует, что для сепарабельных локальных правил значение функции Ь-сложности сь(1) = /, т.е. она равна числу полуинтервалов I в Ь.
Отметим особо, что саму параметризацию разбиения Я, определяемую табл. 1 и 2, можно рассматривать как максимальные локальные
Ы ?4 + ?5)
TG( ?2 + ?4)
Тя( ?4)
Тя( ?3 + ?4)
Рис. 1. Одиннадцать различных локальных окружений в разбиении Рози и порождающая их 1-корона
Crn(TЯGB, 1).
Таблица 2. Полуинтервалы 11 типов локальных окружений фигур в разбиении Рози
Тип фигуры Полуинтервал Локальные числа
TR [0, q5) 2, 4, 6, 7, 9, 11, 20
[q5, q4) 2, 4, 6, 7, 9, 11, 20
[q4, q4 + q5) -2, 2, 4, 6, 7, 9, 20
[q4 + q5, q3) -2, 2, 4, 6, 7, 9, 17, 20
[q3, q3 + q5) -2, -4, 2, 4, 6, 7, 17
[q3 + q5, q3 + q4) -2, 2, -4, 4, 6, 7, 17
[q3 + q4, q2) -2, -4, -6, 2, 4, 6, 17
TG [q2, q2 + q4) -2, -4, -6, -7, 4, 13
[q2 + q4, q2 + q3) -4, -6, -7, -9, 11, 13
[q2 + q3, q) -4, -6, -7, -9, -11, 11
Tb [q + q2, 1) -11, -13,-17, -20
правила Ь = Ьтах. Для локальных правил Ьтах п-е окружение ShL(T, п) совпадает с п-м координационным окружением фигуры Т, п-кластер SlL(T, п) называется п-короной Сгп(Т, п), а функцию Ь-сложности в этом случае будем называть функцией сложности разбиения Я и обозначать с(п).
ФУНКЦИЯ СЛОЖНОСТИ И РАЗБИЕНИЯ ПАРАМЕТРОВ
Прежде всего, условимся, что при любом выборе локальных правил сЬ(0) = 3, т.е. она равна количеству различных типов ТЯ, Та и Тв фигур в разбиении Я. При этом множество параметров Р разбивается по этим типам на три полуинтервала Р = [0, с2) и [с2, £) и [с + с2, 1). Это разбиение множества параметров обозначим РЬ(0) и назовем разбиением параметров нулевого уровня. Левые концы полуинтервалов t01 = 0, = с2, t03 = с + с2, очевидно, определяют разбиение РЬ(0) и соответствуют фигурам ТЯ(0), Тс(^2), Тв(с + с2), каждая из которых касается двух других ( рис. 1).
Разбиение параметров п-го порядка РЬ(п) определяется полуинтервалами из Р, определяющими все различные, точностью до параллельного переноса, п-кластеры С1Ь(Т, п), где Т пробегает множество всех фигур разбиения Я. Разбиение РЬ(п) однозначно определяется конечным множеством левых концов полуинтервалов ^п1 = 0, tn3, ...}. Исходя из такого определения разбиений РЬ(п), заключаем, что Ь-сложность сЬ(п) совпадает с количеством полуинтервалов в разбиении
Рь(п).
Будем говорить, что локальные правила Ь удовлетворяют Я^В-условию, если множество левых концов полуинтервалов t12, ...} разбиения параметров РЬ(1) 1-го порядка совпадает с множеством левых концов полуинтервалов I] из Ь.
Для локальных правил L = {(I, Sj); i = 1, 2, ... l, j = 1, 2, ...} определим двойственные локальные правила L = {(Ii + Sj, -sij); i = 1, 2, ... l, j = 1, 2, ...}. В этих терминах удается доказать теорему.
Теорема 1. Если локальные правила L сепара-белъны и удовлетворяют RGB-условию, то справедливы следующие утверждения.
1. Имеет место равенство
cL(n) = cIl (Trgb, n) для всех n = 0, 1, 2, ...,
где правая часть есть количество фигур в n-кла-стере CIl (TRGB, n), выращенном из затравки TRGB = TR(0) и TG(q2) и TB(q + q2) по двойственным локальным правилам L.
2. Разные фигуры T из n-кластера CIl (Trgb, n)
имеют разные с точностью до параллельного переноса, n-кластеры ClL(T, n) и, таким образом, n-кластер CIl (Trgb, n) содержит представителей всех типов фигур T из R, которые порождают все cL(n) различных n-кластеров ClL(T, n) в разбиении R.
3. Параметры фигур n-кластера CIl (Trgb, n)
определяют левые концы полуинтервалов разбиения параметров PL(n) n-го порядка.
Следствием теоремы 1 является тот факт, что функцию L-сложности и многообразие n-кластеров ClL(T, n) разбиения R удобно исследовать путем послойного роста кластера CIl (Trgb, n) из затравки TRGB, состоящей из трех фигур разного типа, по двойственным локальным правилам L.
ФУНКЦИЯ СЛОЖНОСТИ ДЛЯ РАЗБИЕНИЯ РОЗИ
Рассмотрим на R максимальные локальные правила L = Lmax. Это означает, что 11 полуинтервалов Tj, I2, ... I11 и соответствующие им наборы локальных сдвигов S,- определяются табл. 1, 2, а L-соседними являются любые две соприкасающиеся фигуры. Как было отмечено выше, n-кластер ClL(T, n) в этом случае совпадает с n-короной Crn(T, n), образованной первыми n координационными окружениями фигуры T, а функция сложности c(n) принимает значения, равные количеству всех различных с точностью до параллельного переноса n-корон в разбиении R.
Локальные правила Lmax сепарабельны и удовлетворяют RGB-условию. Кроме того, они самодвойственны, т.е. Lmax = Lmax. Поэтому по теореме 1 получаем формулу c(n) = Crn(TRGB, n), выражающую функцию сложности разбиения R через количество фигур в n-короне Crn(TRGB, n), построенной из затравки, состоящей из фигур
TR(0), Tg(q2), Tb(q + Q2). Кроме того, также по теореме 1 «-корона Crn(TRGB, n) содержит представителей всех типов фигур из R, которые порождают все c(n) различных «-корон Crn(T, n) в разбиении R. При этом n-короны Crn(T, n) попарно различны для всех фигур T из n-короны Crn(TRGB, n).
Например, 1-корона Crn(TRGB, 1) содержит 11 фигур, поэтому при n = 1 значение функции сложности c(1) = 11, а все возможные 1-короны в разбиении R можно построить на основе фигур, входящих в 1-корону Crn(TRGB, 1). На рис. 1 представлен фрагмент разбиения R, содержащий 2-корону Crn(TRGB, 2). Жирной линией выделена 1-корона Crn(TRGB, 1). Для каждой из 11 фигур T этой 1-короны отдельно вынесена ее 1-корона Crn(T , 1).
В табл. 3 приведены значения функции сложности c(n) разбиения R для n < 12. Анализ этих значений показывает, что c(n) не является многочленом второй степени от n. Это - новое явление, так как до сих пор в тех случаях, когда для двумерных разбиений удавалось получить явную формулу для функции сложности c(n) [5], она представляла собой многочлен второй степени.
Чтобы описать асимптотическое поведение функции сложности при n —► го, воспользуемся одним результатом работы [10]: граница n-коро-ны Crn(TRGB, n), совпадающая с n-м координационным окружением ShL (TRGB, n) затравки TRGB,
содержится в е-окрестности центрально-симметричного восьмиугольника Pol, растянутого в n раз:
ShLmS Trgb, n )c( n • Pol )е,
где радиус окрестности е не зависит от n.
Число фигур в n-короне Crn(TRGB, n) при n —► го можно оценить как отношение площади n2SPol восьмиугольника Pol, растянутого в n раз, к средней площади ST = Arq + Agq2 + Abq3 одной фигуры в разбиении R. Здесь AR = q/(1 + q2), Ag = (1 - q)/(1 + q2) и AB = q2/(1 + q2) - частоты появления в разбиении R, а q, q2 и q3 - площади фигур TR, TG и TB соответственно. Площадь восьмиугольника Pol рассчитывается по его вершинам, координаты которых вычислены в [10].
Таким образом, учитывая пункт 1 теоремы 1, для функции сложности разбиения R удается доказать следующее утверждение.
Теорема 2. Для функции сложности c(n) разбиения Рози R выполняется асимптотическая формула
c(n) ~ kn2 при n -«- го,
Таблица 3. Значения функции сложности с(п) разбиения Рози для п < 12
n 0 1 2 3 4 5 6 7 8 9 10 11 12
c(n) 3 11 31 53 87 129 173 233 291 361 441 527 621
Таблица 4. Локальные правила L+, L- и L0 в разбиении R
Локальные правила Полуинтервалы Локальные числа сдвигов
L+ [0, Q4) 4, 6, 7, 11
[q4, q4 + q5) -2, 4, 6, 7
[q4 + q5, q3 + q4) -2, 4, 6, 7, 17
[q3 + q4, q2) -2, -6, 4, 6, 17
L_ [0, Q3) 2, 6, 7, 9, 20
[Q3, Q3 + Q4) 2, -4, 6, 7
[Q3 + Q4, Q2) 2, -4, -6, 6
L0 [0, Q3 + Q4) 6, 7
[Q3 + Q4, Q2) 6, -6
[Q2, Q) -6, -7
[Q + Q2, 1)
S
где коэффициент k = -P-' = 0.5(5 + 2q
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.