Academic
Publications
Dynamic approximation of complex graphical constraints by linear constraints

Dynamic approximation of complex graphical constraints by linear constraints,10.1145/571985.572012,Nathan Hurst,Kim Marriott,Peter Moulder

Dynamic approximation of complex graphical constraints by linear constraints   (Citations: 8)
BibTex | RIS | RefWorks Download
Current constraint solving techniques for interactive graphical applications cannot satisfactorily handle constraints such as non-overlap, or containment within non-convex shapes or shapes with smooth edges. We present a generic new technique for efficiently handling such kinds of constraints based on trust regions and linear arithmetic constraint solving. Our approach is to model these more complex constraints by a dynamically changing conjunction of linear constraints. At each stage, these give a local approximation to the complex constraints. During direct manipulation, linear constraints in the current local approximation can become active indicating that the current solution is on the boundary of the trust region for the approximation. The associated complex constraint is notified and it may choose to modify the current linear approximation. Empirical evaluation demonstrates that it is possible to (re-)solve systems of linear constraints that are dynamically approximating complex constraints such as non-overlap sufficiently quickly to support direct manipulation in interactive graphical applications.
Conference: User Interface Software and Technology - UIST , pp. 191-200, 2002
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The key to our approach is the use of dynamic linear approximation (DLA) [16, 12]...
    • ...The most closely related work are our earlier papers introducing DLA [16, 12]...
    • ...Dynamic linear approximation (DLA) [16, 12] is a recent technique for handling non-linear constraints that builds upon the aforementioned ecient linear constraint solving algorithms...
    • ...This was improved in [12] by storing only the current conguration in the solver and dynamically generating and checking satisability of other congurations when required...

    Graeme Gangeet al. Smooth Linear Approximation of Non-overlap Constraints

    • ...Our initial prototype implementation [25,18] is very promisin g, but we need to develop a methodology and theoretical justification for desig ning such linear approximations...

    Kim Marriottet al. Towards Flexible Graphical Communication Using Adaptive Diagrams

    • ...Recent progress of methods for constraint hierarchies has enabled use of nonlinear constraints such as Euclidean geometric constraints, nonoverlap constraints, and graph layout constraints [13, 14]...
    • ...In [14], a method is presented that handles complex graphical constraints such as nonoverlap constraints by dynamically approximating them by linear constraints...
    • ...Previous research on constraint hierarchies often focused on incremental constraint satisfaction [1, 6, 8, 12, 14, 16]...
    • ...However, if we can expect constraint hierarchies to be “almost linear” as in [14], incrementality will be useful for speeding up constraint satisfaction...

    Hiroshi Hosobe. Hierarchical nonlinear constraint satisfaction

    • ...Our table layout algorithm is based on linear programming techniques [7] developed in operations research for finding the solution to a system of linear arithmetic constraints which best minimizes a linear objective function and a dynamic linear approximation technique used in interactive graphical applications for modelling complex non-linear constraints by a changing collection of linear constraints [8]...
    • ...This is an example of Dynamic Linear Approximation [8] in which non-linear constraints are approximated by linear constraints and is a reasonably well known approach from operations research...

    Nathan Hurstet al. Towards optimal table layout

    • ...Recent work has demonstrated a technique for using sets of linear constraints to approximate nonlinear constraints [14], but the general problem still exists...

    James Fogartyet al. GADGET: a toolkit for optimization-based approaches to interface and d...

Sort by: