Collinearities in Kinetic Point Sets

الأصل · EN

Let P be a set of n points in the plane, each point moving along a given trajectory. A 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 2n3, and this bound is tight. There are n points having Ω(n³/k⁴ + n²/k²) distinct k-collinearities. Thus, the number of k-collinearities among n points, for constant k, is O(n³), 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.