Merging of two convex polygon chains in O(log n)

Question

Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the points $p_1\rightarrow p_2\rightarrow p_3$ is stored as $\{0\Rightarrow p_1,1\Rightarrow p_2,2\Rightarrow p_3\}$. The key-value store is implemented with a data structure which allows the operations split and join in $O(\log n)$ time.

I want to join the chain $P = p_1\rightarrow p_2\rightarrow p_3$ and the chain $Q = q_1->q_2->q_3$ to a chain $p_1\rightarrow p_2\rightarrow p_3\rightarrow q_1\rightarrow q_2\rightarrow q_3$.

Is there a way to join two polygon chains in logarithmic time without updating the keys? If I do a simple join, I get a problem with duplicated keys, so the keys of $Q$ have to be updated before the join, but this destroys my logarithmic time approach as I need linear time for updating the keys.

Am I wrong here already?

If not, is there a way to keep the logarithmic time?

Answer 1

You are asking for a data structure for sequences (aka vectors or arrays) that permits efficient concatenation. I suggest using any standard binary tree data structure, e.g., AVL tree, red-black tree, splay tree, treap, etc. They support $O(\lg n)$ time concatenation and $O(\lg n)$ time lookups. The differences between them come down to details related to implementation complexity and constant-factor differences in running time.

With these algorithms, the keys are not stored explicitly. Instead, they are implicit. To lookup key $i$, you search for the $i$th leaf from the left, but the key $i$ is never stored anywhere. Thus, when concatenating two trees, there is no need to renumber the keys. You can find the $i$th leaf in $O(\lg n)$ time: augment the data structure so that each node keeps a count of the number of leafs underneath it; then it's clear how to traverse the tree during a lookup (whether to go left or right at each node is an easy decision, given the information stored in each node).