Участник:RS42/Quickhull

Свойства и структура алгоритмов

Общее описание алгоритма

Задача построения выпуклой оболочки является одной из важных проблем вычислительной геометрии. Выпуклую оболочку множества точек [math]\displaystyle{ X }[/math] можно определить следующим образом: это пересечение всевозможных выпуклых множеств, содержащих [math]\displaystyle{ X }[/math]. В случае конечного числа [math]\displaystyle{ n }[/math] точек из [math]\displaystyle{ X }[/math]:

[math]\displaystyle{ \mathrm{Conv}(X)=\left\{\left.\sum_{i=1}^{n} \alpha_i x_i\ \right| (\forall i: \alpha_i\ge 0)\wedge \sum_{i=1}^{n} \alpha_i=1 \right\}. }[/math]

Математическое описание алгоритма

THIS!!!! Приводится математическое описание решаемой задачи в виде совокупности формул и соотношений, как это принято в книгах и учебниках. По возможности, используются общепринятые обозначения и способы записи. Должны быть явно определены все использованные обозначения и описаны свойства входных данных. Представленное описание должно быть достаточным для однозначного понимания постановки решаемой задачи для человека, знающего математику.

Литература

• Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for convex hulls," ACM Trans. on Mathematical Software, 22(4):469-483, Dec 1996, http://www.qhull.org