Мин. расстoяние тoчка-многoугольник в N-мернoм прoстранстве

[zosimovser]

В N-мерном пространстве есть точка и выпуклый многоугольник, заданный точками. Как найти мин. расстояние между ними? Понятно, что это будет либо перпендикуляр к гиперплоскости, либо расстояние до одной из точек. Но как его найти (перпендикуляр), ума не приложу..

И еще, может быть в Matlab есть для этого ф-я специальная? или другие функции упрощающие эту задачу?

[ИСН]

Выпуклый многочто, простите?

[zosimovser]

Типа многогранник что-ли.. Дан произвольный набор точек, причем их может быть намного больше размерности пространства, они ограничивают некую область, которая выпукла.

Кстати по поводу перпендикуляра погорячился.. Это не обязательно перпендикуляр будет, к сожалению.

-- 22.11.2018, 13:43 --

Выход - алгоритм Гилберта—Джонсона—Кёрти, но похоже его хорошо проверенной реализации в измерениях >3 нет.

Не думал, что, как мне казалось простая задача, приведет к такой жести..

[Papazol]

zosimovser в сообщении #1355854 писал(а):

Типа многогранник что-ли.. Дан произвольный набор точек, причем их может быть намного больше размерности пространства, они ограничивают некую область, которая выпукла.

Коряво как-то... видимо, речь идет о выпуклой линейной оболочке, т.е. наименьшем выпуклом множество содержащем данные точки.

[grizzly]

zosimovser в сообщении #1355854 писал(а):

Выход - алгоритм Гилберта—Джонсона—Кёрти, но похоже его хорошо проверенной реализации в измерениях >3 нет.

Это Вы что-то странное говорите. То есть все те статьи, которые опубликованы по этому алгоритму, да и сам алгоритм это просто всемирный заговор математиков и программистов?

Вот здесь одна из первых ссылок в гугле. Но там классика этого алгоритма, кажется, -- от одного политопа до другого. Ваш случай должен быть сколько-то проще, я думаю. Вот только разбирать такие алгоритмы та ещё задача :) Лучше бы допилить так, чтоб заработало "как есть".

Вы ведь не ожидали увидеть в ответе пару строчек кода, решающих задачу?

[g______d]

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

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

Из общих соображений всегда будет алгоритм, работающий за $O(N^{C(d)})$, где $N$ -- количество точек, $d$ размерность. А, ну собственно в первом случае так и получается, потому что можно ограничиться подмножествами из не более чем $d+1$ точек.

[zosimovser]

Цитата:

Коряво как-то... видимо, речь идет о выпуклой линейной оболочке, т.е. наименьшем выпуклом множество содержащем данные точки.

Не совсем. Все эти точки лежат на ограничивающей границе, внутри точек нет.

Цитата:

Это Вы что-то странное говорите. То есть все те статьи, которые опубликованы по этому алгоритму, да и сам алгоритм это просто всемирный заговор математиков и программистов?

Вот здесь одна из первых ссылок в гугле. Но там классика этого алгоритма, кажется, -- от одного политопа до другого. Ваш случай должен быть сколько-то проще, я думаю. Вот только разбирать такие алгоритмы та ещё задача :) Лучше бы допилить так, чтоб заработало "как есть".

Вы ведь не ожидали увидеть в ответе пару строчек кода, решающих задачу?

Да, для моей задачи излишне. Ссылку эту я знал еще до открытия темы. Во первых этот код не проверялся на размерностях >3, а во вторых его так просто не используешь. Как раз я их и ждал! Что может быть проще, отправить массив точек, точку и получить расстояние? Другое дело что нет написанного, а самому писать застрелишься.. и проверить правильность сложно.
В матлабе могли бы сделать.

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

[g______d]

zosimovser в сообщении #1356275 писал(а):

Всегда ли максимальное расстояние между выпуклыми оболочками это максимальное расстояние между их точками (составляющими наименьшее выпуклое множество)?

Да.

[Dmitriy40]

zosimovser в сообщении #1356275 писал(а):

Всегда ли максимальное расстояние между выпуклыми оболочками это максимальное расстояние между их точками (составляющими наименьшее выпуклое множество)? Для минимального нет, а для максимального???

Всегда: любая хорда лежит внутри окружности и расстояние от центра до неё меньше расстояния до её концов (радиуса). Под окружностью понимать описывающую. В многомерии и гиперплоскостями аналогично. Собственно это тривиально доказывается: касательная к гиперсфере гиперплоскость лежит снаружи этой гиперсферы и значит любые другие точки гиперплоскости дальше от центра гиперсферы, включая и точки вашей фигуры, для любой из гиперграней.