Repositorio de producción científica de la Universidad de Sevilla

On geometric properties of enumerations of axis-parallel rectangles

 

Advanced Search
 
Opened Access On geometric properties of enumerations of axis-parallel rectangles
Cites
Show item statistics
Icon
Export to
Author: Vyatkina, Kira
Date: 2004
Document type: Presentation
Abstract: 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.
Size: 128.1Kb
Format: PDF

URI: http://hdl.handle.net/11441/55280

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)