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

We give a deterministic output-sensitive algorithm for computing the standard decomposition that runs in O(n log2 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(n2 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 log2 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
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 - | ![]() |
![]() |