@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)$.",
}