Presentation
On geometric properties of enumerations of axis-parallel rectangles
dc.creator | Vyatkina, Kira | es |
dc.date.accessioned | 2017-03-06T07:50:33Z | |
dc.date.available | 2017-03-06T07:50:33Z | |
dc.date.issued | 2004 | |
dc.identifier.citation | Vyatkina, K. (2004). On geometric properties of enumerations of axis-parallel rectangles. En 20th European Workshop on Computational Geometry, Sevilla. | |
dc.identifier.uri | http://hdl.handle.net/11441/55280 | |
dc.description.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. | es |
dc.description.sponsorship | Russian Foundation for Basic Research | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | 20th European Workshop on Computational Geometry (2004). | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Rectangles | es |
dc.subject | Enumeration | es |
dc.subject | Orthogonal packing | es |
dc.subject | NP-hardness | es |
dc.title | On geometric properties of enumerations of axis-parallel rectangles | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.relation.projectID | 04-01-00173 | es |
idus.format.extent | 4 p. | es |
dc.eventtitle | 20th European Workshop on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |
Files | Size | Format | View | Description |
---|---|---|---|---|
On geometric properties of ... | 128.1Kb | [PDF] | View/ | |