Алговики - Вклад [ru]

Участник:Aleksey Dumbay/QuickHull

2017-10-30T10:37:04Z

Aleksey Dumbay:

Алгоритм: QuickHull для двумерного случая

Автор статьи: [[Участник: Aleksey_Dumbay |Думбай А.Д. группа 317]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Построение выпуклой оболочки множества точек - задача построения минимального по вложенности выпуклого множества, содержащего все точки из исходного множества. В случае конечного числа точек на плоскости выпуклая оболочка описывается некоторым подмножеством точек, которые принадлежат этой выпуклой оболочке. В этом случае выпуклая оболочка представляет собой выпуклый многоугольник с вершинами из этого подмножества точек.

Алгоритм QuickHull<ref>Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). [http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf "The quickhull algorithm for convex hulls"]</ref> - алгоритм построения выпуклой оболочки множества точек в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае, где <math>N</math> - мощность множества точек. Алгоритм использует подход, аналогичный подходу QuickSort, разделяя исходное множество на некоторые подмножества, отсекая ненужные точки, после этого применяется рекурсивно к образовавшимся подмножествам, а потом объединяет их. В рамках этого алгоритма решаются две задачи - выделения подмножеств и объединения нескольких выпуклых оболочек вместе.

Есть несколько различных вариантов данного алгоритма, которые по-разному находят подмножества для рекурсивного обхода. Общая их идея заключается в выделении крайних точек и отсечении всех точек, что попали в образованный ими многоугольник. Остальные точки делятся на множества и обрабатываются рекурсивно. Так же существует вариант алгоритма, в котором рекурсивно находится наиболее удаленная от отрезка вершина, отсекается образованный треугольник, а к новым сторонам и разбившемуся множеству алгоритм применяется рекурсивно.<ref>[http://algolist.manual.ru/maths/geom/convhull/quickhull.php Пример реализации такого варианта]</ref>

На вход алгоритму подается множество точек на плоскости, на выходе - те точки, которые являются вершинами выпуклой оболочки.
== Математическое описание алгоритма ==
Выпуклое множество <math>A</math> для векторного пространства <math>\mathbb{V}</math> над <math>\mathbb{R}</math> - такое множество, что

<math>
\forall \textbf{x}, \textbf{y} \in A, \forall \alpha \in [0,1]: \textbf{x} \cdot \alpha + \textbf{y} \cdot (1 - \alpha) \in A
</math>.<ref>[http://www.machinelearning.ru/wiki/images/c/cc/MO17_seminar6.pdf Выпуклое множество]</ref>

Выпуклая оболочка множества точек <math>\mathbb{X}</math> - это такое выпуклое множество, которое содержит все точки из множества <math>\mathbb{X}</math> и при этом является минимальным по вложению. В случае <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math> выпуклая оболочка является многоугольником.

На вход алгоритму подается множество <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math>, которое описывает набор точек на плоскости, где каждая точка - вектор <math>(x,y)</math> где компоненты соответствуют координатам на плоскости в декартовой системе координат. <math>\mathbb{X} = \{a_1, a_2, \ldots, a_N\}</math>.
Алгоритм работает в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае.

Алгоритм строит упорядоченный набор из точек <math>x_{1}, x_{2}, \ldots, x_m </math>, которые образуют многоугольник <math>X_1X_2X_3\ldots X_m</math>, являющийся выпуклой оболочкой множества точек <math>\mathbb{X}</math>, где <math>x_i \in A</math>.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

[[en:Description of algorithm properties and structure]]

Участник:Aleksey Dumbay/QuickHull

2017-10-30T10:36:39Z

Aleksey Dumbay:

Алгоритм: QuickHull для двумерного случая

Автор статьи: [ Участник: Aleksey_Dumbay |Думбай А.Д. группа 317]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Построение выпуклой оболочки множества точек - задача построения минимального по вложенности выпуклого множества, содержащего все точки из исходного множества. В случае конечного числа точек на плоскости выпуклая оболочка описывается некоторым подмножеством точек, которые принадлежат этой выпуклой оболочке. В этом случае выпуклая оболочка представляет собой выпуклый многоугольник с вершинами из этого подмножества точек.

Алгоритм QuickHull<ref>Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). [http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf "The quickhull algorithm for convex hulls"]</ref> - алгоритм построения выпуклой оболочки множества точек в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае, где <math>N</math> - мощность множества точек. Алгоритм использует подход, аналогичный подходу QuickSort, разделяя исходное множество на некоторые подмножества, отсекая ненужные точки, после этого применяется рекурсивно к образовавшимся подмножествам, а потом объединяет их. В рамках этого алгоритма решаются две задачи - выделения подмножеств и объединения нескольких выпуклых оболочек вместе.

Есть несколько различных вариантов данного алгоритма, которые по-разному находят подмножества для рекурсивного обхода. Общая их идея заключается в выделении крайних точек и отсечении всех точек, что попали в образованный ими многоугольник. Остальные точки делятся на множества и обрабатываются рекурсивно. Так же существует вариант алгоритма, в котором рекурсивно находится наиболее удаленная от отрезка вершина, отсекается образованный треугольник, а к новым сторонам и разбившемуся множеству алгоритм применяется рекурсивно.<ref>[http://algolist.manual.ru/maths/geom/convhull/quickhull.php Пример реализации такого варианта]</ref>

На вход алгоритму подается множество точек на плоскости, на выходе - те точки, которые являются вершинами выпуклой оболочки.
== Математическое описание алгоритма ==
Выпуклое множество <math>A</math> для векторного пространства <math>\mathbb{V}</math> над <math>\mathbb{R}</math> - такое множество, что

<math>
\forall \textbf{x}, \textbf{y} \in A, \forall \alpha \in [0,1]: \textbf{x} \cdot \alpha + \textbf{y} \cdot (1 - \alpha) \in A
</math>.<ref>[http://www.machinelearning.ru/wiki/images/c/cc/MO17_seminar6.pdf Выпуклое множество]</ref>

Выпуклая оболочка множества точек <math>\mathbb{X}</math> - это такое выпуклое множество, которое содержит все точки из множества <math>\mathbb{X}</math> и при этом является минимальным по вложению. В случае <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math> выпуклая оболочка является многоугольником.

На вход алгоритму подается множество <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math>, которое описывает набор точек на плоскости, где каждая точка - вектор <math>(x,y)</math> где компоненты соответствуют координатам на плоскости в декартовой системе координат. <math>\mathbb{X} = \{a_1, a_2, \ldots, a_N\}</math>.
Алгоритм работает в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае.

Алгоритм строит упорядоченный набор из точек <math>x_{1}, x_{2}, \ldots, x_m </math>, которые образуют многоугольник <math>X_1X_2X_3\ldots X_m</math>, являющийся выпуклой оболочкой множества точек <math>\mathbb{X}</math>, где <math>x_i \in A</math>.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

[[en:Description of algorithm properties and structure]]

Участник:Aleksey Dumbay/QuickHull

2017-10-30T10:35:56Z

Aleksey Dumbay:

Алгоритм: QuickHull для двумерного случая

Автор статьи: [[Участник:Aleksey_Dumbay|Думбай А.Д. группа 317]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Построение выпуклой оболочки множества точек - задача построения минимального по вложенности выпуклого множества, содержащего все точки из исходного множества. В случае конечного числа точек на плоскости выпуклая оболочка описывается некоторым подмножеством точек, которые принадлежат этой выпуклой оболочке. В этом случае выпуклая оболочка представляет собой выпуклый многоугольник с вершинами из этого подмножества точек.

Алгоритм QuickHull<ref>Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). [http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf "The quickhull algorithm for convex hulls"]</ref> - алгоритм построения выпуклой оболочки множества точек в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае, где <math>N</math> - мощность множества точек. Алгоритм использует подход, аналогичный подходу QuickSort, разделяя исходное множество на некоторые подмножества, отсекая ненужные точки, после этого применяется рекурсивно к образовавшимся подмножествам, а потом объединяет их. В рамках этого алгоритма решаются две задачи - выделения подмножеств и объединения нескольких выпуклых оболочек вместе.

Есть несколько различных вариантов данного алгоритма, которые по-разному находят подмножества для рекурсивного обхода. Общая их идея заключается в выделении крайних точек и отсечении всех точек, что попали в образованный ими многоугольник. Остальные точки делятся на множества и обрабатываются рекурсивно. Так же существует вариант алгоритма, в котором рекурсивно находится наиболее удаленная от отрезка вершина, отсекается образованный треугольник, а к новым сторонам и разбившемуся множеству алгоритм применяется рекурсивно.<ref>[http://algolist.manual.ru/maths/geom/convhull/quickhull.php Пример реализации такого варианта]</ref>

На вход алгоритму подается множество точек на плоскости, на выходе - те точки, которые являются вершинами выпуклой оболочки.
== Математическое описание алгоритма ==
Выпуклое множество <math>A</math> для векторного пространства <math>\mathbb{V}</math> над <math>\mathbb{R}</math> - такое множество, что

<math>
\forall \textbf{x}, \textbf{y} \in A, \forall \alpha \in [0,1]: \textbf{x} \cdot \alpha + \textbf{y} \cdot (1 - \alpha) \in A
</math>.<ref>[http://www.machinelearning.ru/wiki/images/c/cc/MO17_seminar6.pdf Выпуклое множество]</ref>

Выпуклая оболочка множества точек <math>\mathbb{X}</math> - это такое выпуклое множество, которое содержит все точки из множества <math>\mathbb{X}</math> и при этом является минимальным по вложению. В случае <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math> выпуклая оболочка является многоугольником.

На вход алгоритму подается множество <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math>, которое описывает набор точек на плоскости, где каждая точка - вектор <math>(x,y)</math> где компоненты соответствуют координатам на плоскости в декартовой системе координат. <math>\mathbb{X} = \{a_1, a_2, \ldots, a_N\}</math>.
Алгоритм работает в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае.

Алгоритм строит упорядоченный набор из точек <math>x_{1}, x_{2}, \ldots, x_m </math>, которые образуют многоугольник <math>X_1X_2X_3\ldots X_m</math>, являющийся выпуклой оболочкой множества точек <math>\mathbb{X}</math>, где <math>x_i \in A</math>.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

[[en:Description of algorithm properties and structure]]

Участник:Aleksey Dumbay/QuickHull

2017-10-30T10:35:48Z

Aleksey Dumbay:

Алгоритм: QuickHull для двумерного случая
Автор статьи: [[Участник:Aleksey_Dumbay|Думбай А.Д. группа 317]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Построение выпуклой оболочки множества точек - задача построения минимального по вложенности выпуклого множества, содержащего все точки из исходного множества. В случае конечного числа точек на плоскости выпуклая оболочка описывается некоторым подмножеством точек, которые принадлежат этой выпуклой оболочке. В этом случае выпуклая оболочка представляет собой выпуклый многоугольник с вершинами из этого подмножества точек.

Алгоритм QuickHull<ref>Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). [http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf "The quickhull algorithm for convex hulls"]</ref> - алгоритм построения выпуклой оболочки множества точек в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае, где <math>N</math> - мощность множества точек. Алгоритм использует подход, аналогичный подходу QuickSort, разделяя исходное множество на некоторые подмножества, отсекая ненужные точки, после этого применяется рекурсивно к образовавшимся подмножествам, а потом объединяет их. В рамках этого алгоритма решаются две задачи - выделения подмножеств и объединения нескольких выпуклых оболочек вместе.

Есть несколько различных вариантов данного алгоритма, которые по-разному находят подмножества для рекурсивного обхода. Общая их идея заключается в выделении крайних точек и отсечении всех точек, что попали в образованный ими многоугольник. Остальные точки делятся на множества и обрабатываются рекурсивно. Так же существует вариант алгоритма, в котором рекурсивно находится наиболее удаленная от отрезка вершина, отсекается образованный треугольник, а к новым сторонам и разбившемуся множеству алгоритм применяется рекурсивно.<ref>[http://algolist.manual.ru/maths/geom/convhull/quickhull.php Пример реализации такого варианта]</ref>

На вход алгоритму подается множество точек на плоскости, на выходе - те точки, которые являются вершинами выпуклой оболочки.
== Математическое описание алгоритма ==
Выпуклое множество <math>A</math> для векторного пространства <math>\mathbb{V}</math> над <math>\mathbb{R}</math> - такое множество, что

<math>
\forall \textbf{x}, \textbf{y} \in A, \forall \alpha \in [0,1]: \textbf{x} \cdot \alpha + \textbf{y} \cdot (1 - \alpha) \in A
</math>.<ref>[http://www.machinelearning.ru/wiki/images/c/cc/MO17_seminar6.pdf Выпуклое множество]</ref>

Выпуклая оболочка множества точек <math>\mathbb{X}</math> - это такое выпуклое множество, которое содержит все точки из множества <math>\mathbb{X}</math> и при этом является минимальным по вложению. В случае <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math> выпуклая оболочка является многоугольником.

На вход алгоритму подается множество <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math>, которое описывает набор точек на плоскости, где каждая точка - вектор <math>(x,y)</math> где компоненты соответствуют координатам на плоскости в декартовой системе координат. <math>\mathbb{X} = \{a_1, a_2, \ldots, a_N\}</math>.
Алгоритм работает в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае.

Алгоритм строит упорядоченный набор из точек <math>x_{1}, x_{2}, \ldots, x_m </math>, которые образуют многоугольник <math>X_1X_2X_3\ldots X_m</math>, являющийся выпуклой оболочкой множества точек <math>\mathbb{X}</math>, где <math>x_i \in A</math>.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

[[en:Description of algorithm properties and structure]]

Участник:Aleksey Dumbay/QuickHull

2017-10-30T10:35:09Z

Aleksey Dumbay:

{{algorithm
| name = QuickHull
}}

Автор статьи: [[Участник:Aleksey Dumbay|Думбай А.Д. группа 317]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Построение выпуклой оболочки множества точек - задача построения минимального по вложенности выпуклого множества, содержащего все точки из исходного множества. В случае конечного числа точек на плоскости выпуклая оболочка описывается некоторым подмножеством точек, которые принадлежат этой выпуклой оболочке. В этом случае выпуклая оболочка представляет собой выпуклый многоугольник с вершинами из этого подмножества точек.

Алгоритм QuickHull<ref>Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). [http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf "The quickhull algorithm for convex hulls"]</ref> - алгоритм построения выпуклой оболочки множества точек в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае, где <math>N</math> - мощность множества точек. Алгоритм использует подход, аналогичный подходу QuickSort, разделяя исходное множество на некоторые подмножества, отсекая ненужные точки, после этого применяется рекурсивно к образовавшимся подмножествам, а потом объединяет их. В рамках этого алгоритма решаются две задачи - выделения подмножеств и объединения нескольких выпуклых оболочек вместе.

Есть несколько различных вариантов данного алгоритма, которые по-разному находят подмножества для рекурсивного обхода. Общая их идея заключается в выделении крайних точек и отсечении всех точек, что попали в образованный ими многоугольник. Остальные точки делятся на множества и обрабатываются рекурсивно. Так же существует вариант алгоритма, в котором рекурсивно находится наиболее удаленная от отрезка вершина, отсекается образованный треугольник, а к новым сторонам и разбившемуся множеству алгоритм применяется рекурсивно.<ref>[http://algolist.manual.ru/maths/geom/convhull/quickhull.php Пример реализации такого варианта]</ref>

На вход алгоритму подается множество точек на плоскости, на выходе - те точки, которые являются вершинами выпуклой оболочки.
== Математическое описание алгоритма ==
Выпуклое множество <math>A</math> для векторного пространства <math>\mathbb{V}</math> над <math>\mathbb{R}</math> - такое множество, что

<math>
\forall \textbf{x}, \textbf{y} \in A, \forall \alpha \in [0,1]: \textbf{x} \cdot \alpha + \textbf{y} \cdot (1 - \alpha) \in A
</math>.<ref>[http://www.machinelearning.ru/wiki/images/c/cc/MO17_seminar6.pdf Выпуклое множество]</ref>

Выпуклая оболочка множества точек <math>\mathbb{X}</math> - это такое выпуклое множество, которое содержит все точки из множества <math>\mathbb{X}</math> и при этом является минимальным по вложению. В случае <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math> выпуклая оболочка является многоугольником.

На вход алгоритму подается множество <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math>, которое описывает набор точек на плоскости, где каждая точка - вектор <math>(x,y)</math> где компоненты соответствуют координатам на плоскости в декартовой системе координат. <math>\mathbb{X} = \{a_1, a_2, \ldots, a_N\}</math>.
Алгоритм работает в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае.

Алгоритм строит упорядоченный набор из точек <math>x_{1}, x_{2}, \ldots, x_m </math>, которые образуют многоугольник <math>X_1X_2X_3\ldots X_m</math>, являющийся выпуклой оболочкой множества точек <math>\mathbb{X}</math>, где <math>x_i \in A</math>.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

[[en:Description of algorithm properties and structure]]

Участник:Aleksey Dumbay/QuickHull

2017-10-23T19:06:09Z

Aleksey Dumbay: Правки

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Построение выпуклой оболочки множества точек - задача построения минимального по вложенности выпуклого множества, содержащего все точки из исходного множества. В случае конечного числа точек на плоскости выпуклая оболочка описывается некоторым подмножеством точек, которые принадлежат этой выпуклой оболочке. В этом случае выпуклая оболочка представляет собой выпуклый многоугольник с вершинами из этого подмножества точек.

Алгоритм QuickHull<ref>Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). [http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf "The quickhull algorithm for convex hulls"]</ref> - алгоритм построения выпуклой оболочки множества точек в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае, где <math>N</math> - мощность множества точек. Алгоритм использует подход, аналогичный подходу QuickSort, разделяя исходное множество на некоторые подмножества, отсекая ненужные точки, после этого применяется рекурсивно к образовавшимся подмножествам, а потом объединяет их. В рамках этого алгоритма решаются две задачи - выделения подмножеств и объединения нескольких выпуклых оболочек вместе.

Есть несколько различных вариантов данного алгоритма, которые по-разному находят подмножества для рекурсивного обхода. Общая их идея заключается в выделении крайних точек и отсечении всех точек, что попали в образованный ими многоугольник. Остальные точки делятся на множества и обрабатываются рекурсивно. Так же существует вариант алгоритма, в котором рекурсивно находится наиболее удаленная от отрезка вершина, отсекается образованный треугольник, а к новым сторонам и разбившемуся множеству алгоритм применяется рекурсивно.<ref>[http://algolist.manual.ru/maths/geom/convhull/quickhull.php Пример реализации такого варианта]</ref>

На вход алгоритму подается множество точек на плоскости, на выходе - те точки, которые являются вершинами выпуклой оболочки.
== Математическое описание алгоритма ==
Выпуклое множество <math>A</math> для векторного пространства <math>\mathbb{V}</math> над <math>\mathbb{R}</math> - такое множество, что

<math>
\forall \textbf{x}, \textbf{y} \in A, \forall \alpha \in [0,1]: \textbf{x} \cdot \alpha + \textbf{y} \cdot (1 - \alpha) \in A
</math>.<ref>[http://www.machinelearning.ru/wiki/images/c/cc/MO17_seminar6.pdf Выпуклое множество]</ref>

Выпуклая оболочка множества точек <math>\mathbb{X}</math> - это такое выпуклое множество, которое содержит все точки из множества <math>\mathbb{X}</math> и при этом является минимальным по вложению. В случае <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math> выпуклая оболочка является многоугольником.

На вход алгоритму подается множество <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math>, которое описывает набор точек на плоскости, где каждая точка - вектор <math>(x,y)</math> где компоненты соответствуют координатам на плоскости в декартовой системе координат. <math>\mathbb{X} = \{a_1, a_2, \ldots, a_N\}</math>.
Алгоритм работает в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае.

Алгоритм строит упорядоченный набор из точек <math>x_{1}, x_{2}, \ldots, x_m </math>, которые образуют многоугольник <math>X_1X_2X_3\ldots X_m</math>, являющийся выпуклой оболочкой множества точек <math>\mathbb{X}</math>, где <math>x_i \in A</math>.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

[[en:Description of algorithm properties and structure]]

Участник:Aleksey Dumbay/QuickHull

2017-10-23T19:04:54Z

Aleksey Dumbay: Новая страница: « = Свойства и структура алгоритма = == Общее описание алгоритма == Построение выпуклой обол…»

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Построение выпуклой оболочки множества точек - задача построения минимального по вложенности выпуклого множества, содержащего все точки из исходного множества. В случае конечного числа точек на плоскости выпуклая оболочка описывается некоторым подмножеством точек, которые принадлежат этой выпуклой оболочке. В этом случае выпуклая оболочка представляет собой выпуклый многоугольник с вершинами из этого подмножества точек.

Алгоритм QuickHull<ref>Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). [http://dpd.cs.princeton.edu/Papers/BarberDobkinHuhdanpaa.pdf "The quickhull algorithm for convex hulls"]</ref> - алгоритм построения выпуклой оболочки множества точек в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае, где <math>N</math> - мощность множества точек. Алгоритм использует подход, аналогичный подходу QuickSort, разделяя исходное множество на некоторые подмножества, отсекая ненужные точки, после этого применяется рекурсивно к образовавшимся подмножествам, а потом объединяет их. В рамках этого алгоритма решаются две задачи - выделения подмножеств и объединения нескольких выпуклых оболочек вместе.

Есть несколько различных вариантов данного алгоритма, которые по-разному находят подмножества для рекурсивного обхода. Общая их идея заключается в выделении крайних точек и отсечении всех точек, что попали в образовываемый ими многоугольник. Остальные точки делятся на множества и обрабатываются рекурсивно. Так же существует вариант алгоритма, в котором рекурсивно находится наиболее удаленная от отрезка вершина, отсекается образованный треугольник, а к новым сторонам и разбившемуся множеству алгоритм применяется рекурсивно.<ref>[http://algolist.manual.ru/maths/geom/convhull/quickhull.php Пример реализации такого варианта]</ref>

На вход алгоритму подается множество точек на плоскости, на выходе - те точки, которые являются вершинами выпуклой оболочки.
== Математическое описание алгоритма ==
Выпуклое множество <math>A</math> для векторного пространства <math>\mathbb{V}</math> над <math>\mathbb{R}</math> - такое множество, что

<math>
\forall \textbf{x}, \textbf{y} \in A, \forall \alpha \in [0,1]: \textbf{x} \cdot \alpha + \textbf{y} \cdot (1 - \alpha) \in A
</math>.<ref>[http://www.machinelearning.ru/wiki/images/c/cc/MO17_seminar6.pdf Выпуклое множество]</ref>

Выпуклая оболочка множества точек <math>\mathbb{X}</math> - это такое выпуклое множество, которое содержит все точки из множества <math>\mathbb{X}</math> и при этом является минимальным по вложению. В случае <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math> выпуклая оболочка является многоугольником.

На вход алгоритму подается множество <math>\mathbb{X}</math> из <math>\mathbb{R}^2</math>, которое описывает набор точек на плоскости, где каждая точка - вектор <math>(x,y)</math> где компоненты соответствуют координатам на плоскости в декартовой системе координат. <math>\mathbb{X} = \{a_1, a_2, \ldots, a_N\}</math>.
Алгоритм работает в среднем за <math>\Theta(N*\log{N})</math> и за <math>O(N^2)</math> в худшем случае.

Алгоритм строит упорядоченный набор из точек <math>x_{1}, x_{2}, \ldots, x_m </math>, которые образуют многоугольник <math>X_1X_2X_3\ldots X_m</math>, являющийся выпуклой оболочкой множества точек <math>\mathbb{X}</math>, где <math>x_i \in A</math>.

== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

[[en:Description of algorithm properties and structure]]