Rooted Uniform Monotone Minimum Spanning Trees

摘要

We study the construction of the minimum cost spanning geometric graph of a given rooted point set P where each point of P is connected to the root by a path that satisfies a given property. We focus on two properties, namely the monotonicity w.r.t. a single direction (y-monotonicity) and the monotonicity w.r.t. a single pair of orthogonal directions (xy-monotonicity). We propose algorithms that compute the rooted y-monotone (xy-monotone) minimum spanning tree of P in O(|P| log~2 |P|) (resp. O(|P| log~3 |P|)) time when the direction (resp. pair of orthogonal directions) of monotonicity is given, and in O(|P|~2 log |P|) time when the optimum direction (resp. pair of orthogonal directions) has to be determined. We also give simple algorithms which, given a rooted connected geometric graph, decide if the root is connected to every other vertex by paths that are all monotone w.r.t. the same direction (pair of orthogonal directions).