Geometric Systems of Disjoint RepresentativesFiala, Jiří and Kratochvíl, Jan and Proskurowski, Andrzej (2002) Geometric Systems of Disjoint Representatives. In: Graph Drawing, August 2628, 2002 , pp. 110117(Official URL: http://dx.doi.org/10.1007/3540361510_11). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540361510_11
AbstractConsider 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 NPhard. Our NPhardness proof can be adjusted also for higher dimensions.
Actions (login required)
