Задача: у нас есть N точек на плоскости, и нам нужно для каждой точки отсортировать все остальные по полярному углу.
Вчера мной была косвенно высказана гипотеза, что эта задача может быть разрешима за O(n2). Гипотеза возникла в тот момент, когда я доказал, что различных сортировок существует O(cn2), где c — небольшая константа.
После долгих мучений придумать что-то лучше наивного алгоритма за 
у меня так и не получилось. Хотелось бы услышать какие-либо идеи либо насчет алгоритма, либо насчет доказательства нижней оценки 
.
насколько я знаю, эту задачу решает rotation tree для построения visibility графа. Описано в этой статье Overmars & Welzl, работает за O(n2)
Вроде бы, это то, что мне нужно. Спасибо большое!
Интуиция меня не подвела :).