‘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:


Lemma

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^*.


Problem

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 statistics, optimization, and machine learning.
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