Fourier elimination for compiling constraint hierarchies

Abstract

Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces, such as requiring that one window be to the left of another, requiring that a pane occupy the leftmost 1/3 of a window, or preferring that an object be contained within a rectangle if possible. For interactive use, we need to solve similar constraint satisfaction problems repeatedly for each screen refresh, with each successive problem differing from the previous one only in the position of an input device and the previous state of the system. We present an algorithm for solving such systems of constraints using projection. The solution is compiled into very efficient, constraint-free co..