2015/12/23 by Alexandre Rok, Rok, Alexandre, Shakhar Smorodinsky +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #Optimization and Search Problems #cs.DM
paper · pdf · doi:10.48550/arxiv.1512.07505
arxiv created 2015/12/23 · openalex publication_date 2015/12/23 · arxiv updated 2015/12/24 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
(i) We provide a short and simple proof of the first selection lemma. (ii) We also prove a selection lemma of a new type in \Red. For example, when d=2 assuming n is large enough we prove that for any set P of n points in general position there are Ω(n4) pairs of segments spanned by P all of which intersect in some fixed triangle spanned by P. (iii) Finally, we extend the weak (1)/(r)-net theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog N of a weak (1)/(r)-net of cardinality O(r(d(d+1))/(2)logdr) whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of N has one polynomial coordinate.