8.1. Положение главы и постановка задачи

Оператор Merge является ключевым элементом конструктивной схемы псевдоэллипсоидов высших порядков. В главах 4–6 показано, что итерационная схема

I_{k+1}(x) = Merge(C_{R_k}(I_k(x))), k = 2, 3, …, n−1,

порождает всё семейство Ω_n. На каждом шаге оператор смещения–отражения C_{R_k} применяется к текущему интервальному состоянию I_k(x) и удваивает число формальных компонент. Однако результат C_{R_k}(I_k(x)) не является каноническим объектом: соседние компоненты могут пересекаться, соприкасаться или содержать одна другую. Без нормализации последующие операции теряют однозначность, а число формальных компонент растёт экспоненциально без отражения реальной геометрии.

Цель настоящей главы — формализовать оператор Merge как нормализующее отображение на множестве конечных объединений замкнутых интервалов в [0, +∞), доказать его корректность (Теорема 8.1) и установить его базовые алгебраические свойства: идемпотентность, монотонность относительно вложения и совместимость с объединением (Предложение 8.2). Дополнительно устанавливается единственность канонического представления (Следствие 8.3).

Все утверждения формулируются на уровне одномерных интервальных состояний; распространение на пространственное множество Ω_n обеспечивается покоординатным применением Merge по каждому срезу x = const и обсуждается в главе 5.

8.2. Базовые объекты: класс ℐ

Обозначим через ℐ класс всех конечных объединений замкнутых интервалов в [0, +∞):

ℐ = { U ⊂ [0, +∞) : U = ⋃_{j=1}^{N} [αⱼ, βⱼ], N ∈ ℕ, 0 ≤ αⱼ ≤ βⱼ < +∞ }.

Допускаются вырожденные интервалы вида [α, α] (одиночные точки), пересекающиеся пары [αⱼ, βⱼ] ∩ [α_i, β_i] ≠ ∅ при j ≠ i, и любой порядок интервалов в исходном списке. Пустое множество ∅ также относится к ℐ как случай N = 0.

Множество U ∈ ℐ называется представленным в каноническом виде, если выполнены три условия:

(К1) интервалы в списке попарно дизъюнктны: [αⱼ, βⱼ] ∩ [α_i, β_i] = ∅ при j ≠ i;

(К2) интервалы не соприкасаются: βⱼ < α_{j+1} для всех j = 1, …, N−1;

(К3) интервалы упорядочены по возрастанию левого конца: α₁ < α₂ < … < α_N.

Условие (К2) усиливает (К1): даже соприкасающиеся интервалы [α, β] и [β, γ], формально дизъюнктные только в одной точке β, объединяются в один интервал [α, γ]. Это согласовано с тем, что для построения тела вращения Ω_n физически различимыми являются только интервалы, разделённые ненулевым зазором.

Канонический вид однозначен: фиксированное множество точек U ⊂ [0, +∞), являющееся конечным объединением замкнутых интервалов, имеет единственное представление в виде списка ([α₁, β₁], …, [α_N, β_N]), удовлетворяющего (К1)–(К3). Этот факт оформляется как Следствие 7.3.

8.3. Определение оператора Merge

Определение 8.1. Оператор Merge : ℐ → ℐ ставит в соответствие произвольному элементу U ∈ ℐ его каноническое представление, рассматриваемое как множество точек в [0, +∞).

Конструктивно Merge задаётся следующей процедурой. Пусть U = ⋃_{j=1}^{N} [αⱼ, βⱼ] — произвольное представление.

Шаг 1. Упорядочить пары (αⱼ, βⱼ) по возрастанию αⱼ; при равных αⱼ — по возрастанию βⱼ.

Шаг 2. Положить [a₁, b₁] = [α₁, β₁] и для j = 2, …, N выполнить:

если αⱼ ≤ b_{cur}, обновить b_{cur} := max(b_{cur}, βⱼ); иначе зафиксировать текущий интервал [a_{cur}, b_{cur}] в выходной список и начать новый: [a_{cur}, b_{cur}] := [αⱼ, βⱼ].

Шаг 3. Зафиксировать последний интервал в выходной список.

Результирующий список ([a₁, b₁], …, [a_M, b_M]) с M ≤ N удовлетворяет условиям (К1)–(К3) и определяет множество Merge(U) ⊂ [0, +∞) как объединение этих интервалов.

