Sweep Based Algorithms for Constraint Propagation

			  Nicolas Beldiceanu
		    Intelligent Systems Laboratory
	      SICS, Lägerhyddsvägen 18, SE-75237 Uppsala
				Sweden
			   nicolas@sics.se

Sweep is a powerful method which was developed within computational
geometry in order to come up with efficient algorithms for problems
such as detecting intersections. This talk will present different ways
of using the idea of sweep within the context of constraint
programming in order to come up with filtering algorithms for
constraints such as:

* the multi-resource "cumulatives" constraint,

* a conjunction of elementary constraints where all constraints share
  two given variables,

* the cardinality operator where a given number of elementary constraints
  have to be satisfied,

* the non-overlapping constraint between polygons.

The work presented in this talk was done in collaboration with Mats
Carlsson, Guo Qi and Sven Thiel.