## Optimizing some constructions with bars: new geometric knapsack problemsby S. Bereg, J. M. Díaz-Báñez, D. Flores-Peñaloza, S. Langerman, P. Péñrez-Lantero, J. Urrutia
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
We prove that both the Maximum Fence Problem and the Maximum Umbrella Problem can be solved in O(nlog n) time. |