Solving disjunctive constraints for interactive graphical applications

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

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    20 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 languageEnglish
    Title of host publicationPrinciples and Practice of Constraint Programming – CP 2001
    Subtitle of host publication7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings
    EditorsToby Walsh
    Place of PublicationBerlin Germany
    Pages361-376
    Number of pages16
    DOIs
    Publication statusPublished - 2001
    EventInternational Conference on Principles and Practice of Constraint Programming 2001 - Paphos, Cyprus
    Duration: 26 Nov 20011 Dec 2001
    Conference number: 7th

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume2239
    ISSN (Print)0302-9743

    Conference

    ConferenceInternational Conference on Principles and Practice of Constraint Programming 2001
    Abbreviated titleCP 2001
    CountryCyprus
    CityPaphos
    Period26/11/011/12/01

    Cite this