Technical Report No. 30, July 1991 - Abstract

Edmund Ihler, Gabriele Reich, Peter Widmayer:
On Shortest Networks for Classes of Points in the Plane

We are given a set P of points in the plane, together with a partition of P into classes of points; i.e., each point of P belongs to exactly one class. For a given network optimization problem, such as finding a minimum spanning tree or finding a minimum diameter spanning tree, we study the problem of choosing a subset P' of P that contains at least one point of each class and solving the network optimization problem for P', such that the solution is optimal among all possible choices for P'. We show that solving the minimum spanning tree problem for classes of points is defined by any of the Minkowski metrics L_p, 1 <= p <= infinity. In contrast, a class solution for the minimum diameter spanning tree problem can be computed in time O(|P|^3).

By proving the NP-completeness of the minimum spanning tree class problem we also get some results for distance graphs. Here, computing a class solutioin for the minimum spanning tree problem is NP-complete, even under several restrictions, e.g., if the graph is part of a unit grid and is a tree, where the vertex degree and the numver of vertices per class are both bounded by three. This is true even if the graph is a minimum spanning tree for its set of vertices