The new coincidence check makes use of the topology and the edge-weights of the facility interactions graph, only. It is shown that the algorithm proposed is best possible in the sense that any condition detecting more coincidences has to use additional properties of the underlying normed space. Moreover, the amount of work necessary to detect all embedding space-independent coincidences increases only polynomially in the problem size given.

Key Words. Coincidence conditions, multifacility location problem, optimality criteria, flow problems