Заметим, что Merge действует на множество точек U, а не на конкретное представление U в виде списка интервалов: два различных представления одного и того же множества дают один и тот же результат. Это позволяет рассматривать Merge как корректно определённую функцию на ℐ.

8.4. Теорема о корректности Merge

Теорема 8.1 (корректность Merge). Оператор Merge : ℐ → ℐ обладает следующими свойствами:

(А) для любого U ∈ ℐ множество Merge(U) совпадает с U как подмножество [0, +∞);

(Б) Merge(U) представлено в каноническом виде (К1)–(К3);

(В) количество компонент M в каноническом представлении Merge(U) удовлетворяет неравенству M ≤ N, где N — число интервалов в исходном представлении U; равенство достигается тогда и только тогда, когда исходное представление уже было каноническим;

(Г) результат Merge(U) не зависит от выбора исходного представления множества U.

Доказательство.

(А) Конструкция Merge не добавляет и не удаляет ни одной точки из U. На каждом шаге процедуры точка x ∈ [0, +∞) принадлежит выходному списку тогда и только тогда, когда она принадлежит хотя бы одному из исходных интервалов [αⱼ, βⱼ]. Действительно, при слиянии αⱼ ≤ b_{cur} новый интервал [a_{cur}, max(b_{cur}, βⱼ)] содержит и старый [a_{cur}, b_{cur}], и новый [αⱼ, βⱼ] полностью, поскольку αⱼ ≥ a_{cur} (по упорядоченности) и αⱼ ≤ b_{cur} (по условию слияния). При несовпадении αⱼ > b_{cur} новый интервал [αⱼ, βⱼ] добавляется в выходной список как отдельный, без изменения предыдущего. Следовательно, Merge(U) и U как множества точек совпадают.

(Б) Условие (К3) выполнено по построению: интервалы добавляются в выходной список строго в порядке возрастания левого конца. Условие (К2), а с ним и (К1), выполнено по правилу слияния: новый интервал [αⱼ, βⱼ] открывается только при αⱼ > b_{cur}, то есть всегда строго после правого конца предыдущего. Следовательно, b_{cur} < αⱼ для всех соседних пар выходного списка, что есть в точности (К2).

(В) Каждое выполнение шага слияния (αⱼ ≤ b_{cur}) уменьшает число компонент на единицу по сравнению с исходным числом. Если исходное представление каноническое, то для всех j ≥ 2 выполняется α_{j} > b_{j−1}, слияний не происходит, и M = N. Если хотя бы для одной пары соседних интервалов нарушено (К2) или (К1), происходит хотя бы одно слияние, и M < N.

(Г) Пусть U = ⋃{j=1}^{N} [αⱼ, βⱼ] и U = ⋃{i=1}^{N’} [α’_i, β’_i] — два различных представления одного и того же множества точек U. Применим к каждому из них процедуру Merge и обозначим результаты Merge(U) и Merge’(U) соответственно. Оба удовлетворяют (К1)–(К3) и совпадают с U как множества точек. Покажем, что в этом случае они имеют одинаковое число компонент и одинаковые интервалы.

Действительно, замкнутое множество U ⊂ [0, +∞), являющееся конечным объединением замкнутых интервалов, распадается единственным образом на максимальные замкнутые связные компоненты. Каждая такая компонента есть замкнутый интервал. Их число конечно. Условия (К1)–(К3) означают в точности, что список интервалов канонического представления есть упорядоченный список максимальных связных компонент U. Этот список однозначно определяется самим множеством U и не зависит от представления.

Следовательно, Merge(U) = Merge’(U) как упорядоченные списки интервалов, в частности как множества точек. ∎

8.5. Алгебраические свойства Merge

Предложение 8.2. Оператор Merge обладает следующими алгебраическими свойствами:

(а) идемпотентность: Merge(Merge(U)) = Merge(U) для любого U ∈ ℐ;

(б) монотонность: если U ⊆ V, то Merge(U) ⊆ Merge(V);

(в) совместимость с объединением: Merge(U ∪ V) = Merge(Merge(U) ∪ Merge(V)) для любых U, V ∈ ℐ.

Доказательство.

(а) По пункту (А) Теоремы 8.1 Merge(U) совпадает с U как множество точек, и по пункту (Б) представлено в каноническом виде. Применение Merge к каноническому представлению по пункту (В) не производит ни одного слияния и возвращает тот же список интервалов. Следовательно, Merge(Merge(U)) = Merge(U).

