An efficient algorithm for determining the extreme vertices of a moving 3D convex polyhedron with respect to a plane

Abstract

We present an efficient algorithm for finding the sequence of extreme vertices of a moving convex polyhedron P with respect to a fixed plane H. Using the spherical extreme vertex diagram due to the point-plane duality, we are able to find such a sequence in O(log n + Sigma(j=1)(s) m(j)) time, where s is the number of extreme vertices in the sequence, and m(j), 1 less than or equal to j less than or equal to s, is the number of edges of the spherical region S-vj corresponding to an extreme vertex v(j) in the sequence. (C) 1998 Elsevier Science Ltd. All rights reserved.