A Class of Linear Algorithms to Process Sets of Segments

Gonzalo Navarro and Ricardo Baeza-Yates

We address the problem of efficiently 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, difference and others more specific to segments). In those cases, extending the current approaches leads to O (n log n) 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.