Critical Placements of a Square or Circle amidst Trajectories for Junction Detection

Abstract

Motivated by automated junction recognition in tracking data, we study a problem of placing a square or disc of fixed size in an arrangement of lines or line segments in the plane. We let distances among the intersection points of the lines and line segments with the square or circle define a clustering, and study the complexity of \emph{critical} placements for this clustering. Here critical means that arbitrarily small movements of the placement change the clustering. A parameter ε defines the granularity of the clustering. Without any assumptions on ε, the critical placements have a trivial O(n4) upper bound. When the square or circle has unit size and 0<ε<1 is given, we show a refined O(n2/ε2) bound, which is tight in the worst case. We use our combinatorial bounds to design efficient algorithms to compute junctions. As a proof of concept for our algorithms we have a prototype implementation that showcases their application in a basic visualization of a set of n trajectories and their k most important junctions.