Efficient reduction of L-infinity geometry problems

This paper presents a new method for computing optimal L_∞ solutions for vision geometry problems, particularly for those problems of fixed-dimension and of large-scale. Our strategy for solving a large L_∞ problem is to reduce it to a finite set of smallest possible subproblems. By using the fact that many of the problems in question are pseudoconvex, we prove that such a reduction is possible. To actually solve these small subproblems efficiently, we propose a direct approach which makes no use of any convex optimizer (e.g. SOCP or LP), but is based on a simple local Newton method. We give both theoretic justification and experimental validation to the new method. Potentially, our new method can be made extremely fast.