Manhattonian proximity in a simple polygon
Rolf Klein, Andrzej Lingas · 1992
Let P be a simple planar polygon. We present a linear worst-case time algorithm for constructing the bounded Voronoi diagram of P in the Manhattan metric, where each point z in P belongs to the region of the closest vertex of P that is visible from z. Among other consequences, the minimal spanning tree of the vertices in the Manhattan metric that is contained in P can be computed within optimal linear time.