EN|RU
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 in
J. 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.
 © Sobolev Institute of Mathematics, 2015