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 , pp. 110-117(Official URL:

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_11
Classifications: G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.630 Labeling

Actions (login required)

View Item View Item