Range tree в общем случае, если у точек имеются совпадающие некоторые координаты?

Question

[borgch]

Прочитал вот эту статью: goo.gl/kXmR7L и соответствующие главы из де Берга, Computational Geometry. В качестве основы дерева предлагается "использовать сбалансированное бинарное дерево поиска, в листьях которого будем хранить точки искомого множества, а в нелистовых вершинах - разделющие значения, по которым будет вестись поиск в дереве."

Одномерное range-tree — просто дерево поиска, описанное выше.
d-мерное range-tree — дерево поиска (по первой координате X_1), аналогичное описанному выше, но в каждой вершине дополнительно хранящее d-1-мерное range-tree (по остальным координатам X_2 x ... x X_d) для множества элементов, являющихся листами поддерева этой вершины.

Предположим, надо построить дерево из таких точек: (1, 2), (1, 3) и (1, 4). Очевидно, невозможно сделать такое дерево поиска, чтобы у него было несколько одинаковых листов. Ну вот как тогда построить дерево поиска из первых x-координат, то есть из единиц?) Что за тип данных такой, который не может хранить даже такой простой пример?) Где я неверно понял определение?

Comments

[AtomKrieg]

очевидно, что невозможно построить такое range tree, потому что это interval tree

[borgch]

AtomKrieg: пример про двумерный случай range tree, здесь (1,2) - это точка пространства RxR, с первой координатой 1, в второй 2. А не интервал из R. То есть вопрос: три точки на плоскости, у которых совпадают первые координаты. Как построить range tree?