Geodesic
Solving some vector subset problems by Voronoi diagrams
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 4, pp. 102-115.

Voir la notice de l'article provenant de la source Math-Net.Ru

We propose a general approach to solving some vector subset problems in a Euclidean space that is based on higher-order Voronoi diagrams. In the case of a fixed space dimension, this approach allows us to find optimal solutions to these problems in polynomial time which is better than the runtime of available algorithms. Ill. 1, bibliogr. 16.
Keywords: computational geometry, vector subset problem, Euclidean space, Voronoi diagram
Mots-clés : polynomial-time algorithm. 
@article{DA_2016_23_4_a3,
     author = {V. V. Shenmaier},
     title = {Solving some vector subset problems by {Voronoi} diagrams},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {102--115},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_4_a3/}
}
TY  - JOUR
AU  - V. V. Shenmaier
TI  - Solving some vector subset problems by Voronoi diagrams
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 102
EP  - 115
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_4_a3/
LA  - ru
ID  - DA_2016_23_4_a3
ER  - 
%0 Journal Article
%A V. V. Shenmaier
%T Solving some vector subset problems by Voronoi diagrams
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 102-115
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_4_a3/
%G ru
%F DA_2016_23_4_a3
V. V. Shenmaier. Solving some vector subset problems by Voronoi diagrams. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 4, pp. 102-115. http://geodesic.mathdoc.fr/item/DA_2016_23_4_a3/

[1] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Ind. Math., 2:1 (2008), 32–38 | DOI | MR | Zbl

[2] A. E. Baburin, A. V. Pyatkin, “Polynomial algorithms for solving the vector sum problem”, J. Appl. Ind. Math., 1:3 (2007), 268–272 | DOI | MR | MR | Zbl

[3] E. Kh. Gimadi, A. V. Kel'manov, M. A. Kel'manova, S. A. Khamidullin, “A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence”, Pattern Recognit. Image Anal., 18:1 (2008), 30–42 | DOI | MR | MR | Zbl

[4] E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension”, J. Appl. Ind. Math., 4:1 (2010), 48–53 | DOI | MR | Zbl

[5] A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for solving a problem of cluster analysis”, J. Appl. Ind. Math., 5:4 (2011), 551–558 | DOI | MR | Zbl

[6] A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Tr. Inst. Mat. Mekh., 21, no. 3, 2015, 100–109 | MR

[7] A. V. Kel'manov, A. V. Pyatkin, “On a version of the problem of choosing a vector subset”, J. Appl. Ind. Math., 3:4 (2009), 447–455 | DOI | MR | Zbl

[8] A. V. Kel'manov, A. V. Pyatkin, “NP-completeness of some problems of choosing a vector subset”, J. Appl. Ind. Math., 5:3 (2011), 352–357 | DOI | MR | Zbl

[9] A. V. Kel'manov, S. M. Romanchenko, “An FPTAS for a vector subset search problem”, J. Appl. Ind. Math., 8:3 (2014), 329–336 | DOI | MR | Zbl

[10] V. V. Shenmaier, “An approximation scheme for a problem of search for a vector subset”, J. Appl. Ind. Math., 6:3 (2012), 381–386 | DOI | MR | Zbl

[11] Aggarwal A., Imai H., Katoh N., Suri S., “Finding $k$ points with minimum diameter and related problems”, J. Algorithms, 12:1 (1991), 38–56 | DOI | MR | Zbl

[12] Aronov B., Har-Peled S., “On approximating the depth and related problems”, SIAM J. Computing, 38:3 (2008), 899–921 | DOI | MR | Zbl

[13] Aurenhammer F., Klein R., “Voronoi diagrams”, Handbook of computational geometry, eds. J.-R. Sack, J. Urrutia, Elsevier, Amsterdam, 2000, 201–290 | DOI | MR

[14] Edelsbrunner H., O'Rourke J., Seidel R., “Constructing arrangements of lines and hyperplanes with applications”, SIAM J. Computing, 15:2 (1986), 341–363 | DOI | MR | Zbl

[15] Johnson D. S., Preparata F. P., “The densest hemisphere problem”, Theor. Comput. Sci., 6:1 (1978), 93–107 | DOI | MR | Zbl

[16] Shamos M. I., Hoey D., “Closest-point problems”, Proc. 16th IEEE Annu. Symp. Found. Comput. Sci. (Berkeley, Oct. 13–15, 1975), IEEE, Piscaway, 1975, 151–162 | MR