Максимальный слой (вычислительная геометрия)

Максима́льный слой^{[комм 1]} (англ. maximal layer^[1][2]) непустого конечного множества точек — набор точек этого множества, которые имеют в некотором смысле максимальные координаты➤➤^[3][1][4].

Не следует путать с выпуклым слоем.

Точки максимального слоя точечного множества на плоскости красного цвета

Задача о нахождении максимумов множества точек появляется в приложениях таких отраслях, как статистика, экономика (граница Парето^[англ.]), инженерное дело (граница Парето), многокритериальная оптимизация (граница Парето), исследование операций. Первоначально эту задачу описали как «задачу о плавающих курсах валют»➤^[4].

Имеется связь между задачей о максимумах и задачей о построении выпуклой оболочки➤^[5], вместе с тем между этими задачами имеются глубокое различие➤^[6].

Максимальные слои (англ. maximal layers^[1][2]) — один из двух способов разложить всё точечное множество на непересекающиеся слои➤. Другой способ — выпуклые слои, которые не зависят от системы координат^[3][7].

Максимальный слой на плоскости

Некоторая точка непустого конечного множества точек на плоскости доминирует над некоторой его точкой, если обе координаты первой точки соответственно не меньше обеих координат второй точки (это понятие зависит от системы координат)^[3][1][4].

Например, в множестве из четырёх точек ${\displaystyle \{(1,\,4),\,(2,\,1),\,(3,\,3),\,(4,\,2)\}}$ каждая из двух точек ${\displaystyle (3,\,3)}$ и ${\displaystyle (4,\,2)}$ доминирует над точкой ${\displaystyle (2,\,1)}$ (сравните с максимальными точками➤)^[8].

Обычно предполагают, явно или неявно, что никакие соответствующие координаты никаких двух точек данного множества не совпадают, то есть никакие две точки множества не лежат на прямой, параллельной одной из координатный осей^[9].

Максимальная точка (англ. maximal point^[1][2]), или максимальный элемент (англ. maximal element^[10]), или максимум (англ. maximum^[1][10]), или максимальный вектор (англ. maximal vector^[8]), непустого конечного множества точек на плоскости — точка этого множества, над которой не доминирует ни одна другая точка этого множества^[1][3][5][8]. Другими словами, в первом квадранте максимальной точки (то есть выше и правее этой точки при стандартном расположении осей) нет других точек данного множества^[8].

Максимальный слой в виде лестницы

Максимальный слой (англ. maximal layer^[1][2]) непустого конечного множества точек на плоскости — все максимальные точки➤ этого множества^[3][1].

Синонимы: максимумы (англ. maxima^[11])^[4]; первый максимальный слой (англ. first maximal layer^[1][2])➤^[3][1]; доминирующее подмножество (англ. dominance hull^[12])➤^[13].

Например, множество из четырёх точек ${\displaystyle \{(1,\,4),\,(2,\,1),\,(3,\,3),\,(4,\,2)\}}$ имеет 3 максимальные точки и одну немаксимальную ${\displaystyle (2,\,1)}$ (сравните с доминирующими точками➤)^[8].

Лестница (англ. staircase^[1][14]) — другое название всех максимальных точек плоского множества, поскольку их можно соединить в естественном порядке направо вниз в виде лестничной структуры отрезками, параллельными осям координат. Лестницей называется также плоское множество, совпадающее со своим максимальным слоем➤^[15][1].

Максимальный слой в пространстве

Понятие максимального слоя обобщается на вещественное евклидово пространство произвольной конечной размерности ${\displaystyle \mathbb {E} ^{d}}$ (и даже на прямое произведение ${\displaystyle U_{1}\times U_{2}\times \cdots \times U_{d}}$ произвольного конечного количества упорядоченных множеств)^[4].

