Maximum Plane Trees in Multipartite Geometric Graphs

摘要

A geometric graph is a graph whose vertices are points in the plane and whose edges are straight-line segments between the points. A plane spanning tree in a geometric graph is a spanning tree that is non-crossing. Let R and B be two disjoint sets of points in the plane such that RB is in general position, and let n=|RB|. Assume that the points of R are colored red and the points of B are colored blue. A bichromatic plane spanning tree is a plane spanning tree in the complete bipartite geometric graph with bipartition (R,B). In this paper we consider the maximum bichromatic plane spanning tree problem, which is the problem of computing a bichromatic plane spanning tree of maximum total edge length.For the maximum bichromatic plane spanning tree problem, we present an approximation algorithm with ratio 1/4 that runs in O(nlogn) time.We also consider the multicolored version of this problem where the input points are colored with k2 colors. We present an approximation algorithm that computes a plane spanning tree in a complete k-partite geometric graph, and whose ratio is 1/6 if k=3, and 1/8 if k4.We also revisit the special case of the problem where k=n, i.e., the problem of computing a maximum plane spanning tree in a complete geometric graph. For this problem, we present an approximation algorithm with ratio 0.503; this is an extension of the algorithm presented by Dumitrescu and Toth (Discrete Comput Geom 44(4):727-752, 2010) whose ratio is 0.502.For points that are in convex position, the maximum bichromatic plane spanning tree problem can be solved in O(n3) time. We present an O(n5)-time algorithm that solves this problem for the case where the red points lie on a line and the blue points lie on one side of the line.