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

РМ>Очевидно, что проекции строятся за O(N).

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

РМ>Берем два перепендикулярных направления. Выбираем то, для которого проекции множеств выглядят не так: < { } >.
РМ>Если такого из наших двух нет, то значит нет вообще.
РМ>Если уже получили < > { }, то все готово.

Неправда. Контрпример: два круга, один вписан в квадрат, а другой — в угол квадрата.
По обоим проекциям будет вложение, хотя очевидно, что через точку касания проходит разделительная прямая.

РМ>Иначе находим в какую сторону вращать, чтобы уменьшать область перекрытия и вращаем. Можно применять всякие методы Ньютона, касательных, хорд и всех остальных.

Вот на этих вращениях ты и получишь искомый N*logN, если не больше.