Точка ${\displaystyle P(x_{1},\,x_{2},\,\dots ,\,x_{d})}$ непустого конечного множества ${\displaystyle S}$ из ${\displaystyle n>0}$ точек на евклидовой плоскости ${\displaystyle \mathbb {E} ^{d}}$ доминирует над его точкой ${\displaystyle Q(x'_{1},\,x'_{2},\,\dots ,\,x'_{d})}$, ${\displaystyle Q\prec P}$, если ${\displaystyle x'_{i}\leqslant x}$, ${\displaystyle i=1,\,2,\,\dots ,\,d}$^[3][1][4].

Отношение доминирования — описанное в предыдущем абзаце отношение «${\displaystyle \prec }$»^[4].

Отношение доминирования «${\displaystyle \prec }$» определяет на множестве ${\displaystyle S\subset \mathbb {E} ^{d}}$ частичный порядок при ${\displaystyle d>1}$^[5].

Максимальная точка, или максимальный элемент, или максимум, или максимальный вектор, непустого конечного множества точек ${\displaystyle S\subset \mathbb {E} ^{d}}$ — точка множества ${\displaystyle P\in S}$ такая, что не существует другой точки ${\displaystyle Q\in S}$, ${\displaystyle Q\neq P}$, такой, что ${\displaystyle P\prec Q}$^[3][1][5]. Другими словами, в первом ортанте максимальной точки («выше и правее») нет других точек^[8].

Задача о максимумах — нахождение всех максимумов данного множества для данного отношения доминирования^[5].

Максимальный слой ${\displaystyle \operatorname {M} (S)}$ непустого конечного множества ${\displaystyle S}$ точек в пространстве — все максимальные точки множества ${\displaystyle S}$^[3][1].

Обычно предполагают, явно или неявно, что соответствующие координаты ${\displaystyle x_{1},\,x_{2},\,\dots ,\,x_{d}}$ никаких двух точек множества ${\displaystyle S}$ не совпадают, то есть никакие две точки множества ${\displaystyle S\in \mathbb {E} ^{d}}$ не лежат на прямой, параллельной одной из координатный осей^[9].

Получены следующие оценки сложности:

• при использовании модели деревьев сравнений произвольный алгоритм, решающий двумерную задачу о максимумах, имеет сложность ${\displaystyle \Omega (n\ln n)}$ [Kung, Luccio, Preparata (1975)]^[16];
• максимальный слой множества из ${\displaystyle n}$ точек в евклидовом пространстве ${\displaystyle \mathbb {E} ^{d}}$ при ${\displaystyle d\geqslant 2}$ возможно отыскать за время ${\displaystyle O(n(\ln n)^{d-2})+O(n\ln n)}$^[17].

Задача о плавающих курсах валют

Соединение точек максимального слоя в виде лестницы на плоскости

Рассмотрим следующую забавную, как написали Ф. Препарата и М. Шеймос^[англ.], формулировку задачи о плавающих курсах валют, которая впервые привела к задаче о максимуме множества точек^[4].

Задача о плавающих курсах валют (англ. floating-currency problem^[11]). У каждого гражданина Эревона (страна в фантастических романах) есть пакет валюты, то есть некоторое количество денег в иностранной валюте. В Эревоне курсы этих иностранных валют колеблются в широком диапазоне. По закону республики Эревон в конце дня человек, имеющий пакет валюты наибольшей общей стоимости, провозглашается Королём Эревона. Возникает вопрос, как найти наименьшее подмножество граждан Эревона, которое со 100 % определённостью содержит всех потенциальных королей? Ответом является максимальный слой ${\displaystyle d}$-мерного пространства, где размерность пространства ${\displaystyle d}$ — количество валют, элемент пространства — гражданин Эревона, координаты элемента — стоимости соответствующих валют, которыми обладает человек^[4].

Связь с выпуклой оболочкой

Рассмотрим связь между задачей о максимумах и задачей о построении выпуклой оболочки^[5].

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

Суть связи заключается в следующем сходстве максимального слоя и границы выпуклой оболочки: оба этих понятия представляют «границу» множества точек ${\displaystyle S}$, причём максимальный слой даёт неполное представление этой «границы» и зависит от системы координат. Например, если задано некоторое множество точек ${\displaystyle S}$ на плоскости, то можно поставить столько задач о максимумах, сколько имеется квадрантов, то есть четыре, следующими образом. Любая из этих четырёх задач конструируется приписыванием одного из знаков «${\displaystyle +}$» или «${\displaystyle -}$» каждой из координат точек ${\displaystyle (x,\,y)}$ множества ${\displaystyle S}$. Обычной формулировке задачи соответствует комбинация знаков ${\displaystyle (+,\,+)}$. Поэтому взаимосвязь между этими задачами демонстрирует следующая теорема^[5].

Приведём следующую теорему^[5]:

если никакие две точки множества ${\displaystyle S}$ не лежат на прямой, параллельной одной из координатный осей (или хотя бы никакие три точки ${\displaystyle S}$ не лежат на одой прямой), то любая вершина границы выпуклой оболочки множества точек ${\displaystyle S}$ есть максимум по крайней мере при одном из четырёх присвоений знаков «${\displaystyle +}$» или «${\displaystyle -}$» координатам точек из ${\displaystyle S}$.

Содержание этого раздела обобщается на многомерное множество ${\displaystyle S\subset \mathbb {E} ^{d}}$^[18].

Отличие от выпуклой оболочки

На плоскости точка ${\displaystyle P}$ лежит вне выпуклых оболочек ${\displaystyle \operatorname {Conv} (S_{1})}$ и ${\displaystyle \operatorname {Conv} (S_{2})}$, но внутри выпуклой оболочки их объединения

Между задачей о максимумах и задачей о построении выпуклой оболочки имеются глубокое различие, связанное с понятием декомпозируемости^[17].

Рассмотрим множество точек ${\displaystyle S\subset \mathbb {E} ^{d}}$, представленное как объединение произвольных множеств ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$. Тогда произвольная точка плоскости ${\displaystyle P}$ есть максимум множества ${\displaystyle S\cup \{P\}}$ тогда и только тогда, когда ${\displaystyle P}$ есть максимум как множества ${\displaystyle S_{1}\cup \{P\}}$, так и ${\displaystyle S_{2}\cup \{P\}}$. С другой стороны, множество ${\displaystyle S}$ можно представить как объединение таких множеств ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$, что некоторая точка плоскости ${\displaystyle P}$ лежит внутри выпуклой оболочки ${\displaystyle \operatorname {Conv} (S)}$, тогда как эта точка ${\displaystyle P}$ лежит как вне ${\displaystyle \operatorname {Conv} (S_{1})}$, так и вне ${\displaystyle \operatorname {Conv} (S_{2})}$^[17].

Максимальные слои

Максимальные слои на плоскости. Точки одного слоя соединены. Степень доминирования множества равна 17

Рассмотрим способ разложить всё точечное множество на непересекающиеся максимальные слои. Формальное определение максимальных слоёв — рекурсивное с использованием обозначений^[19].

Первый максимальный слой ${\displaystyle M_{1}}$ множества ${\displaystyle S}$ из ${\displaystyle n>0}$ точек на плоскости состоит из максимальных точек множества ${\displaystyle S}$. Пусть ${\displaystyle S_{1}=S}$ и множество ${\displaystyle S_{i}}$, ${\displaystyle i>1}$, — это точки множества ${\displaystyle S}$ без всех точек максимальных слоёв с номерами ${\displaystyle 1,\,2,\,\dots ,\,i-1}$. Тогда ${\displaystyle i}$-й максимальный слой ${\displaystyle M_{i}}$ состоит из максимальных точек множества ${\displaystyle S_{i}}$, если множество точек ${\displaystyle S_{i}\neq \varnothing }$; иначе слой не определён^[19][7].

Первый максимальный слой также называют просто максимальным слоем➤^[3][1] множества, или доминирующим подмножеством^[13].

Степень доминирования точки множества — минимальное количество доминирующих подмножеств, при последовательном удалении которых удаляется сама точка^[13].

Степень доминирования множества — максимальная степень доминирования всех его точек^[13].

Максимальные слои — один из двух способов разложить всё точечное множество на непересекающиеся слои. Другой способ — выпуклые слои, которые не зависят от системы координат^[3][7].

Свойства максимальных слоёв

1 [Bentley, Kung, Schkolnick, Thompson (1978)^[20]]. Среднее количество максимальных точек ${\displaystyle \mu (n,\,d)}$ множества ${\displaystyle S}$ из ${\displaystyle n}$ точек в евклидовом пространстве ${\displaystyle \mathbb {E} ^{d}}$ равно

${\displaystyle \mu (n,\,d)=O((\ln n)^{d-1})}$,

но при условии, что координаты всех точек независимы и выбираются из одного и того же непрерывного распределения^[17].

2. При условии того, что координаты всех точек независимы и выбираются из одного и того же непрерывного закона распределения, все максимальные точки множества ${\displaystyle S}$ из ${\displaystyle n}$ точек в ${\displaystyle \mathbb {E} ^{d}}$ возможно найти за время, равное в среднем ${\displaystyle O(n)}$^[21].

Обычно предполагают, явно или неявно, что соответствующие координаты ${\displaystyle x_{1},\,x_{2},\,\dots ,\,x_{d}}$ никаких двух точек множества ${\displaystyle S}$ не совпадают, то есть никакие две точки множества ${\displaystyle S\in \mathbb {E} ^{d}}$ не лежат на прямой, параллельной одной из координатный осей^[9].

3. Если множество ${\displaystyle S}$ имеет ${\displaystyle k}$ непустых максимальных слоёв, причём ${\displaystyle y_{i}}$, ${\displaystyle i=1,\,2,\,\dots ,\,k}$, — ордината самой левой точки в слое ${\displaystyle M_{i}}$, то тогда

${\displaystyle y_{1}>y_{2}>\cdots >y_{k}}$^[9].

4. Дано: точечное множество ${\displaystyle S}$; точка ${\displaystyle (x,\,y)}$, лежащая левее любой точки множества ${\displaystyle S}$, причём её координата ${\displaystyle y}$ отлична от координат ${\displaystyle y}$ всех точек множества ${\displaystyle S}$; множество ${\displaystyle S'=S\cup \{(x,\,y)\}}$; все ${\displaystyle k}$ непустых максимальных слоёв множества ${\displaystyle S}$, причём ${\displaystyle y_{i}}$, ${\displaystyle i=1,\,2,\,\dots ,\,k}$, — ордината самой левой точки в слое ${\displaystyle M_{i}}$; ${\displaystyle j}$ — минимальный индекс такой, что ${\displaystyle y_{j}<y}$; если его нет, ${\displaystyle y<y_{k}}$, то ${\displaystyle j=k+1}$. Доказать: максимальные слои множества ${\displaystyle S'}$ имеют следующие свойства^[9]:

• при ${\displaystyle j\leqslant k}$ максимальные слои множеств ${\displaystyle S'}$ и ${\displaystyle S}$ совпадают, кроме слоя ${\displaystyle M_{j}}$ с крайней левой точкой ${\displaystyle (x,\,y)}$ в множестве ${\displaystyle S'}$;
• при ${\displaystyle j=k+1}$ первые ${\displaystyle k}$ максимальных слоёв множеств ${\displaystyle S'}$ и ${\displaystyle S}$ совпадают, а множество ${\displaystyle S'}$ имеет дополнительный максимальный слой ${\displaystyle M_{k+1}}$, состоящий из одной точки: ${\displaystyle M_{k+1}=\{(x,\,y)\}}$.