Задача: у нас есть N точек на плоскости, и нам нужно для каждой точки отсортировать все остальные по полярному углу.

Вчера мной была косвенно высказана гипотеза, что эта задача может быть разрешима за O(n²). Гипотеза возникла в тот момент, когда я доказал, что различных сортировок существует O(cⁿ²), где c — небольшая константа.

После долгих мучений придумать что-то лучше наивного алгоритма за у меня так и не получилось. Хотелось бы услышать какие-либо идеи либо насчет алгоритма, либо насчет доказательства нижней оценки .