3:30 PM, Seminar Hall
First Selection Lemma for Various Geometric Objects
Pradeesha Ashok
The Department of Computer Science and Automation, IISc.
12-02-14

---

Abstract

Selection lemmas are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delaunay triangulations. Selection lemma type results typically show that there exists a point that is contained in many objects that are induced (spanned) by an underlying point set. In the first selection lemma, we consider the set of all the objects induced (spanned) by a point set $P$. This question has been widely explored for simplices in $\mathbb{R}^d$, with tight bounds in $\mathbb{R}^2$. In this talk, we prove first selection lemma for other classes of geometric objects. We also consider the strong variant of this problem where we add the constraint that the piercing point comes from $P$. We discuss these problems for objects like axis-parallel rectangles, disks etc.