elib
DLR-Header
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

Abstract

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
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Glück, Rolandroland.glueck (at) dlr.dehttps://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 SCOPUS:No
In ISI Web of Science:Yes
Volume:10185
DOI :10.1007/978-3-319-55911-7
Page Range:pp. 274-288
Editors:
EditorsEmail
Jäger, Gerhardjaeger@inf.unibe.ch
Gopal, T.V.gopal@annauniv.edu
Steila, Silviasteila@inf.unibe.ch
Publisher:Springer
Series Name:Lecture Notes in Computer Science
ISSN:0302-9743
ISBN:978-3-319-55910-0
Status:Published
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
Location: Augsburg
Institutes and Institutions:Institute of Structures and Design > Automation and Production Technology
Institute of Structures and Design > Flexible Automation Systems
Deposited By: Glück, Dr. Roland
Deposited On:11 Dec 2017 11:48
Last Modified:11 Dec 2017 11:48

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.