Loading...
Please wait, while we are loading the content...
Similar Documents
Vertical DecompositionsSubmitted to Discrete and Computational Geometryfor Triangles in 3-Space
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bergy, Mark De Guibasz, Leonidas J. Halperinx, Dan |
| Copyright Year | 1995 |
| Abstract | We prove that, for any constant " > 0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n 2+" + K), where K is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to be O(n 2+"). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs in O(n 2 log n + V log n) time, where V is the complexity of the decomposition. The algorithm is reasonably simple (in particular , it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for eecient implementations. The algorithm is extended to compute the vertical decomposition of arrangements of n algebraic surface patches of constant maximum degree in three-dimensional space in time O(nn q (n) log n + V log n), where V is the combina-torial complexity of the vertical decomposition, q (n) is a near-linear function related to Davenport-Schinzel sequences, and q is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the rst algorithm. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://robotics.stanford.edu/users/assembly/dBGH.ps.gz |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
