Conference Proceedings
Solving disjunctive constraints for interactive graphical applications
K Marriott, P Moulder, PJ Stuckey, A Borning
Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics | Published : 2001
Abstract
In interactive graphical applications we often require that objects do not overlap. Such non-overlap constraints can be modelled as disjunctions of arithmetic inequalities. Unfortunately, disjunctions are typically not handled by constraint solvers that support direct manipulation, in part because solving such problems is NP-hard. We show here that is in fact possible to (re-)solve systems of disjunctive constraints representing non-overlap constraints sufficiently fast to support direct manipulation in interactive graphical applications. The key insight behind our algorithms is that the disjuncts in a non-overlap constraint are not disjoint: during direct manipulation we need only move betw..
View full abstract