Ponencia
On geometric properties of enumerations of axis-parallel rectangles
Autor/es | Vyatkina, Kira |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-06 |
Publicado en |
|
Resumen | We show that for any set of non-overlapping axis-parallel rectangles in the plane, there exists a sloping enumeration, such that the numbers of rectangles intersected by any line with a non-negative slope increase along ... We show that for any set of non-overlapping axis-parallel rectangles in the plane, there exists a sloping enumeration, such that the numbers of rectangles intersected by any line with a non-negative slope increase along this line. Such enumeration can be computed in the optimal time Θ(n log n) using linear space. The notion of a sloping enumeration can be generalized to higher dimensions; however, already in three-dimensional space it may not exist. We also consider a strip packing problem for a set of rectangles with a fixed enumeration, which is required to be sloping for the resulting packing. This problem is proved to be NP-hard in any dimension d ≥ 2. |
Identificador del proyecto | 04-01-00173 |
Cita | Vyatkina, K. (2004). On geometric properties of enumerations of axis-parallel rectangles. En 20th European Workshop on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On geometric properties of ... | 128.1Kb | [PDF] | Ver/ | |