Запросы на объемную защиту

У меня есть выпуклая форма, определяемая набором вершин. У меня также есть большой набор точек, и я бы хотел проверить, какие они содержатся в выпуклой форме. В настоящее время я просто использую решатель линейного программирования с открытым исходным кодом для каждой точки независимо с постоянной целевой функцией. Дополнительную информацию см. В главе 11.4 от http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf.Запросы на объемную защиту

Однако это довольно медленно даже в 100 измерениях. Есть ли способ использовать тот факт, что все точки запроса известны заранее, чтобы ускорить процесс?

Редактировать Исправлена опечатка.

источник

2013-08-25 oxbowlake

Линейный программный решатель? Зачем? Разве вы не можете просто проверить неравенство один за другим? Это должно быть намного быстрее, чем решить проблему оптимизации, а затем отбросить большую часть ответа ... –

Я бы также предложил использовать какое-то пространственное подразделение (дерево kd?). Вы существенно разбиваете пространство на параллелепипедальные куски, каждый из которых (1) полностью находится внутри вашей формы, (2) полностью снаружи или (3) частично внутри и пересекает * небольшое число * гиперплоскостей, которые определяют вашу форму. Теперь вам нужно только проверить небольшое количество одномерных ограничений, чтобы определить, в какой части вашей точки находится (тогда только если это кусок типа 3), небольшое количество N-мерных ограничений, чтобы проверить, находится ли оно внутри вашей фигуры. –

@ н.м. Была опечатка. У меня есть вершины, а не неравенства. – oxbowlake

Мое предложение состояло бы в том, чтобы найти выпуклую оболочку точек внутри формы. Я не могу сразу придумать способ получить это непосредственно из решателя LP, но вы можете найти точку, ближайшую к данной гиперплоскости формы, добавив линейный член для этой гиперплоскости к целевой функции. Повторите это для всех краев фигуры, и для каждого края повторите это несколько раз, исключив последнее решение каждый раз, чтобы забрать все более отдаленные точки. Это должно дать вам несколько точек «близко» к и внутри гиперплоскости.

Как только у вас есть корпус, вы должны иметь возможность классифицировать все остальные точки как находящиеся внутри или снаружи относительно быстро. Я уверен, что есть алгоритмы, чтобы делать это довольно быстро, хотя я не знаю никого. Одним из потенциально полезных методов, который мог бы избавиться от множества внутренних точек, было бы: если пространство n-мерно, выберите n + 1 точку на корпусе и проверьте каждую точку, чтобы увидеть, является ли это выпуклой комбинацией этих точек (используя линейные алгебра).

источник

2013-08-25 09:35:17

Извинения, моя форма определяется вершинами. У вопроса была ошибка. – oxbowlake

Корпус n точек в d-размерах может иметь порядок n^(floor (d/2)) граней, а d - 100. –

@DavidEisenstat: Кажется, это говорит о том, что почти все точки внутри формы будут факт лежит на * корпусе. Это возможно? Или это худший случай, о котором вы упоминаете в отношении маловероятного патологического случая? Я думаю, что дело в том, чтобы установить, какая * пропорция * точек находится на корпусе и внутри нее. Если на корпусе меньше, скажем, 20% очков, то, возможно, стоит попробовать найти корпус. –

ответ

Смежные вопросы