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

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

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

Максима́льный слой (англ. maximal layer) непустого конечного множества точек — набор точек этого множества, которые имеют в некотором смысле максимальные координаты.

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

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

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

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

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

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

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

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

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

Максимальный слой (англ. maximal layer) непустого конечного множества точек на плоскости — все максимальные точки этого множества.

Синонимы: максимумы (англ. maxima); первый максимальный слой (англ. first maximal layer); доминирующее подмножество (англ. dominance hull).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый максимальный слой также называют просто максимальным слоем множества, или доминирующим подмножеством.

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

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

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

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

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

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

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

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

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

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

$y_{1}>y_{2}>\cdots >y_{k}$.

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

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

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ = 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.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to algorithms (англ.). — Second Edition. — Cambridge, Massachusetts · London, England · Boston · Burr Ridge, IL · Dubuque, IA · Madison, WI · New York · San Francisco · St. Louis · Montréal · Toronto: The MIT Press (2), McGraw-Hill Book Company (9), 2001. — XXII+1017 p. — ISBN 0-262-03293-7 (hc. : alk. paper, MIT Press). — ISBN 0-07-013151-1 (McGraw-Hill).
• 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.
• Franco P. Preparata, Michael Ian Shamos. Computational geometry. An introduction (англ.) / editor David Gries. — New York : Springer-Verlag, 1985. — XII+390 p. — (Texts and Monographs in Computer Science). — ISBN 0-387-96131-3. — ISBN 3-540-96131-3.