These may be as simple as how best to place a pencil on a desk without having to reach too far and still keeping the work space clear, up to the question of where to place the next out of hundreds of thousands of transistors on a microchip.

Some of these questions have easy answers, while others are so complex that not even satisfactory solutions are ava- able, never mind asking for optimized placement.

The scales of problems reach from microchip design up to global trade and may demand consid- ation of one, two, three, or even more dimensions.

As modern life encounters an ever increasing concentration in many - spects, usually a multitude of restrictions will be imposed on a problem.

Theserestrictionsmaybeclassi?edasregionsoflimitedorforbiddenpla- ment of a new facility or as regions with limitations on traveling.

Areas where the placement of a new facility is forbidden, referred to as forbidden regions,canbeusedtomodel,forexample,protectedareasorregionswhere thegeographiccharacteristicsforbidtheconstructionofthedesiredfacility.

Limitations on traveling are constituted by barrier regions or obstacles like military regions,mountainranges,lakes,big rivers,interstatehighways,or, on smaller scales, machinery and conveyor belts in an industrial plant.