(б) Применение Merge не меняет точечного состава множества (пункт (А) Теоремы 8.1). Поэтому Merge(U) = U и Merge(V) = V как множества точек, и из U ⊆ V непосредственно следует Merge(U) ⊆ Merge(V).

(в) Поскольку Merge не меняет точечного состава, имеем Merge(U) ∪ Merge(V) = U ∪ V как множества точек. Применение Merge к обеим сторонам даёт Merge(Merge(U) ∪ Merge(V)) = Merge(U ∪ V). ∎

Заметим, что свойства (а)–(в) являются непосредственными следствиями определения и того, что Merge есть оператор канонизации, а не самостоятельной нетривиальной алгебраической структуры. Они оформлены как Предложение, а не Теорема, чтобы отразить их выводный характер.

8.6. Единственность канонического представления

Следствие 8.3 (единственность канонического представления). Для любого U ∈ ℐ существует ровно одно представление в виде списка ([α₁, β₁], …, [α_M, β_M]), удовлетворяющее условиям (К1)–(К3). Это представление совпадает с упорядоченным списком максимальных замкнутых связных компонент множества U.

Доказательство. Существование установлено в пункте (Б) Теоремы 8.1: процедура Merge строит такое представление по любому исходному. Единственность установлена в пункте (Г): любое каноническое представление есть упорядоченный список максимальных связных компонент U, а такой список определяется самим множеством U однозначно. ∎

Это следствие имеет конструктивное значение. Оно гарантирует, что в итерационной схеме главы 5 после каждого применения Merge интервальное состояние I_k(x) представлено в фиксированной форме, не зависящей от истории вычислений. Это позволяет однозначно сравнивать результаты, полученные при разных порядках обхода ветвей C_{R_k}, и обеспечивает воспроизводимость численных реализаций.

8.7. Совместимость Merge с оператором C_R

Помимо алгебраических свойств самого оператора Merge, для итерационной схемы существенна его согласованность с оператором смещения–отражения C_R, введённым в главе 4. Эта согласованность устанавливается следующим утверждением.

Предложение 8.4 (совместимость с C_R). Для любого U ∈ ℐ и любого R > 0 выполняется:

Merge(C_R(U)) = Merge(C_R(Merge(U))).

Доказательство. Оператор C_R линеен в смысле объединения: для любого представления U = ⋃ⱼ [αⱼ, βⱼ] имеем

C_R(U) = ⋃ⱼ C_R([αⱼ, βⱼ]),

где каждое слагаемое C_R([αⱼ, βⱼ]) — объединение не более чем двух замкнутых интервалов. Это означает, что C_R(U) ∈ ℐ и точечный состав C_R(U) определяется точечным составом U. Поскольку Merge не меняет точечного состава (пункт (А) Теоремы 8.1), точечный состав C_R(Merge(U)) совпадает с точечным составом C_R(U). Применение Merge к обеим сторонам даёт требуемое равенство. ∎

Следствие 8.4 имеет конструктивное значение: оно показывает, что в итерационной схеме можно эквивалентно выполнять Merge до или после применения C_R. На практике Merge применяется после C_R, поскольку именно тогда возникают потенциальные пересечения и соприкосновения, требующие канонизации. Однако теоретически результат итерации не зависит от того, проводится ли промежуточная канонизация на каждом шаге, или Merge применяется только в конце последовательности.

8.8. Граничные случаи

Для полноты рассмотрим поведение Merge на граничных конфигурациях.

Случай пустого множества. Если U = ∅, процедура Merge возвращает пустой список, и Merge(∅) = ∅. Все свойства (А)–(Г) Теоремы 8.1 выполнены тривиально.

Случай одиночного интервала. Если U = [α, β] с α ≤ β, исходное представление уже каноническое, и Merge(U) = U. Свойство (В) даёт M = N = 1.

Случай вырожденного интервала. Если U содержит вырожденный интервал [α, α] (одиночную точку), процедура Merge обрабатывает его так же, как невырожденный: при αⱼ ≤ b_{cur} точка поглощается текущим интервалом; при αⱼ > b_{cur} становится новой компонентой. Это согласовано с тем, что в схеме главы 5 одиночные точки возникают как граничные случаи (например, при d(x) = 0 в окрестности круговых рёбер регрессии).

