1
$\begingroup$

I am interested in the details of the implementation of the "sweep-line status" data structure, which is used to implement the Bentley-Ottmann algorithm to find all intersections (and the corresponding involved segments) of a set of segments (or line-segments). The algorithm and the sweep-line status data structure is briefly described in chapter $2$ of the book "Computational Geometry: Algorithms and Applications" by de Berg, Cheong, van Kreveld, and Overmars.

In the book, the authors suggest two methods to implement the sweep line status. Both of these methods use a self-balancing BST, let's call it $T$.

One method (according to the authors the easiest one) consists in storing the segments at the leaves of the $T$ in the same order that they intersect the sweep line and use internal nodes to store the rightmost segment which is found in the left subtree of that node. For example, in the following figure, we see that the root node (an internal node) stores $s_1$, which is the rightmost leaf node (segment) in the left subtree of the root itself.

enter image description here

How exactly do we define the total (or partial?) order of the segments, given that we must maintain this invariant? How do we define or represent the segments? How exactly do we compare them?

If we needed to treat internal nodes in a different way (as the picture above suggests, given the different types of objects, i.e. circles and rectangles, used to represent internal and leaf nodes) than the leaf nodes (the actual segments), then it may not be an easy task to maintain a self-balancing BST (e.g. an RBT). Actually, a "plain" RBT usually treats all nodes equally, so we would need a new data structure. Nonetheless, the authors of the book claim that a self-balancing BST is enough to implement the "sweep-line status" data structure.

According to the lecture notes of D. Mount, we can store the segments (in the sweep line status) as a pair of numbers $(a, b)$, which are the numbers of the equation line which goes through the segments, i.e. $y = a*x + b$. However, he doesn't really explain how to compare segments, but only how to compare lines.

In the Bentley-Ottmann algorithm, let's suppose that we are processing segments/events from left to right. If we are processing one event point (from the event queue), this event point can either be of three cases (i.e. a left endpoint of a segment, a right endpoint of a segment, or an intersection point of two segments). Now, let's suppose it's a left endpoint of a segment. D. Mount suggests a way to compare if the line corresponding to new segment that we need to add to the sweep line status is below or above another line. I understand that and I understand his method. What I don't understand is how we go down the $T$ (from the root) to insert this new segment whose left endpoint corresponds to the current event point being processed, according to the description of the method the authors of the book regarding the storage of the segments in the tree $T$. In other words, given an event point corresponding to a left endpoint of a segment, which we want to add to $T$, how do we actual insert it into $T$ (in a self-balancing BST which needs to maintain the invariant that each internal node stores the rightmost segment or leaf of its left subtree), and maintaining the self-balancing BST $T$ as the authors of the book describe (and as I am describing above)?

$\endgroup$

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.