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.

Abstract

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