Случай соприкасающихся интервалов. Если в исходном представлении присутствуют интервалы [α, β] и [β, γ] с общей точкой β, процедура Merge сливает их в один интервал [α, γ]. Условие (К2) (строгое неравенство β < α_{j+1}) исключает соприкосновение в каноническом представлении. Это согласовано с физическим смыслом: интервалы, разделённые нулевым зазором, рассматриваются как одна полость.

Случай вложенных интервалов. Если [αⱼ, βⱼ] ⊆ [α_i, β_i] при j ≠ i, процедура Merge поглощает вложенный интервал внешним. Это автоматически обеспечивается правилом обновления b_{cur} := max(b_{cur}, βⱼ).

Все перечисленные граничные случаи корректно обрабатываются процедурой и не требуют специальных оговорок в итерационной схеме.

8.9. Вычислительная сложность

Процедура Merge, описанная в разделе 8.3, состоит из сортировки N исходных пар (αⱼ, βⱼ) и линейного прохода по упорядоченному списку. Сортировка выполняется за O(N log N), линейный проход — за O(N). Общая сложность одного применения Merge:

T_Merge(N) = O(N log N).

В итерационной схеме главы 5 на k-м шаге число формальных компонент N_k(x) ≤ 2^{k−2}. Полная сложность построения интервального состояния I_n(x) для одного фиксированного x составляет:

T_total(n, x) = O(2^{n−2} · (n−2)) = O(n · 2^n).

При типичных значениях n ≤ 5, используемых в иллюстрациях и расчётах объёмов, это даёт от 4 до 80 элементарных операций на одно сечение, что практически незначимо. При больших n (n ≥ 8) экспоненциальный рост числа формальных ветвей становится заметным, и реализация требует оптимизаций: раннего обнаружения слияний, отсечения вырожденных компонент, рекурсивного применения Merge на промежуточных шагах. Эти вопросы относятся к вычислительной реализации и обсуждаются в приложении Б.

8.10. Связь с теорией множеств и морфологическим анализом

Оператор Merge как канонизация конечного объединения замкнутых интервалов в одномерной числовой прямой относится к классической области вычислительной геометрии и математической морфологии. В терминах общей теории множеств он эквивалентен взятию объединения и последующему разложению на максимальные связные компоненты — операции, корректно определённой для любого замкнутого множества с конечным числом компонент.

В терминах математической морфологии Серра оператор Merge можно рассматривать как частный случай канонической нормализации замкнутого множества: всякое замкнутое множество в ℝⁿ с конечным числом компонент имеет однозначное представление в виде упорядоченного объединения связных компонент. Для одномерного случая такое представление принимает особенно простую форму — последовательность непересекающихся замкнутых интервалов, упорядоченных по возрастанию.

Таким образом, оператор Merge в настоящей теории не вводит новой математической конструкции, а адаптирует известную операцию канонизации к специфике итерационной схемы I_{k+1} = Merge(C_{R_k}(I_k)). Его роль — гарантировать, что после каждого применения оператора смещения–отражения C_R результирующее интервальное состояние представлено в фиксированной, воспроизводимой и теоретически однозначной форме.

8.11. Итоги главы

В настоящей главе формально определён оператор Merge как канонизирующее отображение на классе ℐ конечных объединений замкнутых интервалов в [0, +∞). Доказаны:

– Теорема 8.1 о корректности Merge: сохранение точечного состава, существование и единственность канонического представления, монотонное убывание числа компонент;

– Предложение 8.2 об алгебраических свойствах Merge: идемпотентность, монотонность относительно вложения, совместимость с объединением;

– Следствие 8.3 о единственности канонического представления;

– Предложение 8.4 о совместимости Merge с оператором смещения–отражения C_R, обеспечивающее корректность итерационной схемы независимо от порядка промежуточных канонизаций.

Установленные свойства гарантируют, что итерационная схема I_{k+1}(x) = Merge(C_{R_k}(I_k(x))), введённая в главе 5, корректно работает на всём пространстве параметров и для любого конечного числа шагов n − 2. В частности, она однозначно определяет интервальное состояние I_n(x) как функцию исходных параметров (a, K, h₁, h) и списка offsets 𝒪 = (R₁, …, R_{n−2}), без зависимости от порядка обхода формальных ветвей C_R или от выбора промежуточных представлений.