Covering the edges of a complete geometric graph with convex polygons

Seminar
Speaker
Oren Yerushalmi (Technion)
Date
15/05/2022 - 15:30 - 14:00Add to Calendar 2022-05-15 14:00:00 2022-05-15 15:30:00 Covering the edges of a complete geometric graph with convex polygons Given a set $P$ of $m \geq 3$ points in general position in the plane, we want to find the smallest possible number of convex polygons with vertices in $P$ such that the edges of all these polygons contain all the ${m \choose 2}$ straight line segments determined by the points of $P$.  We show that if $m$ is odd, the answer is $\frac{m^2-1}{8}$ regardless of the choice of $P$. The answer in the case where $m$ is even depends on the choice of $P$ and not only on $m$. Nearly tight lower and upper bounds follow in the case where $m$ is even.    Based on joint work with Rom Pinchasi. Room 216/201 and also Zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 216/201 and also Zoom
Abstract

Given a set $P$ of $m \geq 3$ points in general position in the plane, we want to find the smallest possible number of convex polygons with vertices in $P$ such that the edges of all these polygons contain all the ${m \choose 2}$ straight line segments determined by the points of $P$. 

We show that if $m$ is odd, the answer is $\frac{m^2-1}{8}$ regardless of the choice of $P$. The answer in the case where $m$ is even depends on the choice of $P$ and not only on $m$. Nearly tight lower and upper bounds follow in the case where $m$ is even.   

Based on joint work with Rom Pinchasi.

Last Updated Date : 10/05/2022