This article discusses a discrete version of the convex minimization problem with applications to the efficient computation of proximity measures for pairs of convex Ž d . polyhedra. Given a d-variate convex function and an isothetic grid of size O n in ޒ d , which is supposed to be finite but not necessarily regular, we want to find the grid cell containing the minimum point. With this aim, we identify a class of elementary subproblems, each resulting in the determination of a half-space in ޒ d , Ž . and show that the minimization problem can be solved by computing O log n half-spaces in the worst case for almost uniform grids of fixed dimension d and Ž . Olog n half-planes in the average for arbitrary planar grids. A major point is the potential of the approach to uniformly solve distance related problems for different configurations of a pair of convex bodies. In this respect, the case of a bivariate function is of particular interest and leads to a fast algorithm for detecting collisions between two convex polyhedra in three dimensions. The collision algo-Ž 2 . Ž . rithm runs in O log n average time for polyhedra with O n vertices whose boundaries are suitably represented; more specifically, the 1-skeletons can be Ž . embedded into layered Directed Acyclic Graphs which require just O n storage. The article ends with a brief discussion of a few experimental results.
ᮊ 1998
Academic Press
1. Introduction
The main focus of this paper is on the following points:
- Given a d-variate convex function f, we can find the cell of an isothetic grid in ޒ d which contains the minimum point by probing suitable properties of f a polylogarithmic number of times, where the size of the input is measured by the number of hyperplanes defining the grid. Moreover, the amount of required probes is simply logarithmic in the average for planar grids.