ENRU
English version: Journal of Applied and Industrial Mathematics, 2016, 10:4, 560566 

Volume 23, No 4, 2016, P. 102115 UDC 519.176
Keywords: computational geometry, vector subset problem, Euclidean space, Voronoi diagram, polynomialtime algorithm. DOI: 10.17377/daio.2016.23.526 Vladimir V. Shenmaier ^{1} Received 20 May 2016 References[1] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, The problem of finding a subset of vectors with the maximum total weight, Diskretn. Anal. Issled. Oper., Ser. 2, 14, No. 1, 32–42, 2007. Translated inJ. Appl. Ind. Math., 2, No. 1, 32–38, 2008. [2] A. E. Baburin and A. V. Pyatkin, Polynomial algorithms for solving the vector sum problem, Diskretn. Anal. Issled. Oper., Ser. 1, 13, No. 2, 3–10, 2006. Translated in J. Appl. Ind. Math., 1, No. 3, 268–272, 2007. [3] E. Kh. Gimadi, A. V. Kel’manov, M. A. Kel’manova, and S. A. Khamidullin, A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence, Sib. Zh. Ind. Mat., 9, No. 1, 55–74, 2006. Translated in Pattern Recognit. Image Anal., 18, No. 1, 30–42, 2008. [4] E. Kh. Gimadi, A. V. Pyatkin, and I. A. Rykov, On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension, Diskretn. Anal. Issled. Oper., 15, No. 6, 11–19, 2008. Translated in J. Appl. Ind. Math., 4, No. 1, 48–53, 2010. [5] A. V. Dolgushev and A. V. Kel’manov, An approximation algorithm for solving a problem of cluster analysis, Diskretn. Anal. Issled. Oper., 18, No. 2, 29–40, 2011. Translated in J. Appl. Ind. Math., 5, No. 4, 551–558, 2011. [6] A. V. Dolgushev, A. V. Kel’manov, and V. V. Shenmaier, Polynomialtime approximation scheme for a problem of partitioning a finite set into two clusters, Tr. Inst. Mat. Mekh., 21, No. 3, 100–109, 2015. [7] A. V. Kel’manov and A. V. Pyatkin, On a version of the problem of choosing a vector subset, Diskretn. Anal. Issled. Oper., 15, No. 5, 20–34, 2008. Translated in J. Appl. Ind. Math., 3, No. 4, 447–455, 2009. [8] A. V. Kel’manov and A. V. Pyatkin, NPcompleteness of some problems of choosing a vector subset, Diskretn. Anal. Issled. Oper., 17, No. 5, 37–45, 2010. Translated in J. Appl. Ind. Math., 5, No. 3, 352–357, 2011. [9] A. V. Kel’manov and S. M. Romanchenko, An FPTAS for a vector subset search problem, Diskretn. Anal. Issled. Oper., 21, No. 3, 41–52, 2014. Translated in J. Appl. Ind. Math., 8, No. 3, 329–336, 2014. [10] V. V. Shenmaier, An approximation scheme for a problem of search for a vector subset, Diskretn. Anal. Issled. Oper., 19, No. 2, 92–100, 2012. Translated in J. Appl. Ind. Math., 6, No. 3, 381–386, 2012. [11] A. Aggarwal, H. Imai, N. Katoh, and S. Suri, Finding k points with minimum diameter and related problems, J. Algorithms, 12, No. 1, 38–56, 1991. [12] B. Aronov and S. HarPeled, On approximating the depth and related problems, SIAM J. Comput., 38, No. 3, 899–921, 2008. [13] F. Aurenhammer and R. Klein, Voronoi diagrams, in J.R. Sack and J. Urrutia, eds., Handbook of Computational Geometry, pp. 201–290, Elsevier, Amsterdam, 2000. [14] H. Edelsbrunner, J. O’Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, No. 2, 341–363, 1986. [15] D. S. Johnson and F. P. Preparata, The densest hemisphere problem, Theor. Comput. Sci., 6, No. 1, 93–107, 1978. [16] M. I. Shamos and D. Hoey, Closestpoint problems, in Proc. 16th IEEE Annu. Symp. Found. Comput. Sci., Berkeley, USA, Oct. 13–15, 1975, pp. 151–162, IEEE, Piscataway, 1975. 

© Sobolev Institute of Mathematics, 2015  