A time- and cost-optimal algorithm for interlocking sets-with applications

Given a family I of intervals, two intervals in I interlock if they overlap but neither of them strictly contains the other. A set of intervals in which every two are related in the reflexive transitive closure of the interlock relation is referred to as an interlocking set. The task is determining the maximal interlocking sets of I arises in numerous applications, including traffic control, robot arm manipulation, segmentation of range images, routing, automated surveillance systems, recognizing polygonal configurations, and code generation for parallel machines. Our first contribution is to show that any sequential algorithm that computes the maximal interlocking sets of a family of n intervals must take Ω(n log n) time in the algebraic tree model. Next, we show that any parallel algorithm for this problem must take Ω(log n) time in the CREW model even if an infinite number of processors and memory cells are available. We then go on to show that both the sequential and the parallel lower bounds are tight by providing matching algorithms running, respectively, in Θ(n log n) sequential time and in Θ(log n) time using n processors in the CREW model. At the same time, if the endpoints of the intervals are specified in sorted order, our sequential algorithm runs in O(n) time, improving the best previously known result. It is interesting to note that even if the endpoints are sorted, Ω(log n) is a time lower bound for solving the problem in the CREW model, regardless of the amount of resources available. As an application of our algorithm for interlocking sets, we obtain a time- and cost-optimal solution to a restricted version of the single row routing problem. The best previously known result for routing a set of n nets without street crossovers runs in O(log n loglog n) time using n processors in the CRCW model. By contrast, our algorithm runs in Θ(log n) time using n/log n processors in the CREW model, being both time- and cost-optimal