ISSN:
1572-9125
Keywords:
E.1
;
F.2.2
;
computational geometry
;
intersection detection
;
geometric duality
;
multidimensional search
;
hyperplane-polyhedron intersection
;
polyhedron-polyhedron intersection
;
arbitrary dimensions
;
linear programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract This paper presents a dual approach to detect intersections of hyperplanes and convex polyhedra in arbitrary dimensions. Ind dimensions, the time complexities of the dual algorithms areO(2 d logn) for the hyperplane-polyhedron intersection problem, andO((2d) d−1 log d−1 n) for the polyhedron- polyhedron intersection problem. These results are the first of their kind ford 〉 3. In two dimensions, these time bounds are achieved with linear space and preprocessing. In three dimensions, the hyperplane-polyhedron intersection problem is also solved with linear space and preprocessing; quadratic space and preprocessing, however, is required for the polyhedron-polyhedron intersection problem. For generald, the dual algorithms require $$O(n^{2^d } )$$ space and preprocessing. All of these results readily extend to unbounded polyhedra.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01952778
Permalink
