Optimizing some constructions with bars: new geometric knapsack problems
by S. Bereg, J. M. Díaz-Báñez, D. Flores-Peñaloza, S. Langerman, P. Péñrez-Lantero, J. UrrutiaAbstract: Maximum Fence Problem: Given n bars and n points on x-axis, place the vertical bars at the points such that the area of the fence is maximized. An example of a fence for n=6 is shown below.
In the Maximum Umbrella Problem, the bars are placed at the same point with prescribed slopes and the area of the umbrella is maximized. An example of an umbrella for n=8 is shown below.
We prove that both the Maximum Fence Problem and the Maximum Umbrella Problem can be solved in O(nlog n) time.