A class of linear algorithms to process sets of segments

We address the problem of eciently performing operations on sets of segments. While current solutions to operate segments focus on single operations (e.g. insertion or searching), we are interested in set-oriented operations (e.g. union, dierence and others more specic to segments). In those cases, extending the current approaches leads to O(n logn) time complexity to manipulate sets of n elements. We show that a wide class of operations can in fact be performed in O(n) time, i.e. in a constant amortized cost per processed segment. We present the general framework and show a number of operations of that kind, depicting and analyzing the algorithms. Finally, we show some applications of this technique. This work has been supported in part by FONDECYT grants 1940271 and 1950622