Non-overlapping constraint between convex polytopes

Beldiceanu, Nicolas and Guo, Qi and Thiel, Sven (2001) Non-overlapping constraint between convex polytopes. In: CP 2001, 7th International Conference on Principles and Practice of Constraint Programming, 26 Nov - 1 Dec 2001, Paphos, Cyprus.

Full text not available from this repository.


This paper deals with non-overlapping constraints between convex polytopes. Non-overlapping detection between fixed objects is a fundamental geometric primitive that arises in many applications. However from a constraint perspective it is natural to extend the previous problem to a non-overlapping constraint between two objects for which both positions are not yet fixed. A first contribution is to present theorems for convex polytopes, which allow coming up with general necessary conditions for non-overlapping. These theorems can be seen as a generalisation of the notion of compulsory part, which was introduced in 1984 by Lahrichi and Gondran [6] for managing non-overlapping constraint between rectangles. Finally, a second contribution is to derive from the previous theorems efficient filtering algorithms for two special cases: the non-overlapping constraint between two convex polygons as well as the non-overlapping constraint between d-dimensional boxes.

Item Type:Conference or Workshop Item (Paper)
ID Code:3068
Deposited On:15 Jul 2008
Last Modified:18 Nov 2009 16:17

Repository Staff Only: item control page