Здравствуйте, Рома Мик, Вы писали:

РМ>>>Если такого из наших двух нет, то значит нет вообще.
К>>Неправда. Контрпример: два круга, один вписан в квадрат, а другой — в угол квадрата.
К>>По обоим проекциям будет вложение, хотя очевидно, что через точку касания проходит разделительная прямая.
РМ>Ой.
РМ>Могу предложить тогда взять не два, а три направления под углами 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) — тоже квадратичное время.