Сопоставление сбалансированного дерева с точками на плоскости

Question

Нам дано сбалансированное дерево размера N, в том смысле, что для каждого узла в дереве, если корневое дерево, укорененное на этом узле, имеет размер и k детей, размеры его k поддеревков равны Omega(n/k). Нам также даются N точек на плоскости, три не коллинеарны. Мы пытаемся найти биекцию между узлами в этом дереве и точки на плоскости, такие, что рисование дерева на плоскости не приведет к каким-либо пересечениям ребер. k - Theta(1), и может быть разным для каждого узла.

Я пытаюсь найти рекурсивное решение, которое решает это, но безрезультатно, так как я не уверен, как мы можем гарантировать отсутствие пересечений. Целевое время выполнения: O(n log^2 n), поэтому повторение формы T(n)=k*T(n/k) + O(n log n) приведет к этому, поэтому я пытаюсь думать по этим строкам. Я должен сортировать точки по x-координате, находить медиану, а затем разбивать остальную часть точек на блоки и рекурсивно решать ее. Но я вытащил тестовые примеры, которые позволили этому решению выйти из строя. Любая помощь?

Answer 1

Вы должны иметь возможность выбрать произвольную точку для своего корня, а затем срезать вокруг нее плоскость, как пирог, так что каждая область содержит количество точек в соответствующем поддереве, а строка из корня в любую точку региона остается полностью внутри региона.

Затем вы должны иметь возможность делать то же самое рекурсивно, как и в каждом субрегионе. С каждым поддеревом вам нужно будет повторно отсортировать оставшиеся точки в этом субрегионе в угловом порядке вокруг корня поддерева, что должно дать вам ваш повтор T(n) = k*T(n/k) + O(n log n).

---

Редактировать: при дальнейшей мысли вы, вероятно, не можете выбрать произвольную точку; вы хотите выбрать точку на выпуклой оболочке ваших точек, чтобы входящая линия не пересекалась с выпуклой оболочкой - в противном случае ваше поддерево могло бы пересекать входящую строку. Это достаточно легко сделать, выбирая, скажем, первый элемент вашего подмножества в текущей угловой сортировке.