3
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ sorted set $E$ of $e_{(x,y)}$, but sorted by ? $\endgroup$
    – lucasoliveira
    Commented Feb 14, 2015 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
    Commented Feb 14, 2015 at 19:39
  • $\begingroup$ You tried K-d-Tree or R-Tree ? $\endgroup$
    – lucasoliveira
    Commented Feb 14, 2015 at 23:01
  • $\begingroup$ Or maybe H-Tree ? $\endgroup$
    – lucasoliveira
    Commented Feb 14, 2015 at 23:03
  • $\begingroup$ HashTable $O(1)$ Question maybe useful. $\endgroup$
    – lucasoliveira
    Commented Feb 14, 2015 at 23:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.