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  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)|
|Deposited By:||INVALID USER|
|Deposited On:||15 Jul 2008|
|Last Modified:||18 Nov 2009 16:17|
Repository Staff Only: item control page