Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
Constraint Solving
Direct Manipulation
Dynamic Change
Empirical Evaluation
Interactive Graphics
Linear Approximation
Linear Constraint
Trust Region
Related Publications
(3)
A modular geometric constraint solver for user interface applications
Solving Disjunctive Constraints for Interactive Graphical Applications
Practical methods of optimization
Subscribe
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
Edit
Dynamic approximation of complex graphical constraints by linear constraints
(
Citations: 8
)
BibTex

RIS

RefWorks
Download
Nathan Hurst
,
Kim Marriott
,
Peter Moulder
Current
constraint solving
techniques for interactive graphical applications cannot satisfactorily handle constraints such as nonoverlap, or containment within nonconvex 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 nonoverlap sufficiently quickly to support
direct manipulation
in interactive graphical applications.
Conference:
User Interface Software and Technology  UIST
, pp. 191200, 2002
DOI:
10.1145/571985.572012
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.
(
portal.acm.org
)
(
portal.acm.org
)
(
doi.acm.org
)
(
www.informatik.unitrier.de
)
(
portal.acm.org
)
(
www.csse.monash.edu.au
)
More »
Citation Context
(5)
...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 nonlinear 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 Gange
,
et al.
Smooth Linear Approximation of Nonoverlap 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 Marriott
,
et 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 nonlinear constraints by a changing collection of linear constraints [
8
]...
...This is an example of Dynamic Linear Approximation [
8
] in which nonlinear constraints are approximated by linear constraints and is a reasonably well known approach from operations research...
Nathan Hurst
,
et 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 Fogarty
,
et al.
GADGET: a toolkit for optimizationbased approaches to interface and d...
References
(21)
An Incremental Algorithm for Satisfying Hierarchies of Multiway, Dataflow Constraints
(
Citations: 65
)
Brad Vander Zanden
Journal:
ACM Transactions on Programming Languages and Systems  TOPLAS
, 1995
Multiway versus Oneway Constraints in User Interfaces: Experience with the DeltaBlue Algorithm
(
Citations: 125
)
Michael Sannella
,
John Maloney
,
Bjørn N. FreemanBenson
,
Alan Borning
Journal:
Software  Practice and Experience  SPE
, vol. 23, no. 5, pp. 529566, 1993
A modular geometric constraint solver for user interface applications
(
Citations: 17
)
Hiroshi Hosobe
Conference:
User Interface Software and Technology  UIST
, pp. 91100, 2001
Spatial data structures: quadtrees
(
Citations: 9
)
H. Samet
Published in 1989.
Solving Linear Arithmetic Constraints for User Interface Applications: Algorithm Details
(
Citations: 45
)
Alan Borning
,
Kim Marriott
,
Peter J. Stuckey
,
Yi Xiao
Published in 1997.
Sort by:
Citations
(8)
Smooth Linear Approximation of Nonoverlap Constraints
Graeme Gange
,
Kim Marriott
,
Peter J. Stuckey
Conference:
Conference on Diagrammatic Representation and Inference  Diagrams
, pp. 4559, 2008
Qualitative decision making in adaptive presentation of structured information
(
Citations: 13
)
Ronen I. Brafman
,
Carmel Domshlak
,
Solomon Eyal Shimony
Journal:
ACM Transactions on Information Systems  TOIS
, vol. 22, no. 4, pp. 503539, 2004
Towards Flexible Graphical Communication Using Adaptive Diagrams
(
Citations: 3
)
Kim Marriott
,
Bernd Meyer
,
Peter J. Stuckey
Conference:
Asian Computing Science Conference  ASIAN
, pp. 380394, 2004
Hierarchical nonlinear constraint satisfaction
(
Citations: 1
)
Hiroshi Hosobe
Conference:
ACM Symposium on Applied Computing  SAC
, pp. 1620, 2004
Towards optimal table layout
Nathan Hurst
,
Kim Marriott
Published in 2004.