# Data Structure for storing the Sweep Line Status in Sweep Line Algorithms

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.

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