Speeding up the incremental construction of the union of geometric objects in practice. (Q1421031)

A new incremental algorithm called disjoint-cover (DC) algorithm for constructing the union of \(n\) triangles in the plane is given. Experimental results are presented to show that DC algorithm performs better and significantly better in some cases than the randomized incremental construction (RIC) of the union. It is also observed that the DC algorithm can be generalized for other geometric objects in the plane, and also can be extended to higher dimensions. Very recently the authors have also applied the DC algorithm to the problem of constructing efficiently (in subquadratic time) the union of \(n\) triangles when the union is determined by only a small (unknown) subset of the input triangles. This has been reported in a work by \textit{E. Ezra} and \textit{M. Sharir} [Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Alogrithms (SODA, 04), SIAM (2004)].