## February 5, 2016:

#
On the Complexity of an Unregulated Traffic Crossing

##
Nil Mamano

The steady development of motor vehicle technology will enable cars
of the near future to assume an ever increasing role in the decision
making and control of the vehicle itself. In the foreseeable future,
cars will have the ability to communicate with one another in order to
better coordinate their motion. This motivates a number of interesting
algorithmic problems. One of the most challenging aspects of traffic
coordination involves traffic intersections. In this paper we consider a
simple and fundamental geometric optimization problem involving
coordinating the motion of vehicles through an intersection. We are
given a set of $n$ vehicles in the plane, each modeled as a unit length
line segment that moves monotonically, either horizontally or
vertically, subject to a maximum speed limit. Each vehicle is described
by a start and goal position and a start time and deadline. The question
is whether, subject to the speed limit, there exists a collision-free
motion plan so that each vehicle travels from its start position to its
goal position prior to its deadline. We present two results. We begin by
showing that this problem is $\mathsf{NP}$-complete with a reduction from
3-SAT. Second, we consider a constrained version in which cars traveling
horizontally can alter their speeds while cars traveling vertically
cannot. We present a simple algorithm that solves this problem in
$O(n\log n)$ time.

(Based on a paper by Philip Dasler and David M. Mount at WADS 2015.)