Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A subset of $\mathcal{X} \times \mathcal{Y} \subset \mathbb{R}^d \times \mathbb{R}^d$ is cyclically monotone if $\sum_{i=1}^n \langle x_i,y_i\rangle \ge \sum_{i=1}^n \langle x_i,y_{i+1}\rangle$, where $y_{n+1} = y_1$ and $\{x_i\} \subset \mathcal{X}$ and $\{y_i\} \subset \mathcal{Y}$ are some arbitrary subsets of $\mathcal{X}$ and $\mathcal{Y}$.

It is easy to see that if $\mathcal{Y} = \{y_1,y_2\}$ has only two elements, a general cyclically monotone set has the from $\{(x,y) : y = \phi(x)\}$ where $\phi(x) = y_1$ if $\langle x,\theta_1-\theta_2\rangle \ge \tau$ and $\phi(x) = y_2$ otherwise. In other words, it is of the form $\cup_{i=1}^2 S_i \times \{y_i\}$ where $S_i$ are two complementary half-spaces.

Now, is there a "nice" description of cyclically monotone sets when $\mathcal{Y}$ has four points, or the situation is too complicated in general? (Nice here is a bit subjective ...)

share|cite|improve this question
Do you understand the intermediate case of three points? – user53153 Mar 5 '13 at 4:57
@ 5pm: Yes. I also understand the case of four points, but I wanted to see if anyone can come up with a simpler description. (Maybe it is not possible.) By looking at the dual problem, the region that is mapped to a particular $y_i$ corresponds to the region where the maximum of a collection of affine functions is achieved by the $i$th affine function. Four the three point case, this always produces three half-spaces which meet at a common boundary. (In the plane, they meet in a point and produce a star-shaped partition.) The situation seems to be more complicated for 4 points and beyond. – passerby51 Mar 5 '13 at 16:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.