Change search
ReferencesLink to record
Permanent link

Direct link
Non-overlapping Constraints between Convex Polytopes
Number of Authors: 3
2001 (English)Report (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 2001, 1. , 17 p.
SICS Technical Report, ISSN 1100-3154 ; 2001:12
Keyword [en]
Non-overlapping Constraint, Compulsory Part, Sweep
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-14292OAI: diva2:1035580
Available from: 2016-10-13 Created: 2016-10-13

Open Access in DiVA

fulltext(174 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 174 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link