Convex Sequence and Convex Polygon

Angshuman R. Goswami; István Szalkai

doi:10.2478/amsil-2025-0016

1. Introduction

Throughout this paper, ℕ, ℝ, and ℝ₊ denote the set of natural, real, and positive numbers respectively. ℝ² is used to indicate the usual 2-dimensional plane.

A sequence ${(u_{i})}_{i = 0}^{\infty}$ is said to be convex if it satisfies the following inequality

\begin{matrix} 2 u_{i} \leq u_{i - 1} + u_{i + 1} & for all & i \in ℕ . \end{matrix}

In other words,

{(u_{i})}_{i = 0}^{\infty}

possesses sequential convexity if the sequence

{(u_{i} - u_{i - 1})}_{i = 1}^{\infty}

is increasing. If the converse of the above inequality holds, we call

{(u_{i})}_{i = 0}^{\infty}

a concave sequence.

The earliest occurence of the term of sequential convexity was used is the book [14]. Since then many important results have been discovered in this direction, such as establishing a discrete version of Hermite-Hadamard type inequality, Ulam's type stability theorems, applications in the field of trigonometric functions, generalization of sequential convexity to the higher order and in approximate sense. The details of these facts can be found in the papers [5, 6, 8,9,10,11,12,13,14,15,16, 19, 21] and in the references mentioned there.

In discrete geometry, there are many results that primarily mention about the scattered random points and the underlying convex geometry. One of the familiar examples of it is well-known Radon's theorem. Helly's and Carathéodory's results also indirectly deal with the same. The background, origin, generalization, and other research developments related details can be found in the papers [1, 3, 7, 18, 20] and in the book [2]. There are many tempting open problems that deal with questions regarding the possibilities of existing a specifically shaped convex body in a higher dimensional space provided the scattered point bounds with some specific patterns or numbers. For instance, the famous Erdös-Szekeres conjecture is still unsolved even after almost 90 years since its first formulation. For better understanding of the problem, we can look into [4].

The purpose of this paper is to investigate the underlying necessary and sufficient condition for n distinct points in ℝ², namely P₁(x₁, y₁),…, and P_n(x_n, y_n) with x₁ <…< x_n, such that a convex n-gon can be formed. It turns out that if the following inequality holds

\begin{matrix} \frac{y_{i} - y_{i - 1}}{x_{i} - x_{i - 1}} \leq \frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}} & for all & i \in {2, \dots, n - 1} \end{matrix}

then the line segments

\bar{P_{1} P_{2}}, \dots, \bar{P_{n} P_{1}}

form a convex polygon with n-sides that lies below

\bar{P_{n} P_{1}}

. The converse is also true. Similarly, under the same assumptions, the reverse inequality holds if and only if the convex n-gon lies above the line segment

\bar{P_{n} P_{1}}

Based on this result, we derive some other interesting findings. We assume some sequential convexity properties on ${(x_{i})}_{i = 1}^{n}$ and ${(y_{i})}_{i = 1}^{n}$ as follows:

(i) ${(x_{i})}_{i = 1}^{n}$ is strictly increasing and concave,
(ii) ${(y_{i})}_{i = 1}^{n}$ is increasing and convex.

Then P₁,…, P_n are the vertices of an n-convex polygon. A more general version of this result is also presented.

Having prior knowledge of the vertices of a convex polygon often simplifies many mathematical and computational tasks. In linear programming problems, the optimized value of the cost function always lies at one of the vertices of the constrains formulated convex polygon. In computational geometry, efficient algorithms are highly dependent upon the extreme points of convex n-gons. In computer graphics, various rotation, translation and orientation related techniques are performed at the end points of a convex polygon.

In the way of proving our results, we establish several lemmas and propositions related to fractional inequality, convex sequence, and convex function theory.

2. Main results

Our first result shows a very important fractional inequality. Later, this inequality is going to be used extensively to establish some of the results. This inequality is also mentioned in one of our recently submitted papers. However, for the sake of readability, we restate the result together with its proof.

Lemma 2.1

Let n ∈ ℕ be arbitrary. Then for any a₁,…, a_n ∈ ℝ and b₁,…, b_n ∈ ℝ₊, the following inequalities hold

