Determine earliest collision among moving cars

You are given n cars moving over time. Each car has known initial state at time $t=0$:

• 1D case (straight road):
  • initial position $x_i$ (meters)
  • initial velocity $v_i$ (m/s)
  • constant acceleration $a_i$ (m/s²)
  • physical size represented as a radius $r_i$ (meters). (Cars collide when their intervals overlap, i.e., when center distance $\le r_i + r_j$ .)
• 2D case (flat plane):
  • initial position $(x_i, y_i)$
  • initial velocity $(v_{xi}, v_{yi})$
  • constant acceleration $(a_{xi}, a_{yi})$
  • radius $r_i$

A car’s position evolves as:

• 1D: $x_i(t) = x_i + v_i t + \tfrac{1}{2} a_i t^2$
• 2D: $\mathbf{p}_i(t) = \mathbf{p}_i + \mathbf{v}_i t + \tfrac{1}{2} \mathbf{a}_i t^2$

Tasks

1. 1D: Determine whether any collision occurs for $t \ge 0$ . If yes, return the earliest collision time and the pair of cars involved.
2. 2D: Same as (1), but in 2D (cars collide when Euclidean distance between centers $\le r_i + r_j$ ).

Requirements

• Provide an algorithm and implementable approach.
• Discuss time complexity and how you would optimize beyond the naive $O(n^2)$ pairwise checking.
• Handle edge cases such as:
  • collisions at $t=0$
  • cars with identical trajectories (overlapping for an interval)
  • numerical precision when solving for collision times

You may assume $n$ can be large (e.g., up to $10^5$), so a brute-force all-pairs solution may be too slow.