DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Covering Polygons with Rectangles

Glück, Roland (2017) Covering Polygons with Rectangles. In: Theory and Applications of Models of Computation, Proceedings, 10185, pp. 274-288. Springer. 14th Annual Conference on Theory and Applications of Models of Computation, 20.-22. Apr. 2017, Bern, Schweiz. doi: 10.1007/978-3-319-55911-7. ISBN 978-3-319-55910-0. ISSN 0302-9743.

Full text not available from this repository.

Official URL: http://link.springer.com/chapter/10.1007%2F978-3-319-55911-7_20


A well-known and well-investigated family of hard optimization problems deals with nesting, i.e., the non-overlapping placing of polygons to be cut from a rectangle or the plane whilst minimizing the waste. Here we consider the in some sense inverse problem of a subsequent step in production technology: given a set of polygons in the plane and an axis-aligned rectangle (modeling a gripping device), we seek the minimum number of copies of the rectangle such that every polygon is completely covered by at least one copy of the rectangle. As motions of the given rectangle for obtaining the copies we investigate the cases of translation in x-direction, of arbitrary translation and of arbitrary translation combined with rotation. We give a generic algorithm for all three cases which leads to a polynomial-time algorithm for the first case. The other two cases are NP-hard so we introduce a rather straightforward algorithm for the second case and two different approaches to the third one. Finally, we give experimental results and compare them to the theoretical analysis done before.

Item URL in elib:https://elib.dlr.de/114934/
Document Type:Conference or Workshop Item (Speech)
Title:Covering Polygons with Rectangles
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Glück, RolandUNSPECIFIEDhttps://orcid.org/0000-0001-7909-1942
Date:April 2017
Journal or Publication Title:Theory and Applications of Models of Computation, Proceedings
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:Yes
Page Range:pp. 274-288
EditorsEmailEditor's ORCID iD
Jäger, Gerhardjaeger@inf.unibe.chUNSPECIFIED
Gopal, T.V.gopal@annauniv.eduUNSPECIFIED
Steila, Silviasteila@inf.unibe.chUNSPECIFIED
Series Name:Lecture Notes in Computer Science
Keywords:Cover, Polygon, Rectangle
Event Title:14th Annual Conference on Theory and Applications of Models of Computation
Event Location:Bern, Schweiz
Event Type:international Conference
Event Dates:20.-22. Apr. 2017
Organizer:Universität Bern
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Aeronautics
HGF - Program Themes:fixed-wing aircraft
DLR - Research area:Aeronautics
DLR - Program:L AR - Aircraft Research
DLR - Research theme (Project):L - Structures and Materials (old)
Location: Augsburg
Institutes and Institutions:Institute of Structures and Design > Automation and Production Technology
Deposited By: Glück, Dr. Roland
Deposited On:11 Dec 2017 11:48
Last Modified:22 Jan 2021 21:10

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.