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:

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
ID Code:231

Repository Staff Only: item control page


Aharoni, R., P. Haxell, Hall's theorem for hypergraphs, J. Graph Th. 35, (2000), pp. 83-88.

Doddi S., M.V. Marathe, A. Mirizaian, B.M.E. Moret, B. Zhu, Map labeling and its generalizations. Proc. 8th ACM-SIAM Symp. on Discrete Algorithms, (1997), pp. 148-157.

Edmonds, J., Paths, trees and flowers, Can. J. Math. 17, (1965), pp. 449-467.

Fiala, J., J. Kratochvíl, A. Proskurowski, Systems of sets and their representatives, manuscript 2002.

Hall, P., On representatives of subsets, J. London Math. Soc. 10, (1935), pp. 26-30.

Kratochvíl, J., A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Appl. Math. 52, (1994), pp. 233-252.

Marks, J., S. Shieber, The computational complexity of cartographic label placement, Technical Report TR-05-91, Harvard CS, 1991.

Simons, B., A fast algorithm for single processor scheduling, Proc. 19th Symp. Foundations of Computer Science, (1978), pp. 246-252.