|
Abstract : |
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., |
