CODEWITHSUNDEEP
algorithmcomputational-geometry
Mike
Mike

Reputation: 21

Mapping a balanced tree to points on the plane

We're given a balanced tree of size N, in the sense that for every node in the tree, if the subtree rooted at that node has size n and k children, then the sizes of its k subtrees are Omega(n/k). We are also given N points on the plane, no three are collinear. We are trying to find a bijection between nodes in this tree and points on the plane such that drawing the tree on the plane won't result in any edge crossings. k is Theta(1), and can be different per node.

I'm trying to find a recursive solution that solves this, but to no avail, since I'm not sure how we can guarantee the no crossings requirement. The target runtime is O(n log^2 n), so a recurrence of the form T(n)=k*T(n/k) + O(n log n) would result in that, so I'm trying to think along those lines. I'm to sort the points by x-coord, finding the median, and then partitioning the rest of the points into blocks and recursively solving it. But I've drawn out test cases that let that solution fail. Any help?

Upvotes: 2

Views: 185

Answers (1)

comingstorm
comingstorm

Reputation: 26087

You should be able to choose an arbitrary point for your root, then slice up the plane around it like a pie, such that each region contains the number of points in its corresponding sub-tree, and the line from the root to any point in the region stays entirely within the region.

Then, you should be able to do the same recursively, with every sub-region. With every sub-tree, you will need to re-sort the remaining points in that sub-region in angular order around the sub-tree root, which should give you your T(n) = k*T(n/k) + O(n log n) recurrence.

Edit: on further thought, you probably can't pick an arbitrary point; you want to pick a point on the convex hull of your points, such that the incoming line doesn't intersect the convex hull -- otherwise, your subtree could cross the incoming line. This is easy enough to do by picking, say, the first element of your subset in the current angular sorting.

Upvotes: 2

Related Questions