On Weighted Sums of Numbers of Convex Polygons in Point Sets

Clemens Huemer, Deborah Oliveros, Pablo Pérez-Lantero, Ferran Torra, Birgit Vogtenhuber*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Let S be a set of n points in general position in the plane, and let Xk,ℓ(S) be the number of convex k-gons with vertices in S that have exactly ℓ points of S in their interior. We prove several equalities for the numbers Xk,ℓ(S). This problem is related to the Erdős–Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well.
Original languageEnglish
Pages (from-to)448-476
Number of pages29
JournalDiscrete & Computational Geometry
Issue number2
Publication statusPublished - 2022

Cite this