Paper Info
Title
A generic geometrical constraint kernel in space and time for handling polymorphic k-dimensional objects
Abstract
This paper introduces a geometrical constraint kernel for handling the location in space and time of polymorphic k-dimensional objects subject to various geometrical and time constraints. The constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. These constraints are handled globally by the kernel. We first illustrate how tomodel several placement problems with the constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.
Year
DOI
Venue
2007
10.1007/978-3-540-74970-7_15
CP
Keywords
Field
DocType
generic geometrical constraint kernel,polymorphic k-dimensional object,complex shape,placement problem,million integer variable,new constraint,simple shape,generic k-dimensional lexicographic sweep,constraint kernel,time constraint,geometrical constraint kernel,polymorphism
Kernel (linear algebra),Integer,Mathematical optimization,Constraint (mathematics),Kernel embedding of distributions,Computer science,Spacetime,Constraint programming,Filter (signal processing),Lexicographical order
Conference
Volume
ISSN
Citations 
4741
0302-9743
20
PageRank 
References 
Authors
1.07
7
5
Name
Order
Citations
PageRank
N. Beldiceanu1201.07
Mats Carlsson297579.24
E. Poder3201.07
R. Sadek4201.07
C. Truchet5372.16