Beldiceanu, Nicolas and Guo, Qi and Thiel, Sven (2001) Non-overlapping Constraints between Convex Polytopes. [SICS Report]
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 generalization 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:||SICS Report|
|Uncontrolled Keywords:||Non-overlapping Constraint, Compulsory Part, Sweep|
|Deposited By:||Vicki Carleson|
|Deposited On:||30 Jul 2009|
|Last Modified:||18 Nov 2009 16:07|
Repository Staff Only: item control page