Geometric Systems of Disjoint Representatives
Fiala, Jirí and Kratochvíl, Jan and Proskurowski, Andrzej (2002) Geometric Systems of Disjoint Representatives. In: Graph Drawing, August 26-28, 2002, Irvine, CA, USA , pp. 110-117 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_11).
Full text not available from this repository.
Consider a finite collection of subsets of a metric space and ask for a system of representatives which are pairwise at a distance at least q, where q is a parameter of the problem. In discrete spaces this generalizes the well known problem of distinct representatives, while in Euclidean metrics the problem reduces to finding a system of disjoint balls. This problem is closely related to practical applications like scheduling or map labeling. We characterize the compu tational complexity of this geometric problem for the cases of L1 and L2 metrics and dimensions d=1,2. We show that for d=1 the problem can be solved in polynomial time, while for d=2 we prove that it is NP-hard. Our NP-hardness proof can be adjusted also for higher dimensions.
Repository Staff Only: item control page