Some properties of constant width shapes in the plane

March 17, 2023 Leave a comment

Shapes of constant width in the plane have the property that they are convex and any pair of parallel tangent or supporting lines are at a fixed constant width apart. The circle is the most obvious example of shapes having constant width. However, many more such shapes exist.

Feynman recalls in his book What Do You Care What Other People Think? that the Challenger disaster might be caused by the fact that the section of the booster rockets may not have been perfectly circular. Check out this link for more details. The procedure to check for roundness was to measure the diameter of the cylinder at different angles around the tank. As you may imagine, if the tank’s section has non-circular constant width, this technique does not detect anything wrong.

The most famous examples of constant width shapes are the Reuleaux triangle and more generally, Reuleaux polygons in general. These shapes are not just mathematical curiosities, but have various applications. Reuleaux triangles are used in the rotary Wankel engine design and square drilling machines, while the twenty pence British coin is a Reuleaux heptagon.

Read more…

Applications of Helly’s theorem

March 12, 2023 Leave a comment
  1. Prove that if the plane can be covered with n \geq 3 half planes then there exist three of these which also cover the plane.
  2. On a circle consider a finite set of arcs which do not cover the circle, such that any two of them have non-void intersection. Show that all arcs have a common points. If the arcs cover the circle does the conclusion still hold?
  3. Consider n \geq 3 half circles which cover the whole circle. Show that we can pick three of them which still cover the circle.

I’ll not provide the solutions for now. The title should be a strong indication towards finding a solution!

Helly’s Theorem

March 10, 2023 Leave a comment

Helly’s theorem. Let {n\geq 4} convex figures be given in the plane and suppose each three of them have a common point. Prove that all {n} figures have a common point.

Can the convexity hypothesis be removed? 

Read more…

Computing Restricted Voronoi Cells with Geogram

January 24, 2023 Leave a comment

Given a shape D and a family of N points in D, the Voronoi diagram associated to this set of points consists in a partition of D such that each cell contains points closest to the current point than to any other point. Efficient algorithms exist for computing Voronoi diagrams, however in common implementations, the Voronoi cells are not clipped to a bounded region. Indeed, cells corresponding to a “boundary” point among the points considered will be infinite, in this case. Clipping to a bounded region is not difficult, but might require some careful coding.

