Two randomized incramental algorithms for planar arrangements, with a twist

Pankaj K. Agarwal, and Sariel Har-Peled

• An algorithm for computing the union of triangles in the plane in a quasi output-sensitive time.

• A more efficient alternative to vertical decomposition of arrangements of lines in the plane, called \em polygonal decomposition . An efficient randomized incremental algorithm for its construction is presented, and we prove that the size of the resulting decomposition is asymptotically equivalent to size of vertical decomposition. In particular, this representation is more compact than vertical decomposition, and there is ground to believe that in practice it will perform better.

The common theme of those results is their unconventional nature, as both algorithms falls outside the classing settings in computational geometry for randomized incremental algorithms.