# Computational Geometry: what is the key of the BST in the algorithm “ Partitioning a polygon in y-monotone pieces”

The algorithm to partition a polygon into y-monotone pieces is as follows:

Input. A simple polygon P stored in a doubly-connected edge list D
Output. A partitioning of P into monotone subpolygons, stored in D

Process:
1.  Construct a priority queue Q on the vertices of P ,use y-
coordinates to determine priority.If two points have the same y-
coordinate, the one with smaller x-coordinate has higher
priority.
2.  Initialize an empty binary search tree T
3.  While Q is not empty Do
4.      remove the vertex vi with the highest priority from Q
5.      call the appropriate procedure to handle the vertex,
depending on the type of the vertex
6.  End Do


An Example process of handling a vertex if it is a merge vertex will be as follows:

HandleMergeVertex(Vi):
1. If helper(ei−1) is a merge vertex
2.     insert the diagonal connecting vi to helper(ei−1) in D
3. delete ei−1  from T
4. search in T to find the edge ej  directly left of vi
5. If helper(ej) is a merge vertex
6.     Insert the diagonal connecting vi to helper(ej) in D
7. helper(ej) = vi


Now in DeBerg's book of computational geometry , he quoted as:

In the approach above, we need to find the edge to the left of each vertex. Therefore we store the edges of P intersecting the sweep line in the leaves of a dynamic binary search tree T. The left-to-right order of the leaves of T corresponds to the left-to-right order of the edges. Because we are only interested in edges to the left of split and merge vertices we only need to store edges in T that have the interior of P to their right. With each edge in T we store its helper. The tree T and the helpers stored with the edges form the status of the sweep line algorithm. The status changes as the sweep line moves: edges start or stop intersecting the sweep line, and the helper of an edge may be replaced

Now my question would be , what is the key of this BST T ? Is it the vertex in consideration , is it the edge ? And how to determine what is the edge at the left of an vertex?