Maximum Plane Trees in Multipartite Geometric Graphs
Maximum Plane Trees in Multipartite Geometric Graphs
复制标题
多部分几何图中的最大平面树
作者：
Ahmad Biniaz;P. Bose;Kimberly Crosbie;J. Carufel;D. Eppstein;A. Maheshwari;M. Smid
几何图是一个图，其顶点是平面上的点，其边是点之间的直线段。几何图中的平面生成树是不交叉的生成树。设R和B是平面上的两个不相交的点集，使得$$Rcup B$$R ∈ B处于一般位置，并且设$$n=| Rcup B| $$n=| R B|.假设R的点是红色的，B的点是蓝色的。双色平面生成树是具有二分性（R，B）的完全二部几何图中的平面生成树。本文研究了最大双色平面生成树问题，即计算具有最大总边长的双色平面生成树的问题。1.对于最大双色平面生成树问题，我们提出了一个近似算法，其运行时间为$$O（nlogn）$$O（nlogn）2.我们还考虑了这个问题的多色版本，其中输入点用$$k>2$$k>2种颜色着色。本文给出了一个计算完全k-部几何图中平面生成树的近似算法，当k= 3 k =3时，其比率为1 / 6，当k = 4k = 4.3时，其比率为1 / 8。在完全几何图中计算最大平面生成树的问题。对于这个问题，我们给出了一个近似算法，其比值为0.503;这是Dumitrescu和Tóth（Discrete Comput Geom 44（4）：727-752，2010）提出的算法的扩展，其比值为0.502.4。对于凸位置的点，最大双色平面生成树问题可以在O（n^3）O（n3）时间内求解。我们提出了一个O（n^5）O（n5）时间的算法来解决这个问题的情况下，红点位于一条线上，蓝点位于线的一侧。
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 $$Rcup B$$R∪B is in general position, and let $$n=|Rcup B|$$n=|R∪B|. 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.1.For the maximum bichromatic plane spanning tree problem, we present an approximation algorithm with ratio 1 / 4 that runs in $$O(nlog n)$$O(nlogn) time.2.We also consider the multicolored version of this problem where the input points are colored with $$k>2$$k>2 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$$k=3, and 1 / 8 if $$kgeqslant 4$$k⩾4.3.We also revisit the special case of the problem where $$k=n$$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 Tóth (Discrete Comput Geom 44(4):727–752, 2010) whose ratio is 0.502.4.For points that are in convex position, the maximum bichromatic plane spanning tree problem can be solved in $$O(n^3)$$O(n3) time. We present an $$O(n^5)$$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.