Down in the depths ‘on’ Carathéodory’s theorem

By David Orden May 7, 2018 3 comments Print

Research in general, and mathematical one in particular, sometimes reminds to the lyrics that Cole Porter wrote for the Down in the depths song:

And here am I

Facing tomorrow

Alone with my sorrow

Down in the depths on the ninetieth floor.

Carathéodory's theorem — Credit: Alex Lau’s flickr

Nevertheless, sometimes you manage to get down in the depths and achieve a nice and/or remarkable result. The paper consider here achieves both, by extending a classical theorem in a clever and interesting way.

First things first, convex geometry is a branch of mathematics which, despite dating back from ancient times, has boosted particularly in the last century. Its main object of study are those sets being closed under convex combinations, called convex sets. In the more familiar setting of a d-dimensional Euclidean space (like the 2D-plane or the 3D-space), convex sets are then those for which the straight segment joining any two points is entirely contained in the set. The following figure shows examples of convex (left) and non-convex (right) sets.

Focusing on discrete convex geometry, an outstanding notion is that of the convex hull, or convex envelope, of a given set of points in the d-dimensional space $\mathbb{R}^d$ . This is the smallest convex set containing the points, and its computation is, for example, a central problem in computational geometry. Informally, for the 2D case we can see the convex hull as the result obtained if we surround the point set with an expanded rubber band, and then release it allowing its contraction.

This simple notion of convex hull is the main ingredient for one of the outstanding classical theorems in convex geometry, proved by Carathéodory ¹ in 1907, which states that

For any finite set $P$ of points in $\mathbb{R}^d$ , given any point $q$ contained in the convex hull of $P$ , there exist $d+1$ points $p_1,\ldots,p_{d+1}$ in $P$ such that $q$ is contained in their convex hull $\operatorname{conv}(\{ p_1,\ldots,p_{d+1}\})$ .

For the two-dimensional case, with $d=2$ , this means that given any point $q$ “inside” an arbitrary set of points $P$ , there are 3 points $p_1,p_2,p_3$ that contain $q$ inside the triangle they define. (Note that general position, i.e., no three points aligned, should be assumed for the triangle to be proper.) The result might seem trivial for this 2D case but be aware that geometry in higher dimensions is not so apparent and many counterintuitive situations arise.

Back to intuitions, have a look at the left and right configurations in the following figure: Which of the two possibilities for $q$ (red point) do you think is contained in the larger number of triangles spanned by points in $P$ (black)?

You probably have guessed that the configuration on the left should have more triangles containing $q$ than the configuration on the right: In the one on the left, choosing one point in each of the three blades of the windmill gives rise to a triangle containing $q$ , that is, there are $4\cdot 4\cdot 4 = 64$ such triangles. However, in the one on the right, since the point $q$ is just an epsilon over the lower edge of the triangular envelope, that edge is forced to be part of any triangle containing $q$ , and actually the only possibilities are the $10$ triangles using that edge plus an additional point.

In view of the previous example, it seems that the deeper is $q$ inside $P$ , the larger number of triangles can be chosen containing $q$ . Formalizing this intuition is the main result in a recent paper by Fabila-Monroy and Huemer ² who, 110 years later than the original paper by Carathéodory, have succeeded to prove the following result:

For any finite set $P$ of points in $\mathbb{R}^d$ , given any point $q$ of positive depth $d_q$ with respect to $P$ , there is a constant $c$ depending on $d_q$ and there exist $d+1$ pairwise disjoint subsets $P_1,\ldots,P_{d+1}$ of $P$ , each of them with cardinality at least $c\cdot |P|$ , such that, for every choice of a point $p_i$ in each of the subsets $P_i$ , the point $q$ is contained in the convex hull $\operatorname{conv}(\{ p_1,\ldots,p_{d+1}\})$ of the chosen points.

Informally, this statement says that the deeper is $q$ inside $P$ , the larger subsets $P_1,\ldots,P_{d+1}$ exist such that choosing one point in each of them gives an envelope containing $q$ . In this sense, the original and classical Carathéodory’s theorem states the existence of sets $P_i$ with cardinality one, while this recent result goes further by ensuring certain cardinality which depends on the depth. In the left configuration of the example above, we have already seen three subsets of cardinality 4 as in the statement, namely the three blades of the windmill.

There are actually many possibilities to define how deep is a point $q$ inside the envelope of a point set $P$ . The notion of depth considered by Fabila-Monroy and Huemer is the so-called Tukey depth, defined as the minimum number of points from $P$ in a halfplane containing $q$ . In the example above, the depth of $q$ is 4 for the left configuration and 2 for the right configuration.

As their key ingredient, Ruy-Fabila and Huemer introduce the notion of projection Tukey depth of a point $q$ with respect to a set $P$ and a hyperplane $\Pi$ . Informally, a large projection Tukey depth means that there exists a direction $\ell$ in which $q$ can be projected onto hyperplanes $\Pi^{+}$ and $\Pi^{-}$ , parallel to $\Pi$ on opposite sides, such that in the resulting configurations the point $q$ has large Tukey depth with respect to the projections of $P$ .

Credit: Fabila-Monroy, R. & Huemer, C. (2017)

Defining the projection Tukey depth of a point $q$ with respect to a set $P$ as the minimum over all the possible hyperplanes $\Pi$ , the authors prove a projection-depth version of the well-known centerpoint theorem (related to the geometric analogous of the median):

Given any finite set $P$ of points in $\mathbb{R}^d$ , there exists a point $q$ , not necessarily in $P$ , whose projection Tukey depth with respect to $P$ is at least $\frac{1}{d+1}$ .

Last, but not least, the authors also prove depth versions of two other classical theorems, namely Helly’s ³ and Kirchberger’s ⁴. As a summary, this work allows to revisit several classical and important theorems, providing at the same time a new and enriched perspective which enhances their deepness.

Note: This text is part of the dissemination activities of the Marie Skłodowska-Curie grant No 734922 in the European Union’s Horizon 2020 research and innovation programme.

References

Carathéodory, C. (1907). Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen. Mathematische Annalen, 64(1), 95-115. doi:10.1007/BF01449883 ↩
Fabila-Monroy, R. & Huemer, C. (2017). Discrete and Computational Geometry, 58(1): 51-66. doi: 10.1007/s00454-017-9893-8 ↩
Danzer, L., Grünbaum, B., and Klee, V. (1963). Helly’s theorem and its relatives. AMS ↩
Kirchberger, P. (1903). Über Tchebychefsche Annäherungsmethoden. Mathematische Annalen, 57(4), 509-540. doi: 10.1007/BF01445182 ↩

3 comments

Ezjakintasunaren kartografia #215 – Zientzia Kaiera

May 12, 2018

[…] Emaitza interesgarriak ditu geometria konputazionaleko klasiko baten hedapenak. David Ordenen Down in the depths ‘on’ Carathéodory’s theorem […]
Cartografiando la ignorancia #222 | Enlace Recomendado | Naukas

May 12, 2018

[…] La extensión de un problema clásico de la geometría computacional da lugar a resultados muy interesantes. David Orden en Down in the depths ‘on’ Carathéodory’s theorem […]
Carnival of Mathematics 158 | The Aperiodical

June 10, 2018

[…] somewhat more mindbending maths, David Orden explains some new results relating to Carathéodory’s theorem, to do with the properties of a point chosen inside the convex hull of a set of other points, […]

References

3 comments

Leave a ReplyCancel reply

Leave a Reply