Non-overlapping Constraints between Convex Polytopes
Number of Authors: 3
2001 (English)Report (Refereed)
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.
Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 2001, 1. , 17 p.
SICS Technical Report, ISSN 1100-3154 ; 2001:12
Non-overlapping Constraint, Compulsory Part, Sweep
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22104OAI: oai:DiVA.org:ri-22104DiVA: diva2:1041646