ISSN:
1439-6912
Keywords:
51-04
;
52 A 37
;
68 R 05
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We show that the total combinatorial complexity of all non-convex cells in an arrangement ofn (possibly intersecting) triangles in 3-space isO(n 7/3 logn) and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement and an alternative less efficient, but still subcubic algorithm for calculating all non-convex cells, analyze some special cases of the problem where improved bounds (and faster algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02123007
Permalink
