Здравствуйте, Croc, Вы писали:

<skip>

Ты не упомянул об отбрасывании по минимальному расстоянию между охватывающими прямоугольниками.
И тест на пересечение, я надеюсь не порёберная проверка.
А так, для выпуклых, наверное только полным перебором пар вершин...