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.