Reporting Red-Blue Intersections Between Two Sets Of Connected Line Segments
We present a new line sweep algorithm, {\sc HeapSweep}, for reporting bichromatic (`purple') intersections between a red and a blue family of line segments. If the union of the segments in each family is connected as a point set, {\sc HeapSweep} reports all $k$ purple intersections in time $O((n+k) \alpha(n) \log^3 n)$, where $n$ is the total number of input segments and $\alpha(n)$ is the familiar inverse Ackermann function. To achieve these bounds, the algorithm keeps only partial information about the vertical ordering between segments of the same color, using a new data structure called a {\em kinetic queue}. In order to analyze the running time of {\sc HeapSweep}, we also show that a simple polygon containing a set of $n$ line segments can be partitioned into monotone regions by lines cutting these segments $\Theta(n \log n)$ times.References:
- Proceedings of the 4th annual European Symposium on Algorithms, Barcelona
- Algorithmica 35:1-20 (2003)