‘Shear’ convex polyhedra

I came up with what seems quite a beautiful geometric construction solving the problem described below. On a compact convex set  C \subset \mathbb{R}^n  consider the function

\displaystyle w_1(x) = \max_{y \in C}\, y_1 - \min_{y \in C}\, y_1

\displaystyle\text{s.t.}\,\,\,\, y_2=x_2,\, ...,\, y_n = x_n.

where we denote x = (x_1,\, ...,\, x_n).  In other words, “hanging” in the point  x,  we measure the “width” of the set along the first axis of the Cartesian system (note that  w_1(x)  actually doesn’t depend on x_1). In the same fashion we define functions  w_2(x),\, ...,\, w_n(x)  (w_i(x) measures the “width” along the i-th axis). Now consider the following functionals of  C:

\displaystyle w^*(C) = \max_{x \in C} \left[\sum_{i=1}^n w_i(x)\right];

\displaystyle w_i^*(C) = \max_{x \in C}\, w_i(x);

\displaystyle W^*(C) = \sum_{i=1}^n w_i^*(C).

Namely,  w^*  is the maximum sum of “widths”, whereas  W^*  is the sum of maximum “widths”, hence  w^* \le W^*.  Moreover,  w^* = W^*  for some archetypal examples of convex polyhedra: hyperrectangle (box) and rectangular simplex, and it is easy to begin thinking that we have equality for any convex polyhedra. To give a partial justification for this intuition (which is though incorrect in general), consider rectangular convex polyhedra: to build such a polyhedron in  \mathbb{R}^n,  we fix a pair of points  (x_i, y_i)  on each coordinate axis i, and then take the convex hull of these  2n  points. We can easily prove the following geometric fact about such polyhedra:


For any rectangular (in the sense defined above) convex polyhedron in  \mathbb{R}^2, that is, rectangular convex quadrilateral, it holds  w^* = W^*.

However already in  n = 3  one may find a convex polyhedron (in fact a rectangular one), such that  w^* < W^*.


Point out a sequence  \{P_n\},  P_n \in \mathbb{R}^n,  of  [‘shear’]  convex polyhedra, for which

\displaystyle W^*(P_n) = \Theta(n), \quad \text{but} \quad w^*(P_n) = O(1).

Later on I will describe the solution to this problem.


About Dmitry Ostrovsky

PhD student with interests in learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.
This entry was posted in Pretty little things and tagged , . Bookmark the permalink.

One Response to ‘Shear’ convex polyhedra

  1. Pingback: ‘Shear’ convex polyhedra: solution | Look at the corners!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s