Login
TitleBounded Boxes, Hausdorff Distance, and a New Proof of an Interesting Helly-Type Theorem (In Proceedings)
inProceedings of the 10th Annual ACM Symposium on Computational Geometry
Author(s) Nina Amenta
Year 1994
Pages340--347
Download
BibTeX
Abstract In the first part of this paper, we reduce two geometric optimization problems to convex programming: finding the largest axis-aligned box in the intersection of a family of convex sets, and finding the translation and scaling that minimizes the Hausdorff distance between two polytopes. These reductions imply that important cases of these problems can be solved in expected linear time. In the second part of the paper, we use convex programming to give a new, short proof of an interesting Helly-type theorem, first conjectured by Grunbaum and Motzkin.