Tag Archives: convex

Dec2

Confusing terms in topology

Posted on by
Standard

Following are some of the terms used in topology which have similar definition or literal English meanings:

  • Convex set: A subset U of \mathbb{R}^n is called convex1 , if it contains, along with any pair of its points x,y, also the entire line segement joining the points.
  • Star-convex set: A subset U of \mathbb{R}^n is called star-convex if there exists a point p\in U such that for each x\in U, the line segment joining x to p lies in U.
  • Simply connected: A topological space X is called simply connected if it is path-connected2  and any loop in X defined by f : S^1 \to X can be contracted3  to a point.
  • Deformation retract: Let U be a subspace of X. We say  is a X deformation retracts to U if there exists a retraction4 r : X \to U a retraction such that its composition with the inclusion is homotopic5  to the identity map on X.
convex

Various examples to illustrate the interdependence of these terms. Shown here are pentagon, star, sphere, and annulus.

A stronger version of Jordan Curve Theorem, known as Jordan–Schoenflies theorem, implies that the interior of a simple polygon is always a simply-connected subset of the Euclidean plane. This statement becomes false in higher dimensions.

The n-dimensional sphere S^n is simply connected if and only if n \geq 2. Every star-convex subset of \mathbb{R}^n is simply connected. A torus, the (elliptic) cylinder, the Möbius strip, the projective plane and the Klein bottle are NOT simply connected.

The boundary of the n-dimensional ball S^n, that is, the (n-1)-sphere, is not a retract of the ball. Using this we can prove the Brouwer fixed-point theorem. However, \mathbb{R}^n-0 deformation retracts to a sphere S^{n-1}. Hence, though the sphere shown above doesn’t deformation retract to a point, it is a deformation retraction of \mathbb{R}^3-0.

Footnotes

  1. In general, a convex set is defined for vector spaces. It’s the set of elements from the vector space such that all the points on the straight line line between any two points of the set are also contained in the set. If a and b are points in the vector space, the points on the straight line between a and b are given by x = \lambda a + (1-\lambda)b for all \lambda from 0 to 1.
  2. A path from a point x to a point y in a topological space X is a continuous function f from the unit interval [0,1] to X with f(0) = x and f(1) = y. The space X is said to be path-connected if there is a path joining any two points in X.
  3. There exists a continuous map F : D^2 \to X such that F restricted to S^1 is f. Here, S^1 and D^2 denotes the unit circle and closed unit disk in the Euclidean plane respectively. In general, a space X is contractible if it has the homotopy-type of a point. Intuitively, two spaces X and Y are homotopy equivalent if they can be transformed into one another by bending, shrinking and expanding operations.
  4. Then a continuous map r: X\to U is a retraction if the restriction of r to U is the identity map on U.
  5. A homotopy between two continuous functions f and g from a topological space X to a topological space Y is defined to be a continuous function H : X \times [0,1] \to Y such that, if x \in X then H(x,0) = f(x) and H(x,1) = g(x). Deformation retraction is a special type of homotopy equivalence, i.e. a deformation retraction is a mapping which captures the idea of continuously shrinking a space into a subspace.
Apr5

Midpoint Polygon Conjecture is false

Posted on by
Standard

Contrary to my expectations, my previous post turned out to be like  Popular-­Lonely primes and Decimal Problem, i.e. I discovered nothing new.

My conjecture is false. Following counterexample is given on pp. 234 of this paper:

poly-counter

Counterexample of the conjecture, taken from: Berlekamp, E. R., E. N. Gilbert, and F. W. Sinden. “A Polygon Problem.” The American Mathematical Monthly 72, no. 3 (1965): 233-41. doi:10.2307/2313689.

As pointed out by uncombed_coconut, the correct theorem is:

Theorem (Berlekamp-Gilbert-Sinden, 1965). For almost all simple polygons there exist a smallest natural number k such that after k iterations of midpoint polygon procedure, we obtain a convex polygon.

The proof of this theorem is very interesting. Till now I thought that proving euclidean geometry theorems using complex numbers was an overkill. But using an N-tuple of complex numbers to represent the vertices of a closed polygon (in given order),  \mathbf{z} = (z_1,\ldots , z_N),  we can restate the problem in terms of eigenvectors (referred to as eigenpolygons) and eigenvalues.  Following are the crucial facts used is the proof:

  • An arbitrary N-gon (need not be simple) can be written as a sum of regular N-gons i.e. the eigenvalues are distinct.
  • The coefficient of k^{th} eigenvector (when N-gon is written as linear combination of eigenpolygons) is the centroid of the polygon obtained by “winding” \mathbf{z} k times.
  • All vertices of the midpoint polygons (obtained by repeating the midpoint polygon procedure infinitely many times) converge to the centroid.
  • The sum of two convex components of \mathbf{z} is a polygon. This polygon is the affine image of a regular convex N-gon whose all vertices lie on an ellipse. (as pointed out by Nikhil)
  • A necessary and sufficient condition for \mathbf{z} to have a convex midpoint polygon (after some finite iterations of the midpoint polygon procedure) is that the ellipse circumscribing the sum of two convex components of \mathbf{z} is nondegenerate. (The degenerate form of an ellipse is a point. )

For a nice outline of the proof, please refer to the comment by uncombed_coconut on previous post.

Since I didn’t know that this is a well studied problem (and that too by a well known mathematician!) I was trying to prove it on my own. Though I didn’t make much progress, but I discovered some interesting theorems which I will share in my future posts.

Apr2

Midpoint Polygon Conjecture

Posted on by
Standard

This is going to be yet another ambitious post like New Diagonal Contribution Theorem, and Cross Diagonal Cover Problem.

Let’s begin with following definitions from Wikipedia:

A convex polygon is a simple polygon (not self-intersecting) in which no line segment between two points on the boundary ever goes outside the polygon.

A concave polygon is a simple polygon (not self-intersecting) which has at least one reflex interior angle – that is, an angle with a measure that is between 180 degrees and 360 degrees exclusive.

We know that 3 sided polygons (a.k.a triangles) are always convex.  So, they are not very interesting. Let’s define the following procedure:

Midpoint Polygon Procedure: Given a n-sided simple polygon, join the consecutive midpoints of the sides to generate another n-sided simple polygon.

Here are few examples:

concave-convex

Red polygon is the original polygon, green polygon is the one generated by joining midpoints.

We observe that if the original polygon was a concave polygon then the polygon generated by joining midpoints need not be a convex polygon. So, let’s try to observe what happens when we apply the midpoint polygon procedure iteratively on the 4th case above (i.e. when we didn’t get a convex polygon):

big-gon

In fourth iteration of the described procedure, we get the convex polygon.

Based on this observation, I want to make following conjecture:

Midpoint Polygon Conjecture: For every simple polygon there exists a smallest natural number k such that after k iterations of midpoint polygon procedure, we obtain a convex polygon.

If the given polygon is convex, then there is nothing to prove since k=1, but I have no idea about how to prove it for concave polygons. I tried to Google for the answer, but couldn’t find anything similar. So, if you know the proof or counterexample of this conjecture, please let me know.