Rectilinear Shortest Path and Rectilinear Minimum Spanning Tree with Neighborhoods

We study the geometric shortest path and the minimum spanning treeproblem with neighborhoods in the L 1 metric. In this setting, we are given agraph G = (R, E), where R = {R 1 , . . . , R n } is a set of polygonal regions inthe plane. Placing a point p i inside each region R i turns G into an edge-weightedgraph G p , p = {p 1 , . . . , p n }, where the cost of an edge is the distance betweenthe points. The Shortest Path Problem with Neighborhoods asks, for given R s andR t , to find a placement p such that the resulting shortest s-t path in G p is smallestamong all graphs G p . The Minimum Spanning Tree Problem with Neighborhoodsasks for a placement p such that the resulting minimum spanning tree of G p hasthe smallest cost among all minimum spanning trees of all graphs G p . We studythese problems in the L 1 metric, and show that the shortest path problem withneighborhoods is solvable in polynomial time, whereas the minimum spanningtree problem with neighborhoods is NP-hard, even if the neighborhood regionsare segments.