Indigo: A Local Propagation Algorithm for Inequality Constraints

Authors: Alan Borning, Richard Anderson, and Bjorn Freeman-Benson

In Proceedings of the 1996 ACM Symposium on User Interface Software and Technology, pages 129-136.


Inequality constraints are useful for specifying various aspects of user interfaces, such as constraints that one window is to the left of another, or that an object is contained within a rectangle. However, current local propagation constraint solvers can't handle inequality constraints. We present Indigo, an efficient local propagation algorithm for satisfying acyclic constraint hierarchies, including inequality constraints.

full paper (compressed postscript)

A companion technical report, "The Indigo Algorithm", UW tech report 96-05-01, contains additional material (proofs of theorems and definitions of interval operations).

Constraints home page