построение выпуклой оболочки в n-мерном пространстве

[sadomovalex]

добрый день,
есть ли литература, в которой описывается алгоритм построения выпуклой оболочки, не в 2-мерном случае, а в n-мерном (евклидовом) пространстве?

[незваный гость]

q.v.

[sadomovalex]

спасибо, незваный гость
книгу Препараты, Шеймоса я смотрел - там приведены несколько алгоритмов построения для n-мерного пространства. Но интересуйщего алгоритма не нашел. Алгоритм называется "построение выпуклой оболочки методом случайного поиска". Даже гугл ничего подходящего не выдал. Попробую на английском.
Вы ничего не знаете об этом алгоритме?

[K-3]

Описания некоторых алгоритмов построения выпуклой оболочки в $n$-мерном случае есть в книжке Препарата, Шеймоса. Хорошие результаты показывают разные варианты алгоритма quick-hull, очень популярной реализацией которого является программа qhull http://www.qhull.org/. На сайте этого проекта можно найти статью с описанием алгоритма. См. также сслыки на страничках http://www.cs.unb.ca/profs/bremner/docs/recommend.html, http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/links.html

Добавлено спустя 16 минут 54 секунды:

Вот еще две ссылки:

B. Chazelle, An Optimal Convex Hull Algorithm in Any Fixed Dimension, Discrete Comput. Geom. 10 (1993), 377-409

D. Avis, D. Bremner, R. Seidel How good are convex hull algorithms? Comput. Geom. Theory and Appl. 7 (1997) 265-302

[sadomovalex]

K-3, спасибо за помощь
но меня интересует прежде всего метод случайного поиска. Если у Вас есть доступ к электронным журналам, не могли бы Вы поискать в них этот алгоритм

[K-3]

sadomovalex писал(а):

метод случайного поиска

- как это будет по-английски: randomized algorithm (?). В чем его основная идея, чтобы было понятно?

[sadomovalex]

K-3 писал(а):

как это будет по-английски: randomized algorithm (?). В чем его основная идея, чтобы было понятно?

как оказалось, этот метод придумал сам преподаватель, а разъяснять не стал. Здесь я подробно изложил суть проблемы. Если есть какие-нибудь мысли по этому поводу, буду рад Вас выслушать. Пригодится лобая помощь

[PAV]

Чтобы не было дублирования, данная тема закрывается. Продолжение обсуждения в разделе "Математика -> Помогите решить/разобраться"