Inner approximation of distance constraints with existential quantification of parameters

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Inner approximation of distance constraints with existential quantification of parameters

Full text

Pdf (76 KB)

Source

Symposium on Applied Computing archive
Proceedings of the 2006 ACM symposium on Applied computing table of contents

Dijon, France

SESSION: Poster Papers table of contents

Pages: 1660 - 1661

Year of Publication: 2006

ISBN:1-59593-108-2

Authors

Carlos Grandón	Projet COPRIN, INRIA (Sophia-Antipolis)
Alexandre Goldsztejn	University of Nice-Sophia-Antipolis

Sponsor

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 17, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1141277.1141668 What is a DOI?

ABSTRACT

This paper presents and compares two methods for checking if a box is included inside the solution set of an equality constraint with existential quantification of its parameters. We focus on distance constraints, where each existentially quantified parameter has only one occurrence, because of their usefulness and their simplicity. The first method relies on a specific quantifier elimination based on geometric considerations whereas the second method relies on computations with generalized intervals (interval whose bounds are not constrained to be ordered). We show that on two dimensions problems, the two methods yield equivalent results. However, when dealing with higher dimensions, generalized intervals are more efficient.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Goldsztejn A. Définition et Applications des Extensions des Fonctions Réelles aux Intervalles Généralisés. PhD thesis, Université de Nice, Novembre 2005.
	2	Frédéric Benhamou and William J. Older. Applying Interval Arithmetic to Real, Integer and Boolean Constraints. Journal of Logic Programming, 32(1): 1--24, 1997.
	3	SIGLA/X group. Modal intervals (basic tutorial). Applications of Interval Analysis to Systems and Control (Proceedings of MISC'99), pages 157--227, 1999.
	4	James H. Davenport , Joos Heintz, Real quantifier elimination is doubly exponential, Journal of Symbolic Computation, v.5 n.1-2, p.29-35, February/April 1988 [doi>10.1016/S0747-7171(88)80004-X]
	5	Jean-Pierre P. Merlet, Parallel Robots, Kluwer Academic Publishers, Norwell, MA, 2000
	6	Herrero P., M. A. Sainz, Vehí J., and Jaulin L. Quantified set inversion with applications to control. In IEEE International Symposium on Computer Aided Control Systems Design, 2004.