A bound on local minima of arrangements that implies the upper bound theorem |
| |
Authors: | Kenneth L. Clarkson |
| |
Affiliation: | (1) AT&T Bell Laboratories, 600 Mountatin Avenue, 07974 Murray Hill, NJ, USA |
| |
Abstract: | This paper shows that thei-level of an arrangement of hyperplanes inE d has at most local minima. This bound follows from ideas previously used to prove bounds on (≤k)-sets. Using linear programming duality, the Upper Bound Theorem is obtained as a corollary, giving yet another proof of this celebrated bound on the number of vertices of a simple polytope inE d withn facets. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|