Online Maintenance of Disjoint Line Segment Sets Utilizing Treap and Strict partial Ordering Theory

In the realm of computational geometry and data management, the efficient maintenance of a dynamic set of disjoint line segments is a critical requirement for various applications, such as the activity selection problem and other scheduling tasks. We introduce two novel methods for online maintenance of disjoint line segments, focusing on the rapid identification and summarization of intersecting segments, as well as the insertion and removal of activities within a set. The methods presented in this paper facilitate the following operations: quickly identifying all intersecting segments and summarizing their attributes (e.g., count, weight), and, if required, removing them to accommodate the insertion of a new segment. Assuming a set size of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> and a subset size of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">w</tex> for intersecting line segments. Utilizing standard library data structures like the set from C++ STL, a time complexity of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(wlogn)</tex> is achieved for these operations. By implementing a self-balancing binary search tree, such as a treap, the time complexity for these operations is further reduced to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(logn)</tex> .