  This paper presents an optimal $\Theta(n \log n)$ algorithm for determining
time-minimal rectilinear paths among $n$ transient rectilinear obstacles. An
obstacle is transient if it exists in the scene only for a specific time
interval, i.e., it appears and then disappears at specific times. Given a point
robot moving with bounded speed among transient rectilinear obstacles and a
pair of points $s$, $d$, we determine a time-minimal, obstacle-avoiding path
from $s$ to $d$. The main challenge in solving this problem arises as the robot
may be required to wait for an obstacle to disappear, before it can continue
moving toward the destination. Our algorithm builds on the continuous Dijkstra
paradigm, which simulates propagating a wavefront from the source point. We
also solve a query version of this problem. For this, we build a planar
subdivision with respect to a fixed source point, so that minimum arrival time
to any query point can be reported in $O(\log n)$ time, using point location
for the query point in this subdivision.

Computational Geometry