(1)

min \frac{a_{1}}{b_{1}}, \dots, \frac{a_{n}}{b_{n}}\} \leq \frac{a_{1} + \dots + a_{n}}{b_{1} + \dots + b_{n}} \leq max \frac{a_{1}}{b_{1}}, \dots, \frac{a_{n}}{b_{n}}\} .

Proof

We prove the theorem by using mathematical induction. For n = 1, there is nothing to prove. For a₁, a₂ ∈ ℝ and b₁, b₂ ∈ ℝ₊, without loss of generality assume that $\frac{a_{1}}{b_{1}} \leq \frac{a_{2}}{b_{2}}$ , which is equivalent to

\begin{matrix} a_{1} (b_{1} + b_{2}) \leq (a_{1} + a_{2}) b_{1} & and & (a_{1} + a_{2}) b_{2} \leq (b_{1} + b_{2}) a_{2} . \end{matrix}

The two inequalities above together yield the following

(2)

\frac{a_{1}}{b_{1}} \leq \frac{a_{1} + a_{2}}{b_{1} + b_{2}} \leq \frac{a_{2}}{b_{2}},

which validates (1) for n = 2. Now we assume that the statement is true for an n ∈ ℕ. Let a₁,…, a_n, a_n+1 ∈ ℝ and b₁,…, b_n, b_n+1 ∈ ℝ₊. Using (2) and our induction assumption (1), we can compute the following inequalities

min \frac{a_{1}}{b_{1}}, \dots, \frac{a_{n}}{b_{n}}, \frac{a_{n + 1}}{b_{n + 1}}\} \leq min \frac{a_{1} + \dots + a_{n}}{b_{1} + \dots + b_{n}}, \frac{a_{n + 1}}{b_{n + 1}}\} \leq \frac{a_{1} + \dots + a_{n} + a_{n + 1}}{b_{1} + \dots + b_{n} + b_{n + 1}},

and

\frac{a_{1} + \dots + a_{n} + a_{n + 1}}{b_{1} + \dots + b_{n} + b_{n + 1}} \leq max \frac{a_{1} + \dots + a_{n}}{b_{1} + \dots + b_{n}}, \frac{a_{n + 1}}{b_{n + 1}}\} \leq max \frac{a_{1}}{b_{1}}, \dots, \frac{a_{n}}{b_{n}}, \frac{a_{n + 1}}{b_{n + 1}}\} .

This justifies (1) for any n ∈ ℕ and completes our proof.

As a consequence of the above result, we can obtain several mean inequalities. If b₁ =…= b_n = 1, then (1) turns into the standard arithmetic mean inequality which is represented as follows

min a_{1}, \dots, a_{n}\} \leq \frac{a_{1} + \dots + a_{n}}{n} \leq max a_{1}, \dots, a_{n}\} .

On the other hand, we can consider b_i = 1/x_i and a_i = 1 for all i ∈ {1,…, n}. Upon substituting these in (1), we get the Harmonic mean inequality for the positive numbers x₁, … , x_n that can be formulated as

min x_{1}, \dots, x_{n}\} \leq \frac{n}{\frac{1}{x_{1}} + \dots + \frac{1}{x_{n}}} \leq max x_{1}, \dots, x_{n}\} .

Before moving to the main result of this section, there are some notions and terminology that we need to recall. There are several ways to represent a convex function. Besides the standard definition of convexity, for any given function, the monotonic property of the associated slope function can also be used to determine convexity. In other words, a function f : I → ℝ is said to be convex if for any x^′, x and x^″ ∈ I with x^′ < x < x^″, the following inequality holds

(3)

\frac{f (x) - f (x^{'})}{x - x^{'}} \leq \frac{f (x^{″}) - f (x)}{x^{″} - x} .

The other concept we are going to use is the epigraph of a function. For a function f : I → ℝ; the notion of epigraph can be formulated as follows

epi (f) = (x, y) : f (x) \leq y, x \in I\} .

One of the basic characterizations of a convex function can be stated as “A function f is convex if and only if epi(f) is a convex set.”

Now, we have all the required tools to proceed to state the first theorem.

Theorem 2.2

