Collinearities in Kinetic Point Sets

Details Collinearities in Kinetic Point Sets Collinearities in Kinetic Point Sets

2011-05-16

arxiv.org/abs/1105.3078v1

Computer Science

Computational Geometry

Submitted to CCCG11

Scientific paper

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\binom{n}{3}$, and this bound is tight. There are $n$ points having $\Omega(n^3/k^4 + n^2/k^2)$ distinct $k$-collinearities. Thus, the number of $k$-collinearities among $n$ points, for constant $k$, is $O(n^3)$, 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.

Affiliated with

Also associated with

No associations

Rating

Collinearities in Kinetic Point Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Collinearities in Kinetic Point Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Collinearities in Kinetic Point Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-77364