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

Максима́льный слой^{[комм 1]} непустого конечного множества точек на плоскости — все максимальные точки➤ этого множества. Формальное определение максимального слоя дано ниже➤^[1][2].

Синонимы: первый максимальный слой➤^[1][2]; доминирующее подмножество➤^{[3][комм 1]}.

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

Максимальная точка^{[комм 1]}, или максимальный элемент^{[комм 1]}, или максимум^{[комм 1]}, непустого конечного множества точек на плоскости — точка этого множества, над которой не доминирует ни одна другая точка этого множества^[1][2][5]. Другими словами, в первом квадранте максимальной точки (выше и правее) нет других точек^[6].

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

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

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

Понятие максимального слоя обобщается на пространство произвольной размерности➤. И даже на прямое произведение произвольного количества упорядоченных множеств^[7].

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

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

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

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

Точка ${\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}$^[1][2][7].

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

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

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

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

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

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

Лестница^{[комм 1]} — другое название всех максимальных точек ${\displaystyle \operatorname {M} (S)}$ плоского множества ${\displaystyle S\in \mathbb {E} ^{2}}$, поскольку их можно соединить в естественном порядке направо вниз в виде лестничной структуры отрезками, параллельными осям координат ${\displaystyle x}$ и ${\displaystyle y}$. Лестницей называется также плоское множество ${\displaystyle S\in \mathbb {E} ^{2}}$, совпадающее со своим максимальным слоем ${\displaystyle \operatorname {M} (S)}$^[4][2].

Предложение 2 [Kung, Luccio, Preparata (1975)]. При использовании модели деревьев сравнений произвольный алгоритм, решающий двумерную задачу о максимумах, имеет сложность ${\displaystyle \Omega (n\ln n)}$^[11].

Предложение 3. Максимальный слой множества из ${\displaystyle n}$ точек в евклидовом пространстве ${\displaystyle \mathbb {E} ^{d}}$ при ${\displaystyle d\geqslant 2}$ возможно отыскать за время ${\displaystyle O(n(\ln n)^{d-2})+O(n\ln n)}$^[12].

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

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

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

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

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

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

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

Рассмотрим множество точек ${\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})}$^[12].

Формальное определение максимальных слоёв — рекурсивное с использованием обозначений^[15].

Первый максимальный слой ${\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 }$; иначе слой не определён^[15][10].

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

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

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

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

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

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

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

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

Предложение 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}}$^[8].

Предложение 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'}$ имеют следующие свойства^[8]:

• при ${\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)\}}$.

1. ↑ ^{1 2 3 4 5 6 7 8 9 10 11 12 13} Имеется перевод на английский язык.

1. ↑ ^{1 2 3 4 5 6 7 8 9} Кормен Т. Алгоритмы: построение и анализ, 2011, Глава 33. Вычислительная геометрия. 33-2. Максимальные слои, с. 1080.
2. ↑ ^{1 2 3 4 5 6 7 8 9 10} Franck Nielsen. Output-sensitive peeling of convex and maximal layers, 1996, 3. Computing the first k maximal layers, p. 258.
3. ↑ ^{1 2 3 4} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.4. Упражнения, с. 225.
4. ↑ ^{1 2} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 5.8. Упражнения, с. 274.
5. ↑ ^{1 2 3 4 5 6 7 8} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.1.3. Задача о максимумах множества точек, с. 193.
6. ↑ ^{1 2 3} Bentley J. L. On the average number of maxima in a set of vectors and applications, 1978, 1. Introduction, с. 536.
7. ↑ ^{1 2 3 4 5 6 7 8} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.1.3. Задача о максимумах множества точек, с. 192.
8. ↑ ^{1 2 3 4 5} Кормен Т. Алгоритмы: построение и анализ, 2011, Глава 33. Вычислительная геометрия. 33-2. Максимальные слои, с. 1081.
9. ↑ Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.1.3. Задача о максимумах множества точек, с. 192; 202.
10. ↑ ^{1 2} Franck Nielsen. Output-sensitive peeling of convex and maximal layers, 1996, p. 255.
11. ↑ Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.1.3. Задача о максимумах множества точек, с. 195.
12. ↑ ^{1 2 3 4} Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.1.3. Задача о максимумах множества точек, с. 202.
13. ↑ Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.1.3. Задача о максимумах множества точек, с. 194.
14. ↑ Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.1.3. Задача о максимумах множества точек, с. 193—194.
15. ↑ ^{1 2} Кормен Т. Алгоритмы: построение и анализ, 2011, Глава 33. Вычислительная геометрия. 33-2. Максимальные слои, с. 1080—1081.
16. ↑ Bentley J. L. On the average number of maxima in a set of vectors and applications, 1978, 1. Introduction, с. 536.
17. ↑ Препарата Ф., Шеймос М. Вычислительная геометрия. Введение, 1989, 4.1.3. Задача о максимумах множества точек, с. 203.

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. Second edition (рус.) / пер. с англ. канд. техн. наук И. В. Красикова, Н. А. Ореховой, В. Н. Романова под ред. канд. техн. наук И. В. Красикова. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — 1290 с., ил. — 1000 экз. — ISBN 978-5–8459–0857–5 (рус.). — ISBN 0–07–013151–1 (англ.).
• Препарата Ф., Шеймос М.^[англ.]. Вычислительная геометрия. Введение = Franco P. Preparata, Michael Ian Shamos. Computational geometry. An introduction (рус.) / пер. с англ. С. А. Вичеса, М. М. Комарова под ред. Ю. М. Баяковского. — М.: «Мир», 1989. — 478 с., ил. — 10 000 экз. — ISBN 5-03-001041-6 (русск.). — ISBN 0-387-96131-3 (англ.).
• Bentley J. L.^[англ.], Kung H. T.^[англ.], Schkolnick M., Thompson C. D. On the average number of maxima in a set of vectors and applications (англ.) // Journal of the ACM : журнал / Editor-in-Chief: Venkatesan Guruswami^[англ.]. — New York City: Association for Computing Machinery, 1978. — October (vol. 25, iss. 4). — P. 536—543. — ISSN 0004-5411. — doi:10.1145/322092.32209.
• Franck Nielsen. Output-sensitive peeling of convex and maximal layers (англ.) // Information Processing Letters^[англ.] : журнал / editor: Leah Epstein. — Amsterdam: Elsevier, 1996. — Vol. 59, iss. 5. — P. 255—259. — ISSN 0020-0190. — doi:10.1016/0020-0190(96)00116-0.

Статья является кандидатом в добротные статьи с 17 июня 2025.