Let P₁(x₁, y₁),…, P_n(x_n, y_n) be n points (n ≥ 3) with x₁ < … < x_n. Then $\bar{P_{1} P_{2}}, \dots, \bar{P_{n} P_{1}}$ form a convex n-gon in the half-space

(4)

ℋ ¯ = (x, y) | x \in ℝ and y \leq y_{1} + (\frac{x - x_{1}}{x_{n} - x_{1}}) (y_{n} - y_{1})\} \subseteq ℝ^{2}

if and only if the following inequality holds

(5)

\begin{matrix} \frac{y_{i} - y_{i - 1}}{x_{i} - x_{i - 1}} \leq \frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}} & for all & i \in {2, \dots, n - 1} . \end{matrix}

Proof

There are several steps involved in the proof. First, we assume that (5) is valid. We define the function f : [x₁, x_n] → ℝ as follows

(6)

\begin{array}{l} f (x) : = t y_{i} + (1 - t) y_{i + 1} & where & x : = t x_{i} + (1 - t) x_{i + 1} \\ (t \in [0, 1] and {i \in 1, \dots, n - 1}) . \end{array}

From the construction, it is clear that f is formulated by joining total n − 1 consecutive line segments that are defined between the points x_i and x_i₊₁ for all i ∈ {1,…, n − 1}. We call these as functional line segments of f. For the proof, first we are going to establish that the function f is convex. But before that, we need to validate the statement below.

(7)

