@Article{BarCha94, author = "R. Bar-Yehuda and B. Chazelle", title = "Triangulating Disjoint Jordan Chains", journal = "Int. J. of Computational Geometry \& Appl.", volume = "4", number = "4", pages = "475--481", year = "1994", abstract = "Recent advances on polygon triangulation have yielded efficient algorithms for a large number of problems dealing with a single simple polygon. If the input consists of several disjoint polygons, however, it is often desirable to merge them in preprocessing so as to produce a single polygon that retains the geometric characteristics of its individual components. We give an efficient method for doing so, which combines a generalized form of Jordan sorting with the efficient use of point location and interval trees. As a corollary, we are able to triangulate a collection of $p$ disjoint Jordan polygonal chains in time $O(n+p (\log p)^{1+\epsilon})$, for any fixed $\epsilon > 0$, where $n$ is the total number of vertices. A variant of the algorithm gives a running time of $O((n+p \log p) \log \log p)$. The performance of these solutions approaches the lower bound of $\Omega(n+p \log p)$.", }