Approximating minimum-area rectangular and convex containers for packing convex polygons

H.W. Alt; M.T. de Berg; C. Knauer

doi:10.1007/978-3-662-48350-3_3

Approximating minimum-area rectangular and convex containers for packing convex polygons

H.W. Alt
, M.T. de Berg
, C. Knauer

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

1 Downloads (Pure)

Abstract

We investigate the problem of finding a minimum-area container for the disjoint packing of a set of convex polygons by translations. In particular, we consider axis-parallel rectangles or arbitrary convex sets as containers. For both optimization problems which are NP-hard we develop efficient constant factor approximation algorithms.

Original language	English
Title of host publication	Algorithms - ESA 2015
Subtitle of host publication	23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings
Editors	N. Bansel, I. Finocchi
Place of Publication	Dordrecht
Publisher	Springer
Pages	25-34
ISBN (Print)	978-3-662-48349-7
DOIs	https://doi.org/10.1007/978-3-662-48350-3_3
Publication status	Published - 2015

Publication series

Name	Lecture Notes in Computer Science
Volume	9294
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-662-48350-3_3

Cite this

Alt, H. W., de Berg, M. T., & Knauer, C. (2015). Approximating minimum-area rectangular and convex containers for packing convex polygons. In N. Bansel, & I. Finocchi (Eds.), Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings (pp. 25-34). (Lecture Notes in Computer Science; Vol. 9294). Springer. https://doi.org/10.1007/978-3-662-48350-3_3

@inproceedings{eebf29fc41c948bcae13d2abda77daeb,

title = "Approximating minimum-area rectangular and convex containers for packing convex polygons",

abstract = "We investigate the problem of finding a minimum-area container for the disjoint packing of a set of convex polygons by translations. In particular, we consider axis-parallel rectangles or arbitrary convex sets as containers. For both optimization problems which are NP-hard we develop efficient constant factor approximation algorithms.",

author = "H.W. Alt and \{de Berg\}, M.T. and C. Knauer",

year = "2015",

doi = "10.1007/978-3-662-48350-3\_3",

language = "English",

isbn = "978-3-662-48349-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "25--34",

editor = "N. Bansel and I. Finocchi",

booktitle = "Algorithms - ESA 2015",

address = "Germany",

}

Alt, HW, de Berg, MT & Knauer, C 2015, Approximating minimum-area rectangular and convex containers for packing convex polygons. in N Bansel & I Finocchi (eds), Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9294, Springer, Dordrecht, pp. 25-34. https://doi.org/10.1007/978-3-662-48350-3_3

Approximating minimum-area rectangular and convex containers for packing convex polygons. / Alt, H.W.; de Berg, M.T.; Knauer, C.
Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings. ed. / N. Bansel; I. Finocchi. Dordrecht: Springer, 2015. p. 25-34 (Lecture Notes in Computer Science; Vol. 9294).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximating minimum-area rectangular and convex containers for packing convex polygons

AU - Alt, H.W.

AU - de Berg, M.T.

AU - Knauer, C.

PY - 2015

Y1 - 2015

N2 - We investigate the problem of finding a minimum-area container for the disjoint packing of a set of convex polygons by translations. In particular, we consider axis-parallel rectangles or arbitrary convex sets as containers. For both optimization problems which are NP-hard we develop efficient constant factor approximation algorithms.

AB - We investigate the problem of finding a minimum-area container for the disjoint packing of a set of convex polygons by translations. In particular, we consider axis-parallel rectangles or arbitrary convex sets as containers. For both optimization problems which are NP-hard we develop efficient constant factor approximation algorithms.

U2 - 10.1007/978-3-662-48350-3_3

DO - 10.1007/978-3-662-48350-3_3

M3 - Conference contribution

SN - 978-3-662-48349-7

T3 - Lecture Notes in Computer Science

SP - 25

EP - 34

BT - Algorithms - ESA 2015

A2 - Bansel, N.

A2 - Finocchi, I.

PB - Springer

CY - Dordrecht

ER -

Approximating minimum-area rectangular and convex containers for packing convex polygons

Abstract

Publication series

Access to Document

Fingerprint

Cite this