GEOMETRIC 3-DIMENSIONAL ASSIGNMENT PROBLEMS

Authors
SPIEKSMA FCR WOEGINGER GJ
Citation
Fcr. Spieksma et Gj. Woeginger, GEOMETRIC 3-DIMENSIONAL ASSIGNMENT PROBLEMS, European journal of operational research, 91(3), 1996, pp. 611-618
Citations number
20
Categorie Soggetti
Management,"Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
91
Issue
3
Year of publication
1996
Pages
611 - 618
Database
ISI
SICI code
0377-2217(1996)91:3<611:G3AP>2.0.ZU;2-Q
Abstract
We investigate two geometric special cases of the three-dimensional as signment problem: Given are three sets B, R and G (blue, red and green ) each containing n grid points in the Euclidean plane. We want to fin d a partition of B boolean OR R boolean OR G into n three-colored tria ngles such that (a) the total circumference of all triangles or (b) th e total area of all triangles becomes minimum. Both versions of the pr oblem are proved to be NP-hard.