Glück, Roland (2017) Covering Polygons with Rectangles. In: Theory and Applications of Models of Computation, Proceedings, 10185, Seiten 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.
Es ist eine neuere Version dieses Eintrags verfügbar. |
Dieses Archiv kann nicht den Volltext zur Verfügung stellen.
Offizielle URL: http://link.springer.com/chapter/10.1007%2F978-3-319-55911-7_20
Kurzfassung
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.
elib-URL des Eintrags: | https://elib.dlr.de/112094/ | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Dokumentart: | Konferenzbeitrag (Vortrag) | ||||||||||||||||
Titel: | Covering Polygons with Rectangles | ||||||||||||||||
Autoren: |
| ||||||||||||||||
Datum: | April 2017 | ||||||||||||||||
Erschienen in: | Theory and Applications of Models of Computation, Proceedings | ||||||||||||||||
Referierte Publikation: | Ja | ||||||||||||||||
Open Access: | Nein | ||||||||||||||||
Gold Open Access: | Nein | ||||||||||||||||
In SCOPUS: | Nein | ||||||||||||||||
In ISI Web of Science: | Ja | ||||||||||||||||
Band: | 10185 | ||||||||||||||||
DOI: | 10.1007/978-3-319-55911-7 | ||||||||||||||||
Seitenbereich: | Seiten 274-288 | ||||||||||||||||
Herausgeber: |
| ||||||||||||||||
Verlag: | Springer | ||||||||||||||||
Name der Reihe: | Lecture Notes in Computer Science | ||||||||||||||||
ISSN: | 0302-9743 | ||||||||||||||||
ISBN: | 978-3-319-55910-0 | ||||||||||||||||
Status: | veröffentlicht | ||||||||||||||||
Stichwörter: | Cover, Polygon, Rectangle | ||||||||||||||||
Veranstaltungstitel: | 14th Annual Conference on Theory and Applications of Models of Computation | ||||||||||||||||
Veranstaltungsort: | Bern, Schweiz | ||||||||||||||||
Veranstaltungsart: | internationale Konferenz | ||||||||||||||||
Veranstaltungsdatum: | 20.-22. Apr. 2017 | ||||||||||||||||
Veranstalter : | Universität Bern | ||||||||||||||||
HGF - Forschungsbereich: | Luftfahrt, Raumfahrt und Verkehr | ||||||||||||||||
HGF - Programm: | Raumfahrt | ||||||||||||||||
HGF - Programmthema: | Technik für Raumfahrtsysteme | ||||||||||||||||
DLR - Schwerpunkt: | Raumfahrt | ||||||||||||||||
DLR - Forschungsgebiet: | R SY - Technik für Raumfahrtsysteme | ||||||||||||||||
DLR - Teilgebiet (Projekt, Vorhaben): | R - Leichtbau-Robotik [SY], L - Strukturen und Werkstoffe (alt) | ||||||||||||||||
Standort: | Stuttgart | ||||||||||||||||
Institute & Einrichtungen: | Institut für Faserverbundleichtbau und Adaptronik Institut für Faserverbundleichtbau und Adaptronik > Verbundprozesstechnologien Institut für Bauweisen und Strukturtechnologie > Automation und Produktionstechnologie ?? 84 ?? | ||||||||||||||||
Hinterlegt von: | Glück, Dr. Roland | ||||||||||||||||
Hinterlegt am: | 18 Sep 2017 15:33 | ||||||||||||||||
Letzte Änderung: | 18 Sep 2017 15:33 |
Verfügbare Versionen dieses Eintrags
- Covering Polygons with Rectangles. (deposited 18 Sep 2017 15:33) [Gegenwärtig angezeigt]
Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags