Overlaying simply connected planar subdivisions in linear time
Ulrich Finke, Klaus Hinrichs · 1995
We present an algorithm which computes the overlay Hb r+ rIg of two Simply connected planar subdivisions ~b and Hg; we assume that ~b (resp.~) and all its components are colored in blue (resp.green).The algorithm runs in O(n + k) time and space, where n denotes the total nuruber of edges of ~b and IIg and k the number of intersections between blue and green edges.