\begin{array}{l} For x_{1} \leq x^{'} < x^{″} \leq x_{n} : \\ slope of the functional line segment (s) of f that contains (x^{'}, f (x^{'})) \\ \leq slope of the line joining the points (x^{'}, f (x^{'})) and (x^{″}, f (x^{″})) \\ \leq slope of the functional line segment (s) of f that contains (x^{″}, f (x^{″})) \end{array}

If both the points (x^′, f(x^′)) and (x^″, f (x^″)) lie in the same functional line segment, the statement is obvious.

Next, we consider the case when x^′ ∈ [x_i−1, x_i[ and x^″ ∈]x_i, x_i+1] (i ∈ {2,…, n − 1}), that is x^′ and x^″ lie in two consecutive intervals. Using (5) and basic geometry of slopes in straight lines, we can compute the inequality below

(8)

\frac{f (x_{i}) - f (x^{'})}{x_{i} - x} = \frac{f (x_{i}) - f (x_{i - 1})}{x_{i} - xi - 1} \leq \frac{f (x_{i + 1}) - f (x_{i})}{x_{i + 1} - x_{i}} = \frac{f (x^{″}) - f (x_{i})}{x^{'} - x_{i}} .

The expression

\frac{f (x^{″}) - f (x^{'})}{x^{″} - x^{'}}

can also be written as

\frac{f (x^{″}) - f (x_{i}) + f (x_{i}) - f (x^{'})}{(x^{″} - x_{i}) + (x_{i} - x^{'})} .

This, along with (2) and (8), yields

\frac{f (x_{i}) - f (x^{'})}{x_{i} - x^{'}} \leq \frac{f (x^{″}) - f (x^{'})}{x^{″} - x^{'}} \leq \frac{f (x^{″}) - f (x_{i})}{x^{″} - x_{i}}

and validates the statement (7) for this particular case.

Finally, we assume x^′ ∈ [x_j, x_j+1], x^″ ∈ [x_k, x_k+1] where j ∈ {1,…, n − 3} and k ∈ {3,…, n − 1} such that k − j ≥ 2. First, using (1) of Lemma 2.1 and then by applying (5), we obtain the inequality below

\begin{array}{l} \frac{f (x^{″}) - f (x^{'})}{x^{″} - x^{'}} \\ = \frac{(f (x^{″}) - f (x_{k})) + (f (x_{k}) - f (x_{k - 1})) + \dots + (f (x_{j + 1}) - f (x^{'}))}{(x^{″} - x_{k}) + (x_{k} - x_{k - 1}) + \dots + (x_{j + 1} - x^{'})} \\ \leq \max \frac{f (x^{″}) - f (x_{k})}{x^{″} - x_{k}}, \frac{f (x_{k}) - f (x_{k - 1})}{x_{k} - x_{k - 1}}, \dots, \frac{f (x_{j + 1}) - f (x_{j})}{x_{j + 1} - x_{j}}\} \\ = \frac{f (x^{″}) - f (x_{k})}{x^{″} - x_{k}} = \frac{f (x_{k + 1}) - f (x_{k})}{x_{k + 1} - x_{k}} . \end{array}

Similarly, we can compute the following inequality as well

\begin{array}{l} \frac{f (x_{j + 1}) - f (x_{j})}{x_{j + 1} - x_{j}} = \frac{f (x_{j + 1}) - f (x^{'})}{x_{j + 1} - x^{'}} \\ = min \frac{f (x_{j + 1}) - f (x^{'})}{x_{j + 1} - x^{'}}, \frac{f (x_{j + 2}) - f (x_{j + 1})}{x_{j + 2} - x_{j + 1}}, \dots, \frac{f (x^{″}) - f (x_{k})}{x^{″} - x_{k}}\} \\ \leq \frac{(f (x_{j + 1}) - f (x^{'})) + (f (x_{j + 2}) - f (x_{j + 1})) + \dots + (f (x^{″}) - f (x_{i}))}{(x_{j + 1} - x^{'}) + (x_{j + 2} - x_{j + 1}) + \dots + (x^{″} - x_{k})} \\ = \frac{f (x^{″}) - f (x^{'})}{x^{″} - x^{'}} . \end{array}

The above two inequalities establish the statement (7).

We are now ready to show that f is convex. We assume x^′, x, x^″ ∈ [x₁, x_n] with x^′ < x < x^′′. More specifically, x^′ ∈ [x_j, x_j₊₁], x ∈ [x_i, x_i₊₁] and x^″ ∈ [x_k, x_k₊₁] for fixed i, j and k ∈ {1,…, n − 1}. Then, first using the last part of inequality in (7) and then applying the initial part of the same inequality, we obtain the following

\frac{f (x) - f (x^{'})}{x - x} \leq \frac{f (x_{i + 1}) - f (x_{i})}{x_{i + 1} - x_{i}} = \frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}}

and

\frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}} = \frac{f (x_{i + 1}) - f (x_{i})}{x_{i + 1} - x_{i}} \leq \frac{f (x^{″}) - f (x)}{x^{″} - x} .

Combining the above two inequalities, we arrive at (3). It shows that the function f is convex and also implies that epi(f) is an unbounded convex polygon. Due to the convexity property of f, the line segment

\bar{P_{n} P_{1}}

, which is formed by joining (x₁, y₁) and (x_n, y_n), lies entirely in epi(f). The extension of

\bar{P_{n} P_{1}}

creates two closed convex half-spaces. One of these is defined as in (4).

All this yields that ℋ∩ epi(f) is the convex polygon $\bar{P_{1} P_{2}}, \bar{P_{2} P_{3}}, \dots, \bar{P_{n} P_{1}}$ that lies in ℋ.

Conversely, suppose that under the strict monotonic assumptions on $x_{i}^{'} s$ , the n distinct points P₁,…, P_n form a convex polygon. A convex polygon is actually the intersection of a finite number of 2-dimensional hyp erplanes. By neglecting the underlying hyperplane due to the extension of $\bar{P_{n} P_{1}}$ , we will end up in an unbounded convex polygon formed by the line segments $\bar{P_{1} P_{2}}, \dots, \bar{P_{n - 1} P_{n}}$ . In other words, this unbounded convex set is just the epigraph of the function f : [x₁, x_n] → ℝ defined in (6). Convexity of epi(f) implies that f is a convex function. Since P₁(x₁, y₁),…, P_n(x_n, y_n) ∈ gr(f), by (3) we can also conclude that (5) holds. This completes the proof of the statement.

Remark

In the above theorem, the strict monotonicity of the sequence ${(x_{i})}_{i = 1}^{n}$ can be relaxed at the end points. For instance, instead of strict increasingness, we can assume that the elements of the sequence ${(x_{i})}_{i = 1}^{n}$ satisfies the following inequality

x_{1} \leq x_{2} < x_{3} < \dots < x_{n - 1} \leq x_{n} .

In the case of x₁ = x₂, the points P₁,…, P_n still form an n-sided convex polygon provided (5) holds for all i ∈ {2,…, n − 1}. Similar to the proof of Theorem 2.2, one can show that, by joining n − 1 distinct points (x₂, y₂),…, (x_n, y_n), we can construct the convex function f. Then ℋ∩epi(f) is a convex set. This set is bounded from below by the n− 2 line segments that form the function f. The line segment joining the points (x₁, y₁) and (x_n, y_n) gives the upper bound. And finally, the line segment that passes through (x₁, y₁) and (x₂, y₂) also lies in the set. In other words, we ended up in a convex polygon which is formed by the line segments

\bar{P_{1} P_{2}}, \dots, \bar{P_{n} P_{1}}

. Similar conclusion can be drawn by considering equality at the rightmost end point or simultaneously at both end points of the sequence

{(x_{i})}_{i = 1}^{n}

Besides, it is worth mentioning that some related ideas of the above theorem, though in a different context, can be found in the paper [17].

We can now establish the following theorem. The proof is analogous to Theorem 2.2. Hence, the proof is not included.

Theorem 2.3

Let P₁(x₁, y₁),…, P_n(x_n, y_n) be n points (n ≥ 3) with x₁ <…< x_n. Then $\bar{P_{1} P_{2}}, \dots, \bar{P_{n} P_{1}}$ form a convex n-gon in the half-space

ℋ ¯ = (x, y) | x \in ℝ and y_{1} + (\frac{y_{n} - y_{1}}{x_{n} - x_{1}}) (x - x_{1})\} \subseteq ℝ^{2}

if and only if the following inequality holds

\begin{matrix} \frac{y_{i} - y_{i - 1}}{x_{i} - x_{i - 1}} \geq \frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}} & for all & i \in 2, \dots, n - 1\} . \end{matrix}

In the next section, we are going to see how sequential convexity is linked with a convex polygon.

3. The subsequent results

The results of this section heavily depend on the previous section's findings.

The initial proposition resembles the slope property of a convex function.

Proposition 3.1

Suppose ${(x_{i})}_{i = 0}^{\infty}$ is a strictly increasing and concave sequence and ${(y_{i})}_{i = 0}^{\infty}$ is an increasing and convex sequence. Then for any i ∈ ℕ, the following discrete functional inequality holds

(9)

\frac{y_{i} - y_{i - 1}}{x_{i} - x_{i - 1}} \leq \frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}} .

Proof

By our assumptions, 0 < x_i₊₁−x_i ≤ x_i −x_i−₁ and 0 ≤ y_i −y_i−₁ ≤ y_i₊₁ − y_i. Multiplying these two inequalities side by side and rearranging the terms of the resultant inequality, we obtain (9).

In the above proposition, the respective positive/non-negative conditions in sequences ${(x_{i} - x_{i - 1})}_{i = 1}^{\infty}$ and ${(y_{i} - y_{i - 1})}_{i = 1}^{\infty}$ cannot be compromised. One can easily verify this fact by relaxing this crucial condition. Similarly to the above proposition, we can also show the next result.

Proposition 3.2

Suppose ${(x_{i})}_{i = 0}^{\infty}$ is a strictly increasing convex sequence and ${(y_{i})}_{i = 0}^{\infty}$ is a decreasing convex sequence. Then, for any i ∈ ℕ, the discrete functional inequality (9) is satisfied.

Now, we can propose the first theorem of this section. The establishment of it is similar to the first part of Theorem 2.2.

Theorem 3.3

Let P₁,…, P_n be n points with the respective coordinates (x₁, y₁),…, (x_n, y_n) scattered in ℝ² such that the sequences: ${(x_{i})}_{i = 1}^{n}$ is strictly monotone and concave, while ${(y_{i})}_{i = 1}^{n}$ is convex and increasing. Then $\bar{P_{1} P_{2}}, \dots, \bar{P_{n - 1} P_{n}}$ form a convex polygon.

Proof

This theorem is a direct consequence of Proposition 3.1 and Theorem 2.2.

The converse of the above theorem is not necessarily always true. We consider the three vertices of the ΔP₁P₂P₃ as P₁(0, 0), P₂(2, 2) and P₃(3, 1). One can easily observe that both the X and Y-coordinated sequences are strictly concave which shows that the reverse implication is not valid.

The next result is similar to the above one. By using Proposition 3.2 and Theorem 2.2, we can establish it.

Theorem 3.4

Let P₁,…, P_n be n points with the respective coordinates (x₁, y₁),…, (x_n, y_n) scattered in ℝ² such that the sequences: ${(x_{i})}_{i = 1}^{n}$ is strictly monotone and convex, while ${(y_{i})}_{i = 1}^{n}$ is convex and decreasing. Then $\bar{P_{1} P_{2}}, \dots, \bar{P_{n - 1} P_{n}}$ form a convex polygon.

A more general result can be formulated by combining these two theorems. But before proceeding, we must go through a proposition.

Proposition 3.5

Let ${(u_{i})}_{i = 1}^{n}$ be a convex sequence. Then there exists an element m ∈ ℕ ∩ [1, n] that satisfies at least one of the following

(10)

u_{i} \leq u_{m} for all i < m or u_{m} \leq u_{i} for all m < i .

Proof

The sequential convexity of ${(u_{i})}_{i = 1}^{n}$ implies increasingness of the sequence ${(u_{i + 1} - u_{i})}_{i = 1}^{n - 1}$ . If all the terms in this monotone sequence are either non-negative or non-positive, then one can easily validate (10). If not, then there exists a m ∈ ℕ∩ ]1, n[ such that the following inequalities hold

\begin{matrix} u_{m + 1} - u_{m} \geq 0 & and & u_{m} - u_{m - 1} \leq 0. \end{matrix}

This together with non-decreasingness property of the sequence

{(u_{i + 1} - u_{i})}_{i = 1}^{n - 1}

yields (10) and completes the proof of the statement.

The next theorem generalizes our previous results from Theorem 3.3 and Theorem 3.4. Therefore, just a scratch of the proof is mentioned.

Theorem 3.6

Let P₁,…, P_n be n distinct points with the respective coordinates (x₁, y₁),…, (x_n, y_n) scattered in ℝ². Additionally, let the sequence ${(y_{i})}_{i = 1}^{n}$ be convex with $min_{i \leq i \leq n} y_{i} = y_{m}$ . Suppose the sequence ${(x_{i})}_{i = 1}^{n}$ is strictly increasing and the sub-sequences ${(x_{i})}_{i = 1}^{m}$ and ${(x_{i})}_{i = m}^{n}$ are sequentially convex and concave, respectively. Then the points P₁,…, P_n form a convex polygon.

Proof

We construct the function f as in (6). Then, by using Lemma 2.1, Proposition 3.1, Proposition 3.2, Theorem 3.3 and Theorem 3.4, we conclude (7). Analogously to Theorem 2.2, it leads us to the establishment that the function f is convex. Finally, from the epi(f), we can get the desired result.

Of course, as mentioned in the remark after Theorem 2.2, one can discuss relaxing strict monotonic property of the sequence ${(x_{i})}_{i = 1}^{n}$ in its extreme points to simply increasingness.

This investigation also raises several interesting new problems and challenges. For instance, one obvious task is generalizing this concept to any finite dimension. It leads us to the question, in higher dimensions, what coordinate-oriented inequalities need to be satisfied by the scattered points in order to obtain a convex polytope?

Another area of discussion is the possible outcome in ℝ², if the coordinates of the points imply higher order sequential convexity/concavity properties. Are we still able to extract an underlying convex polygon out of it or a complex interesting geometric figure?

Acknowledgement

We would like to extend our gratitude to the anonymous referee for his/her valuable time, insightful comments, and constructive feedback.

Convex Sequence and Convex Polygon

Full Article

1. Introduction

2. Main results

Lemma 2.1

(1)

Proof

(2)

(3)

Theorem 2.2

(4)

(5)

Proof

(6)

(7)

(8)

Remark

Theorem 2.3

3. The subsequent results

Proposition 3.1

(9)

Proof

Proposition 3.2

Theorem 3.3

Proof

Theorem 3.4

Proposition 3.5

(10)

Proof

Theorem 3.6

Proof

Acknowledgement

Paradigm

My account