Здравствуйте, Рома Мик, Вы писали:
РМ>Очевидно, что проекции строятся за O(N).
РМ>Далее дело техники. Видимо, не составит труда уже независимо от кол-ва точек ( нас интересуют только по две крайние для каждого множества ) найти такое направление или убедится, что его нет.
РМ>Берем два перепендикулярных направления. Выбираем то, для которого проекции множеств выглядят не так: < { } >. РМ>Если такого из наших двух нет, то значит нет вообще. РМ>Если уже получили < > { }, то все готово.
Неправда. Контрпример: два круга, один вписан в квадрат, а другой — в угол квадрата.
По обоим проекциям будет вложение, хотя очевидно, что через точку касания проходит разделительная прямая.
РМ>Иначе находим в какую сторону вращать, чтобы уменьшать область перекрытия и вращаем. Можно применять всякие методы Ньютона, касательных, хорд и всех остальных.
Вот на этих вращениях ты и получишь искомый N*logN, если не больше.
Нужен алгорит из области комп. графики и геометрии.
Есть два множества точек на плоскости. Надо ответить на вопрос:
разделимы ли эти два множества? То есть, можна ли провести прямую, что
разделит плоскость на две подплоскости в которых будут лежать эти множества.
Главные прикол, что сделать это надо за О(N). За О(N*log(N)) это сделать не составит
большого труда. Достаточно проверить пересечение опуклых оболонок построеных на
этих множествах. Есть подсказка что надо делать основываясь на линейном программировании...
да вот не могу придумать что именно нужно минимизировать в таком случае...
Здравствуйте, daisywheel, Вы писали:
D>Есть два множества точек на плоскости. D>То есть, можна ли провести прямую, что D>разделит плоскость на две подплоскости в которых будут лежать эти множества.
То есть, можно ли найти такое направление, что проекции точек на прямую в этом направлении... ( в общем ясно )
D>Главные прикол, что сделать это надо за О(N).
Очевидно, что проекции строятся за O(N).
Далее дело техники. Видимо, не составит труда уже независимо от кол-ва точек ( нас интересуют только по две крайние для каждого множества ) найти такое направление или убедится, что его нет.
Берем два перепендикулярных направления. Выбираем то, для которого проекции множеств выглядят не так: < { } >.
Если такого из наших двух нет, то значит нет вообще.
Если уже получили < > { }, то все готово.
Иначе находим в какую сторону вращать, чтобы уменьшать область перекрытия и вращаем. Можно применять всякие методы Ньютона, касательных, хорд и всех остальных.
Здравствуйте, daisywheel, Вы писали:
D>Нужен алгорит из области комп. графики и геометрии. D>Есть два множества точек на плоскости. Надо ответить на вопрос: D>разделимы ли эти два множества? То есть, можна ли провести прямую, что D>разделит плоскость на две подплоскости в которых будут лежать эти множества.
D>Главные прикол, что сделать это надо за О(N). За О(N*log(N)) это сделать не составит D>большого труда. Достаточно проверить пересечение опуклых оболонок построеных на D>этих множествах. Есть подсказка что надо делать основываясь на линейном программировании... D>да вот не могу придумать что именно нужно минимизировать в таком случае...
Кроме чисто программистских есть еще аналитические подходы, например методы, которые используются при тренировке нейросетей. Однослойный персептрон — это как раз простейшая нейросеть, действующая как разделяющая плоскость.
Что там со сложностью — не знаю, но обычно хватает несколько раз предъявить персептрону все точки.
Здравствуйте, Кодт, Вы писали:
РМ>>Если такого из наших двух нет, то значит нет вообще. К>Неправда. Контрпример: два круга, один вписан в квадрат, а другой — в угол квадрата. К>По обоим проекциям будет вложение, хотя очевидно, что через точку касания проходит разделительная прямая.
Ой.
Могу предложить тогда взять не два, а три направления под углами 60 градусов. Вроде должно помочь.
К>Вот на этих вращениях ты и получишь искомый N*logN, если не больше.
Неа. N — число точек. Единственная операция, зависящая от N, вычисление проекций. А она повторяется независимое от кол-ва точек раз. Так что O(N). Ведь O( 100000000 * N ) == O( N ) В чем и заключался основной смысл, остальное так, догадки. Можно еще что-нибудь придумать на базе этого.
Другой вариант: нарисовать эти точки с достаточным разрешением ( как бы только это достаточное разрешение за O(N) выяснить ) и работать далее с рисунком. То же можно что-нибудь выдумать.
Здравствуйте, Рома Мик, Вы писали:
РМ>>>Если такого из наших двух нет, то значит нет вообще. К>>Неправда. Контрпример: два круга, один вписан в квадрат, а другой — в угол квадрата. К>>По обоим проекциям будет вложение, хотя очевидно, что через точку касания проходит разделительная прямая. РМ>Ой. РМ>Могу предложить тогда взять не два, а три направления под углами 60 градусов. Вроде должно помочь.
Хочешь заикой сделаю?
Первое множество точек принадлежит отрезку, не параллельному ни одному из твоих опорных направлений (или по крайней мере, ограничено с одной стороны этим отрезком).
Второе — точка, лежащая достаточно близко к середине этого отрезка.
Таких контрпримеров можно нарожать сколько угодно.
К>>Вот на этих вращениях ты и получишь искомый N*logN, если не больше. РМ>Неа. N — число точек. Единственная операция, зависящая от N, вычисление проекций. А она повторяется независимое от кол-ва точек раз. Так что O(N). Ведь O( 100000000 * N ) == O( N ) В чем и заключался основной смысл, остальное так, догадки. Можно еще что-нибудь придумать на базе этого.
Для любых наперёд заданных направлений можно построить контрпример — см. выше.
А на самом деле, нужно исследовать не более N*(N-1)/2 направлений — это линии, соединяющие попарно все точки множества.
Вот мы получаем уже O(N^3). Это весьма избыточно, но! Когда станем оптимизировать — то придём к тому, что построим выпуклую оболочку.
Кстати, нам не нужно строить две оболочки. Достаточно только одну, а затем исследовать проекции второго множества на нормали к оболочке первого. Это займёт O(H1*N2), где H1 — количество точек оболочки, N2 — мощность второго множества.
T = O(N1*log(N1)) + O(N1*N2), т.е. квадратичное время.
Пересечение двух оболочек, по-моему, займёт O(H1*H2) — тоже квадратичное время.
Здравствуйте, kfmn, Вы писали:
K>Здравствуйте, daisywheel, Вы писали:
D>>Нужен алгорит из области комп. графики и геометрии. D>>Есть два множества точек на плоскости. Надо ответить на вопрос: D>>разделимы ли эти два множества? То есть, можна ли провести прямую, что D>>разделит плоскость на две подплоскости в которых будут лежать эти множества.
D>>Главные прикол, что сделать это надо за О(N). За О(N*log(N)) это сделать не составит D>>большого труда. Достаточно проверить пересечение опуклых оболонок построеных на D>>этих множествах. Есть подсказка что надо делать основываясь на линейном программировании... D>>да вот не могу придумать что именно нужно минимизировать в таком случае...
K>Кроме чисто программистских есть еще аналитические подходы, например методы, которые используются при тренировке нейросетей. Однослойный персептрон — это как раз простейшая нейросеть, действующая как разделяющая плоскость. K>Что там со сложностью — не знаю, но обычно хватает несколько раз предъявить персептрону все точки.
Не все так просто. Несколько раз — это сколько?
Про персептрон можно прочитать что-то здесь.
Serge.
Hасколько проще была бы жизнь, если бы она была в исходниках.
Перекуём баги на фичи!
