TRIANGULATING DISJOINT JORDAN CHAINS
- 1 December 1994
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 4 (4) , 475-481
- https://doi.org/10.1142/s0218195994000252
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+ε), for any fixed ε > 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 Ω (n + p log p).Keywords
This publication has 0 references indexed in Scilit: