We present a new incremental algorithm for constructing the union of n
triangles in the plane. In our experiments, the new algorithm, which we
call the Disjoint-Cover (DC) algorithm, performs significantly better
than the standard randomized incremental construction (RIC) of the union.
Our algorithm is rather hard to analyze rigorously, but we provide an initial
such analysis, which yields an upper bound on its performance that is expressed
in terms of the expected cost of the RIC algorithm.
Our approach and analysis generalize verbatim to the construction of
the union of other objects in the plane, and, with slight
modifications, to three dimensions.
We present experiments with a software implementation of
our algorithm using the CGAL library of geometric algorithms.
Links
Eti Ezra,
Dan Halperin,
Micha Sharir, Speeding up the Inceremental Construction of the Union of Geometric
Objects in Practice Computational Geometry: Theory and Applications, 27 (2004), pp. 63-85.
Special issue, papers from the 18th European Workshop on Computational Geometry,
Warsaw, April 2002.
A preliminary version appeared in Proc. 10th Europen Symposium on Algorithms (ESA) , Rome, 2002, 473-484.
[BibTex,
PostScript]
Contact
Eti Ezra
Site is maintained by
Efi Fogel.
Last modified: June 01 2004.
![[Union]](../images/union.gif)
![[Projects Page]](../images/icons/projects.gif){kind=icon}
![[Top]](../images/icons/top.gif){kind=icon}
