About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:4, 560-566
Volume 23, No 4, 2016, P. 102-115
UDC 519.176
V. V. Shenmaier
Solving some vector subset problems by Voronoi diagrams
Abstract:
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, polynomial-time algorithm.
DOI: 10.17377/daio.2016.23.526
Vladimir V. Shenmaier 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: shenmaier@mail.ru
Received 20 May 2016
Revised 15 June 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, NP-completeness 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. Har-Peled, 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, Closest-point problems, in Proc. 16th IEEE Annu. Symp. Found. Comput. Sci., Berkeley, USA, Oct. 13–15, 1975, pp. 151–162, IEEE, Piscataway, 1975.
