Personal tools
You are here: Home Projects Internal Projects Union of Objects
« April 2017 »
April
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
30
Log in


Forgot your password?
 

Speeding up the Inceremental Construction of the Union of Geometric Objects in Practice

[Union]

Abstract

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

  • Esther Ezra, Dan Halperin, Micha Sharir,
    Speeding up the Incremental Construction of the Union of Geometric Objects in Practice
    Computational Geometry: Theory and Applications, 27(1): 63-85, 2004 [link] [bibtex]
    A preliminary version appeared in Proceedings of the 10th European Symposium on Algorithms (ESA), 473-484, Rome, 2002 [link] [bibtex]

Contact

Esther Ezra http://www.cs.tau.ac.il/~estere estere@post.tau.ac.il
Document Actions