Consider the following scenario: A 911 dispatcher receives a call about a fire and needs to dispatch the closest fire truck. There are two difficulties with locating the appropriate vehicle to dispatch. First, the vehicles are constantly on the move. Second, there are different types of emergency vehicles, whereas the dispatcher specifically needs a fire truck.
Locating the closest unit of certain type under these assumptions is the dynamic vertex-labeled distance query problem on the road network graph. Each vertex in this graph can be annotated with a label that represents the type of the emergency vehicle currently located at that vertex. An alternative scenario where this problem is relevant is when one wishes to find a service provider (e.g., gas station, coffee shop), but different locations are open at different times of the day.
A data structure that answers distance queries between a vertex and a label, and supports label updates is called a dynamic vertex-labeled distance oracle. We model the road map as a planar graph, and extend previous results for the static case (where labels are fixed). We present oracles with polylogarithmic update and query times (in the number of vertices) that require nearly linear space.
Itay Laish, IDC Herzliya