I have been looking into the sweep line algorithms of finding intersection of line segments and polygon partitioning using monotone polygons. The algorithms require a dynamically balanced binary tree which stores the sorted sequence of the elements in the leaves of the tree.

I am familiar with Balanced Binary trees like AVL trees where the elements are stored in the inner leaves too. I am confused on how to implement such a data structure which only stores the data in the leaves and uses the inner nodes as splitter nodes.

Please explain the data structure for storing the data in the leaves and it is helpful if any reference links are given.

Thank you.

  • $\begingroup$ sorted set $E$ of $e_{(x,y)}$, but sorted by ? $\endgroup$ Feb 14 '15 at 16:31
  • 1
    $\begingroup$ Assume the sweep line moves from top to bottom implying the sorting of event points is by y-coordinate and the sorting of the segments in the status line is by x-coordinate. $\endgroup$
    – user27717
    Feb 14 '15 at 19:39
  • $\begingroup$ You tried K-d-Tree or R-Tree ? $\endgroup$ Feb 14 '15 at 23:01
  • $\begingroup$ Or maybe H-Tree ? $\endgroup$ Feb 14 '15 at 23:03
  • $\begingroup$ HashTable $O(1)$ Question maybe useful. $\endgroup$ Feb 14 '15 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.