Solving disjunctive constraints for interactive graphical applications

Kim Marriott; Peter Moulder; Peter J Stuckey; Alan Borning

doi:10.1007/3-540-45578-7_25

Solving disjunctive constraints for interactive graphical applications

Kim Marriott, Peter Moulder, Peter J Stuckey, Alan Borning

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

21 Citations (Scopus)

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 showhere that is in fact possible to (re-)solve systems of disjunctive constraints representing non-overlap constraints suficiently 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 between disjuncts that are adjacent in the sense that they share the current solution. We give both a generic algorithm, and a version specialised for linear arithmetic constraints that makes use of the Cassowary constraint solving algorithm.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming – CP 2001
Subtitle of host publication	7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings
Editors	Toby Walsh
Place of Publication	Berlin Germany
Pages	361-376
Number of pages	16
DOIs	https://doi.org/10.1007/3-540-45578-7_25
Publication status	Published - 2001
Event	International Conference on Principles and Practice of Constraint Programming 2001 - Paphos, Cyprus Duration: 26 Nov 2001 → 1 Dec 2001 Conference number: 7th

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2239
ISSN (Print)	0302-9743

Conference

Conference	International Conference on Principles and Practice of Constraint Programming 2001
Abbreviated title	CP 2001
Country/Territory	Cyprus
City	Paphos
Period	26/11/01 → 1/12/01

Access to Document

10.1007/3-540-45578-7_25

Cite this

Marriott, K., Moulder, P., Stuckey, P. J., & Borning, A. (2001). Solving disjunctive constraints for interactive graphical applications. In T. Walsh (Ed.), Principles and Practice of Constraint Programming – CP 2001: 7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings (pp. 361-376). (Lecture Notes in Computer Science; Vol. 2239).. https://doi.org/10.1007/3-540-45578-7_25

Marriott, Kim ; Moulder, Peter ; Stuckey, Peter J et al. / Solving disjunctive constraints for interactive graphical applications. Principles and Practice of Constraint Programming – CP 2001: 7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings. editor / Toby Walsh. Berlin Germany, 2001. pp. 361-376 (Lecture Notes in Computer Science).

@inproceedings{dfb8c7e5a9aa44f88ffe6a4eca8a2010,

title = "Solving disjunctive constraints for interactive graphical applications",

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 showhere that is in fact possible to (re-)solve systems of disjunctive constraints representing non-overlap constraints suficiently 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 between disjuncts that are adjacent in the sense that they share the current solution. We give both a generic algorithm, and a version specialised for linear arithmetic constraints that makes use of the Cassowary constraint solving algorithm.",

author = "Kim Marriott and Peter Moulder and Stuckey, {Peter J} and Alan Borning",

year = "2001",

doi = "10.1007/3-540-45578-7_25",

language = "English",

isbn = "3540428631",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "361--376",

editor = "Toby Walsh",

booktitle = "Principles and Practice of Constraint Programming – CP 2001",

note = "International Conference on Principles and Practice of Constraint Programming 2001, CP 2001 ; Conference date: 26-11-2001 Through 01-12-2001",

}

Marriott, K, Moulder, P, Stuckey, PJ & Borning, A 2001, Solving disjunctive constraints for interactive graphical applications. in T Walsh (ed.), Principles and Practice of Constraint Programming – CP 2001: 7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2239, Berlin Germany, pp. 361-376, International Conference on Principles and Practice of Constraint Programming 2001, Paphos, Cyprus, 26/11/01. https://doi.org/10.1007/3-540-45578-7_25

Solving disjunctive constraints for interactive graphical applications. / Marriott, Kim; Moulder, Peter; Stuckey, Peter J et al.
Principles and Practice of Constraint Programming – CP 2001: 7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings. ed. / Toby Walsh. Berlin Germany, 2001. p. 361-376 (Lecture Notes in Computer Science; Vol. 2239).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Solving disjunctive constraints for interactive graphical applications

AU - Marriott, Kim

AU - Moulder, Peter

AU - Stuckey, Peter J

AU - Borning, Alan

N1 - Conference code: 7th

PY - 2001

Y1 - 2001

N2 - 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 showhere that is in fact possible to (re-)solve systems of disjunctive constraints representing non-overlap constraints suficiently 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 between disjuncts that are adjacent in the sense that they share the current solution. We give both a generic algorithm, and a version specialised for linear arithmetic constraints that makes use of the Cassowary constraint solving algorithm.

AB - 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 showhere that is in fact possible to (re-)solve systems of disjunctive constraints representing non-overlap constraints suficiently 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 between disjuncts that are adjacent in the sense that they share the current solution. We give both a generic algorithm, and a version specialised for linear arithmetic constraints that makes use of the Cassowary constraint solving algorithm.

U2 - 10.1007/3-540-45578-7_25

DO - 10.1007/3-540-45578-7_25

M3 - Conference Paper

SN - 3540428631

T3 - Lecture Notes in Computer Science

SP - 361

EP - 376

BT - Principles and Practice of Constraint Programming – CP 2001

A2 - Walsh, Toby

CY - Berlin Germany

T2 - International Conference on Principles and Practice of Constraint Programming 2001

Y2 - 26 November 2001 through 1 December 2001

ER -

Marriott K, Moulder P, Stuckey PJ, Borning A. Solving disjunctive constraints for interactive graphical applications. In Walsh T, editor, Principles and Practice of Constraint Programming – CP 2001: 7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings. Berlin Germany. 2001. p. 361-376. (Lecture Notes in Computer Science). doi: 10.1007/3-540-45578-7_25