2011/05/16 by Ben D. Lund, Ben Lund, George Purdy +7
Computer Science · Engineering · Mathematics · #68R99 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Point processes and geometric inequalities #acm:68R99 #cs.CG #math.CO #msc:68R99
paper · pdf · doi:10.48550/arxiv.1105.3078
Submitted to CCCG11
arxiv created 2011/05/16 · openalex publication_date 2011/05/16 · arxiv updated 2011/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let P be a set of n points in the plane, each point moving along a given trajectory. A \em k-collinearity is a pair (L,t) of a line L and a time t such that L contains at least k points at time t, the points along L do not all coincide, and not all of them are collinear at all times. We show that, if the points move with constant velocity, then the number of 3-collinearities is at most 2\binomn3, and this bound is tight. There are n points having Ω(n3/k4 + n2/k2) distinct k-collinearities. Thus, the number of k-collinearities among n points, for constant k, is O(n3), and this bound is asymptotically tight. In addition, there are n points, moving in pairwise distinct directions with different speeds, such that no three points are ever collinear.