Нижняя граница временной сложности целочисленной задачи об уникальности элементов

Рассматривается целочисленная задача об уникальности элементов, которая формулируется следующим образом: проверить, найдется ли среди данных $n$ целых чисел хотя бы одна пара равных между собой. Доказано, что $\Omega(n\log n)$ является нижней границей временной сложности этой задачи в модели линейного дерева решений. Получены нижние границы временной сложности нескольких геометрических задач, к которым она сводится.