Каким может быть реальный пример задачи, в которой возникает потребность в вычислении выпуклой оболочки?

Answer 1

вобще-то на каждом шагу, обычно как часть других алгоритмов, например, когда надо как-то представить общую форму множества точек, а лежащие внутри - не важны.

вот у меня была недавно реальная задача: есть куча точек (от сотен до сотен тысяч) , плотно лежащих на некой плоскости в 3d (например, крыша дома, отсканированная лазерным сканером) , оператор тыкает куда-то недалеко от края (скажем в примерно в полуметре от края) , надо найти линию края крыши. Решение: проецируем все в плоскость, выбираем точки в метре от тычка оператора, они лежат в неком обрезанном краем крыши круге. Берем выпуклую оболочку, е центр тяжести, пробегаем по контуру, ищем середину отрезка, самую близкую к центру тяжести - эти две точки лежат как раз на краю (ну потом уже недолго уточнить линию)

много раз вылезали задачи типа нахождения диаметра множества точек - максимально далекой пары. Если перебирать в лоб тысячу точек - получится пол-миллиона пар, если миллион точек - пол-триллиона (это уже нереально долго) . А если сначала взять выпуклую оболочку - можно быстренько обежать е взаимно скользящей парой точек, получим для миллиона точек порядка 10 миллионов операция на построение оболочки и потом порядка нескольких тысяч на выбор пары. 10 миллионов на современном компе - глазом не увидишь, а пол-триллиона - как минимум часы.

вобще вып. оболочка хороша тем, что считается быстро, а точек остается мало (при случайных данных - порядка корня из чиста точек) .