Optimizing some constructions with bars: new geometric knapsack problems |
| |
| Authors: | S. Bereg J. M. Díaz-Báñez D. Flores-Peñaloza S. Langerman P. Pérez-Lantero J. Urrutia |
| |
| Affiliation: | 1.Department of Computer Science,University of Texas at Dallas,Richardson,USA;2.Departamento de Matemática Aplicada II,Universidad de Sevilla,Sevilla,Spain;3.Facultad de Ciencias,Universidad Nacional Autónoma de México,Ciudad de México,Mexico;4.Département d’Informatique,Université Libre de Bruxelles (ULB),Brussels,Belgium;5.Escuela de Ingeniería Civil en Informática,Universidad de Valparaíso,Valparaíso,Chile;6.Instituto de Matemáticas,Universidad Nacional Autónoma de México,Ciudad de México,Mexico |
| |
| Abstract: | A set of vertical bars planted on given points of a horizontal line defines a fence composed of the quadrilaterals bounded by successive bars. A set of bars in the plane, each having one endpoint at the origin, defines an umbrella composed of the triangles bounded by successive bars. Given a collection of bars, we study how to use them to build the fence or the umbrella of maximum total area. We present optimal algorithms for these constructions. The problems introduced in this paper are related to the Geometric Knapsack problems (Arkin et al. in Algorithmica 10:399–427, 1993) and the Rearrangement Inequality (Wayne in Scripta Math 12(2):164–169, 1946). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
