Convex Minimization on a Grid and Applications

• Main Author: MIROLO, Claudio
• Other Authors: Mirolo, Claudio
• Format: Article in Journal/Newspaper
• Language: English
• Published: 1998
• Subjects: Major Point; Artide
• Online Access: http://hdl.handle.net/11390/679885

This artide discussesa discrete version of the convex minimization problem with applicationsto the efficient computation of proximity measures for pairs of convex polyhedra. Given a d-variate convex function and an isothetic grid of size O(nd) 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 dass 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 O(log 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-rithm runs in O(log2n) 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.