The software Geogram (https://github.com/BrunoLevy/geogram) has a routine for building the clipped Voronoi diagrams. It gets as inputs the Voronoi points and a triangulation of the bounding box D. The reason behind this choice is probably motivated by the existence of efficient clipping algorithm for intersections between polygons and a triangle. Below I show how Geogram can be called from Matlab in a basic situation where D is a square. I tested this on a linux system. Keep in mind that Geogram needs to be installed on the machine prior to launching this code.

The code is tested and works very well for thousands of Voronoi cells. The computation in Geogram is really fast. Most of the time is the post-processing in Matlab and the input-output stage.

Read more…

Construct inellipse from tangency points

January 23, 2023 Leave a comment

In this post I describe the steps for constructing an inellipse \mathcal E starting from the tangency points {\mathbf m \in \mathbf b \mathbf c, \mathbf n \mathbf \in \mathbf a \mathbf c, \mathbf p \in \mathbf a \mathbf b}. It is classical that a necessary and sufficient condition for {\mathcal E} to exist is that {\mathbf a \mathbf m, \mathbf b \mathbf n, \mathbf c\mathbf p} are concurrent. The construction is inspired from T. H. Eagles, Constructive geometry of plane curves, with numerous examples, Macmillan and Co, 1885.

Let {\mathbf q} be the midpoint of {\mathbf m\mathbf p} and {\mathbf r} be the midpoint of {\mathbf m\mathbf n}. Then the center of the inellipse is {\mathbf o \in \mathbf b\mathbf q\cap \mathbf c \mathbf r}.

Construct {\mathbf m'} the symmetric of {\mathbf m} through {\mathbf o}. Thus {\mathbf m \mathbf m'} is a diameter of {\mathcal E}.

Draw the line {d} through {\mathbf o} parallel to {\mathbf b \mathbf c}. Define {\mathbf s \in d\cap \mathbf a \mathbf c} and let {\mathbf s'} be the intersection of {d} with the parallel to {\mathbf m \mathbf m'} through {\mathbf n}. Construct {\mathbf d \in d} such that {\mathbf o \mathbf d^2 = \mathbf o\mathbf s\cdot \mathbf o \mathbf s'}. Then {\mathbf d\in \mathcal E}. Construct {\mathbf d'}, the symmetric of {\mathbf d} through {\mathbf o}. In this way we constructed another diameter {\mathbf d \mathbf d'} conjugate to {\mathbf m\mathbf m'}.

Construct the segment {\mathbf e\mathbf e'}, orthogonal to {\mathbf d\mathbf d'}, having midpoint at {\mathbf m'} such that {\mathbf e\mathbf e' = \mathbf d\mathbf d'}. The angle bisector of {\angle \mathbf e \mathbf o \mathbf e'} is the principal axis of {\mathcal E}.

The lengths of the axes of the ellipse are given by {\mathbf o \mathbf e+\mathbf o\mathbf e'} and {|\mathbf o\mathbf e-\mathbf o\mathbf e'|}.

The construction is shown in the following image.

Categories: Uncategorized

Inscribed squares: Symmetric case

January 19, 2023 Leave a comment

I recently heard about the “inscribed square” problem which states that on any closed, continuous curve without self intersections there should exist four points which are the vertices of a (non-degenerate) square. This problem, first raised by Otto Toeplitz in 1911, is still unsolved today. Many particular cases are solved (convex curves, smooth curves, etc.). Nevertheless, things quickly get complicated as one gets close to the original problems where only continuity is assumed.

I will show below a quick argument for a very particular case. Suppose the curve C is symmetric with respect to the origin. Since the curve is simple, the origin does not lie on the curve. Consider the curve C', rotated with 90 degrees around the origin. Then curves C,\ C' must intersect. Indeed, by continuity, there exists a point A which is closest to the origin on the curve C and a point B furthest away from the origin on the same curve. The rotated curve has the same minimal and maximal distances to the origin. Therefore, point A lies in the interior of C' (or on the boundary) and point B lies outside of C' (or on the boundary). In either case, going from A to B on C we must intersect the curve C'.

If X is a point of intersection, it lies both on C and on its rotation with 90 degrees. Moreover, the symmetric points also lie on C by symmetry. Therefore, we have four points at equal distance from the origin, for which the rays from the origin form equal angles. These points are the vertices of a square!

Build three particular equal segments in a triangle

December 18, 2022 3 comments

I recently stumbled upon the following problem:

Consider a triangle ABC. Construct points P,Q on AB, AC, respectively such that BP=PQ=QC.

I was not able to solve this myself, so a quick search on Google using “BP=PQ=QC” yielded the following article where the solution to the problem above is presented.

Read more…

Geometry problem: a property of the 40-40-100 triangle

December 5, 2022 1 comment

Consider the triangle {ABC} with {\angle A = 100^\circ} and {\angle B = \angle C = 40^\circ}. Consider {D \in AC} such that {\angle CBD = 10^\circ}. Prove that {AD = BC}.

This is a surprising result and easy to remember. I first saw this back in the days I was solving olympiad problems. The 40-40-100 triangle has this nice characteristic property. There is a very nice geometric proof and a one liner trigonometry argument. 

Read more…

Geometry problem: a property of the 30-70-80 triangle

December 4, 2022 Leave a comment

Consider a triangle {XYZ} with angles {\angle X = 70^\circ}, {\angle Y = 30^\circ}, {\angle Z = 80^\circ}. Let {ZT} be the bisector of the angle {\angle XZY}. Consider {U \in XZ} such that {UT || YZ}. Prove that the triangle {YUZ} is isosceles. 

Read more…

Minimal volume of some particular convex sets in the cube

November 21, 2022 Leave a comment

Consider a cube and a convex body K contained in it such that the projections of this body on every face of the cube completely covers that face. Prove that the volume of the convex body is at least equal with a third of the volume of the cube.

Read more…

Graham’s Biggest Little Hexagon

October 14, 2022 Leave a comment

Think of the following problem: What is the largest area of a Hexagon with diameter equal to 1?

As is the case with many questions similar to the one above, called polygonal isoperimetric problems, the first guess is the regular hexagon. For example, the largest area of a Hexagon with fixed perimeter is obtained for the regular hexagon. However, for the initial question, the regular hexagon is not the best one. Graham proved in his paper “The largest small hexagon” that there exists a better competitor and he showed precisely which hexagon is optimal. More details on the history of the problem and more references can be found in Graham’s paper, the Wikipedia page or the Mathworld page.

I recently wanted to use this hexagon in some computations and I was surprised I could not find explicitly the coordinates of such a hexagon. The paper “Isodiametric Problems for Polygons” by Mossinghoff was as close as possible to what I was looking for, although the construction is not explicit. Therefore, below I present a strategy to find what is the optimal hexagon and I will give a precise (although approximate) variant for the coordinates of Graham’s hexagon.

Read more…

Benford’s law

October 11, 2022 Leave a comment

I learned about this while reading the first chapter of the book Le théorème du parapluie – Ou l’art d’observer le monde dans le bon sens by Mickaël Launay. Apparently, the first digits of random numbers appearing in everyday life are not distributed evenly. At least not in the way you would expect!

If you are curios, perform the following experiment. Go in a supermarket with a notebook with columns marked from 1 to 9. Pick random products and mark a line on the column corresponding to the first digit of the price. You will be surprised to know that the digits 1 and 2 occur more often than larger ones. This phenomenon is not limited to prices and is called Benford’s law. The explanation behind this phenomenon is that the numbers appearing in real life are not uniformly distributed in the usual way, but they are uniformly distributed in a multiplicative way. Therefore, there should be as many numbers between 1 and 2 as between 2 and 4 or 4 and 8. This is quite unintuitive at first sight. Consult the link above for further references and mathematical justifications.

In the meantime, let’s put this to the test by looking at first digits of the populations of world countries. We are going to do this in an automated way using the data from worldometers.info and a script inspired from here.

Read more…

Matrices with entries of the form f(i,j) in Matlab

October 7, 2022 Leave a comment

It is often necessary to define a matrix with entries A_{ij} = f(i,j) where i,j are line and column indices. Using loops is possible, but is not the most elegant solution. Also, it may not be the fastest. Here is a way to construct such matrices fast and easy: simply use meshgrid to construct the arrays of indices i, j. Take a look at the example below and construct your own:

N = 10;
[I,J] = meshgrid(1:N,1:N);
A = N+1-max(I,J);

Categories: Algebra, matlab Tags: , ,

Integrating polynomials on polygons

September 13, 2022 Leave a comment

Given the coordinates {(x_i,y_i)_{i=1}^n} of a polygon {P}, compute the following quantities:

\displaystyle \text{Area(P)}, \int_P x\ dxdy, \int_P y\ dxdy, \int_P x^2\ dxdy, \int_Py^2\ dxdy.

Therefore, the area and the centroid of {P} can be computed analytically in terms of the coordinates. More generally, integrals of all polynomials in the coordinates can be evaluated. To convince yourself that this is possible, recall Green’s formula. If {L,M} are functions of {x} and {y}, {D} is a two dimensional domain and {C} is its boundary, then

\displaystyle \oint_C (Ldx+Mdy) = \iint_D \left(\frac{\partial M}{\partial x}-\frac{\partial L}{\partial y}\right)dxdy. \ \ \ \ \ (1)

In the following I will omit the double integral, for simplicity and write simply {\int_D}. The path integration along {C} is anticlockwise. To compute an integral of the form {\oint C L dx} consider a parametrization {\gamma : [a,b] \rightarrow C, \gamma(t)=(x(t),y(t))} and use the formula

\displaystyle \oint_C L(x,y) dx = \int_a^b L(x(t),y(t)) x'(t).

The analogue formula holds for the {dy} variant. Let us now turn to the case of polygons. Consider {P=A_0...A_{n-1}} a polygon, the indices of the vertices being considered modulo {n} whenever necessary. Observe that in order to compute the area of {P}, it is enough to consider {M(x,y)=x} and {L\equiv 0} in (1). The coordinates of {A_i} are denoted {(x_i,y_i)}, {i=0,...,n-1}. We parametrize the segment {[A_iA_{i+1}]} using {t \mapsto (1-t)(x_i,y_i)+t(x_{i+1},y_{i+1})}. Thus we are ready to compute:

\displaystyle |P| = \oint_{\partial C} x dy = \sum_{i=0}^{n-1} \int_0^1 (x_i+t(x_{i+1}-x_i))dt (y_{i+1}-y_i).

Computing the integral and regrouping the terms we obtain the familiar formula

\displaystyle |P| = \frac{1}{2}\sum_{i=0}^{n-1} (x_iy_{i+1}-x_{i+1}y_i).

We have the following analogue computations:

  • To compute {\int_P x\ dxdy} use {M = x^2/2, L\equiv 0}. We obtain
    \displaystyle \int_P x\ dx dy = \frac{1}{6} \sum_{i=0}^{n-1}(x_i+x_{i+1})(x_iy_{i+1}-x_{i+1}y_i).
  • To compute {\int_P y\ dxdy} use {M = xy, L\equiv 0}. We obtain
    \displaystyle \int_P y\ dx dy = \frac{1}{6} \sum_{i=0}^{n-1}(y_i+y_{i+1})(x_iy_{i+1}-x_{i+1}y_i).
  • To compute {\int_P x^2\ dxdy} use {M = x^3/3, L\equiv 0}. We obtain
    \displaystyle \int_P x^2\ dx dy = \frac{1}{6} \sum_{i=0}^{n-1}(x_i^2+x_ix_{i+1}+x_{i+1}^2)(x_iy_{i+1}-x_{i+1}y_i).
  • To compute {\int_P y^2\ dxdy} use {M = xy^2, L\equiv 0}. We obtain
    \displaystyle \int_P y^2\ dx dy = \frac{1}{6} \sum_{i=0}^{n-1}(y_i^2+y_iy_{i+1}+y_{i+1}^2)(x_iy_{i+1}-x_{i+1}y_i).

I guess, up to this point you can convince yourself that the general case {\int_P x^py^q} is just a matter of choosing the right functions in formula (1) and performing the one dimensional integrations.

IMO 2022 – Problem 4 – Geometry

September 6, 2022 Leave a comment

Problem 4. Let {ABCDE} be a convex pentagon such that {BC = DE}. Assume that there is a point {T} inside {ABCDE} with {TB = TD}, {TC = TE} and {\angle ABT = \angle TEA}. Let line {AB} intersect lines {CD} and {CT} at points {P} and {Q}, respectively. Assume that the points {P, B, A, Q} occur on their line in that order. Let line {AE} intersect lines {CD} and {DT} at points {R} and {S}, respectively. Assume that the points {R, E, A, S} occur on their line in that order. Prove that the points {P, S, Q, R} lie on a circle. 

Read more…

IMO 2022 – Problem 2 – Non-standard functional equation

September 6, 2022 2 comments

Problem 2. Let {\Bbb R^+} denote the set of positive real numbers. Find all functions {f : \Bbb{R}^+ \rightarrow \Bbb{R}^+} such that for each {x \in \Bbb R^+}, there is exactly one {y \in \Bbb R^+} satisfying {xf(y) + yf(x) \leq 2}

Read more…

IMC 2022 – Day 1 – Problem 2

August 8, 2022 Leave a comment

Problem 2. Let {n} be a positive integer. Find all {n \times n} real matrices {A} having only real eigenvalues satisfying

\displaystyle A+A^k = A^T

for some integer {k \geq n}

Read more…

IMC 2022 – Day 1 – Problem 1

August 8, 2022 Leave a comment

Problem 1. Let {f:[0,1]\rightarrow (0,\infty)} be an integrable function such that {f(x)\cdot f(1-x) = 1} for all {x\in [0,1]}. Prove that

\displaystyle \int_0^1 f(x) dx \geq 1.

Solution: If you want just a hint, here it is: Cauchy-Schwarz. For a full solution read below.

Read more…

Function with zero average on vertices of all regular polygons

July 4, 2022 Leave a comment

Fix a positive integer {n \geq 3}. Let {f:\Bbb{R}^2 \rightarrow \Bbb{R}} be a function such that for any regular {n}-gon {A_1...A_n} we have

\displaystyle f(A_1)+...+f(A_n) = 0.

Prove that {f} is identically equal to zero. 

Source: Romanian Team Selection Test 1996, see also the Putnam Contest Problems from 2009.

Solution: The solution comes by looking at some examples:

1. Consider an equilateral triangle {A_1A_2A_3}. It is possible to produce another two equilateral triangles {A_1B_2B_3} and {A_1C_2C_3} such that {A_2B_2C_2}, {A_3B_3C_3} are equilateral. Note that we kept a common vertex and we rotated the initial triangle by {2\pi/3} and {4\pi/3}. Applying the result for all the small triangles and summing we obtain

\displaystyle 3f(A_1)+... = 0

where the missing terms are again sums of values of {f} on some equilateral triangles. It follows that {f(A_1)=0}.

2. For a square things are even simpler, since considering rotations of a square around one vertex one ends up with a configuration containing a square, its midpoints and its center. A similar reasoning shows that the value of the function {f} at the center needs to be equal to zero, summing the values of the function {f} on the vertices of all small squares.

In the general case, the idea is the same. Consider an initial polygon {A_1...A_n} and rotate it around {A_1} with angles {2k\pi/n}, {1\leq k \leq n-1}. Then sum all the values of the function on the vertices of these regular polygons. Observe that the vertex {A_1} is repeated {n} times while all other vertices are part of some regular polygon. In the end we get

\displaystyle n f(A_1)+0 = 0

where the zeroes correspond to sums over vertices of regular polygons.

The same type of reasoning should hold when the sum over vertices of regular polygons is replaced by an integral on a circle. The proof would follow the same lines. Fix a point {A}, then integrate {f} on all rotations of the circle {C} through {A}. On one side this integral should be equal to zero. On the other it contains the value of {f} in {A} and values on concentric circles in {A}. This should imply that {f(A)} is zero for any point {A}.

Hadwiger-Finsler inequality – translation of the original paper

June 9, 2022 2 comments

The Hadwiger-Finsler inequality states that if a,b,c are the side lengths of a triangle and S is its area then we have

a^2+b^2+c^2 \geq (a-b)^2+(b-c)^2+(c-a)^2 + 4\sqrt{3}S.

I recently decided to take a look at the original paper: Finsler, PaulHadwiger, Hugo (1937). “Einige Relationen im Dreieck”. Commentarii Mathematici Helvetici10 (1): 316–326. doi:10.1007/BF01214300

This motivated me to try and translate it. Below you can find the document translated into English. Since do not speak German, do not hesitate to suggest corrections and improvements!

%d bloggers like this: