SODA

Non-overlapping Constraints between Convex Polytopes

Beldiceanu, Nicolas and Guo, Qi and Thiel, Sven (2001) Non-overlapping Constraints between Convex Polytopes. [SICS Report]

[img]Postscript
302Kb
[img]
Preview
PDF
173Kb

Abstract

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 [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:SICS Report
Uncontrolled Keywords:Non-overlapping Constraint, Compulsory Part, Sweep
ID Code:2382
Deposited By:Vicki Carleson
Deposited On:30 Jul 2009
Last Modified:18 Nov 2009 16:07

Repository Staff Only: item control page