A note on the minimum number of edge-directions of a convex polytope
type: Item
instance of: scholarly article
title: A note on the minimum number of edge-directions of a convex polytope
zbMATH Open document ID: 1060.52006
author: Shmuel Onn
author: Rom Pinchasi
published in: Journal of Combinatorial Theory. Series A
publication date: 2004-08-06T00:00:00Z
review text: The minimum number of different edge-directions of a convex \(n\)-gon is obviously \(\lceil\frac n2\rceil\). For higher dimensions, the authors prove that for any convex \(d\)-polytope with \(n\) vertices the number of distinct edge-directions is bounded from below by \(\frac{d-1}{2e} n^{1/ (d-1)}\), this lower bound being asymptotically tight and attained, up to a multiplicative factor, e.g., by zonotopes generated by points on the moment curve, and also by any cubical \(d\)-zonotope. From this the following corollary is obtained (regardless of the dimension of the polytope): The number of different edge-directions of any convex polytope with \(n\) vertices is \(\tfrac 12\log_en\).
reviewed by: Horst Martini
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 2083265
zbMATH Keywords: cubical zonotope
zbMATH Keywords: moment curve
zbMATH Keywords: oriented edge direction
zbMATH Keywords: combinatorial optimization
MaRDI profile type: Publication
full work available at URL: j.jcta.2004.03.008
OpenAlex ID: W2017671129
cites work: Momentopes, the complexity of vector partitioning, and Davenport-Schinzel sequences
cites work: Convex combinatorial optimization
cites work: A tight bound for the number of different directions in three dimensions
cites work: 2N noncollinear points determine at least 2N directions
DOI: 10.1016/J.JCTA.2004.03.008
description: scientific article; zbMATH DE number 2083265