Improved Output-Sensitive Construction of Vertical Decompositions of Triangles in 3D

Abstract

This work deals with vertical decompositions of n triangles in three-dimensional space. We describe a new decomposition scheme for triangles in three-dimensional space which in most cases produces less cells than the standard vertical decomposition. A cell in this decomposition might have complexity θ(n), however each of the cells is convex. We show by experiments that in practice our new scheme is more favorable than the standard vertical decomposition.

We give a deterministic output-sensitive algorithm for computing the standard decomposition that runs in O(n log² n + V log n), where V is the complexity of the decomposition. This is a significant improvement over the best previously known algorithm whose running time is O(n² log n + V log n). We also give a deterministic output-sensitive algorithm for computing the new decomposition we describe that runs in O(n log² n + V log n), where V is the complexity of the decomposition.

We implemented the two algorithms and ran them on a series of scenes. We ran programs that use decompositions for their calculations and tried them on the output of the two decompositions. Our results show that programs usually benefit from the new decomposition we propose here. Our algorithms make use of a dynamic point location data structure. By using a trivial point location in restricted number of places, the algorithms become very simple and effective (in particular they perform only a space sweep, and all the computations are done in two dimensions on the sweep plane).

We also show how to extend these algorithms to the case of a vertical decomposition of polyhedral surfaces. We implemented these extensions as well.

 

More Information

Experiments

Exact Computation

Links

• Hayim Shaul and Dan Halperin
  Improved Construction of Vertical Decompositions of 3D Arrangements
  In Proceedings of the 18th ACM Symposium on Computational Geometry (SoCG), pages 283-292, Barcelona, 2002 [link] [bibTex]
• Hayim Shaul
  Improved Output Sensitive Construction of Vertical Decompositions of Triangles in 3D Space
  M.Sc. Thesis [pdf] [bibtex]

Contact

Hayim Shaul -