A Constraint Decomposition Method for Spatio-Temporal Configuration Problems

Abstract

This paper describes a flexible framework and an efficient algorithm for constraint-based spatio-temporal configuration problems. Binary constraints between spatio-temporal objects are first converted to constraint regions, which are then decomposed into hierarchical data structures; based on this constraint decomposition, an improved backtracking algorithm called HBT can compute a solution quite efficiently. In contrast to other approaches, the proposed method is characterized by the efficient handling of arbitrarily-shaped objects, and the flexible integration of quantitative and qualitative constraints; it allows a wide range of objects and constraints to be utilized for specifying a spatio-temporal configuration. The method is intended primarily for configuration problems in user interfaces, but can effectively be applied to similar problems in other areas as well.