Geodesic
The problem of a maximal weighted area of axis-parallel rectangle that covers polygons
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 15 (2019) no. 4, pp. 592-602 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper presents the problem of finding the optimal location of the rectangle with the maximum weighted area. The dimensions of the rectangle are set, the sides of the rectangle are parallel to the axes. On the plane, there are non-self-intersecting polygons of arbitrary shape with a given density. The weighted area of a rectangle is calculated as a sum of the area of the parts of polygons covered by the rectangle multiplied by their densities. The algorithm for solving the problem is described. This problem arises when determining the places of forest felling when the planned cutting area can be modelled by a rectangle, and the polygons describe the areas with same forest taxation, for each of which is known forest stock per hectare.
Keywords: maximizing range sum (MaxRS), maximizing area-range sum, maximizing weighted area-range sum
Mots-clés : polygons. 
@article{VSPUI_2019_15_4_a13,
     author = {L. V. Shchegoleva and R. V. Voronov and L. Sedov},
     title = {The problem of a maximal weighted area of axis-parallel rectangle that covers polygons},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {592--602},
     year = {2019},
     volume = {15},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2019_15_4_a13/}
}
TY  - JOUR
AU  - L. V. Shchegoleva
AU  - R. V. Voronov
AU  - L. Sedov
TI  - The problem of a maximal weighted area of axis-parallel rectangle that covers polygons
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2019
SP  - 592
EP  - 602
VL  - 15
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2019_15_4_a13/
LA  - en
ID  - VSPUI_2019_15_4_a13
ER  - 
%0 Journal Article
%A L. V. Shchegoleva
%A R. V. Voronov
%A L. Sedov
%T The problem of a maximal weighted area of axis-parallel rectangle that covers polygons
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2019
%P 592-602
%V 15
%N 4
%U http://geodesic.mathdoc.fr/item/VSPUI_2019_15_4_a13/
%G en
%F VSPUI_2019_15_4_a13
L. V. Shchegoleva; R. V. Voronov; L. Sedov. The problem of a maximal weighted area of axis-parallel rectangle that covers polygons. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 15 (2019) no. 4, pp. 592-602. http://geodesic.mathdoc.fr/item/VSPUI_2019_15_4_a13/

[1] Hussain M. M., Trajcevski G., “Maximizing area-range sum for spatial shapes (MAxRS3)”, SSDBM18: 30th International Conference on Scientific and Statistical Database Management (July 9–11, 2018, Bozen-Bolzano, Italy), ACM, New York, USA, 5 pp. | DOI

[2] I. R. Shegelman, V. M. Lukashevich, Preparatory work in the national forest management system, Monograph, Publishing House Petrozavodsk State University, Petrozavodsk, 2012, 84 pp. (In Russian)

[3] J. Bentley, “Programming Pearls Algorithm design techniques”, Communications of the ACM, 27:9 (1984), 865–873 | DOI | MR

[4] P. Fischer, K. Höffgen, H. Lefmann, T. Luczak, “Approximations with axis-aligned rectangles”, Fundamentals of Computation Theory, 710 (1993), 244–255 | DOI | Zbl

[5] T. Fukuda, Y. Morimoto, S. Morishita, T. Tokuyama, “Data mining using two-dimensional optimized association rules: Scheme, algorithms, and visualization”, ACM SIGMOD Record, 25:2 (1996), 13–23 | DOI | MR

[6] H. Tamaki, T. Tokuyama, “Algorithms for the maximum subarray problem based on matrix multiplication”, Interdisciplinary Information Sciences, 6:2 (2000), 99–104 | DOI | MR | Zbl

[7] T. Takaoka, “Efficient algorithms for the maximum subarray problem by distance matrix multiplication”, Electronic Notes in Theoretical Computer Science, 61 (2002), 191–200 | DOI | Zbl

[8] K. Daniels, V. Milenkovic, D. Roth, Finding the largest rectangle in several classes of polygons, Harvard University Press, Cambridge, Massachusetts, 1995, 40 pp.

[9] S. C. Nandy, B. B. Bhattacharya, “A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids”, Computers Mathematical Applications (Computers and Mathematics with Applications), 29:8 (1995), 45–61 | DOI | MR | Zbl

[10] A. Backurs, N. Dikkala, C. Tzamos, Tight hardness results for maximum weight rectangles, arXiv: (accessed: May 15, 2019) 1602.05837 | MR