Solving some vector subset problems by Voronoi diagrams
- Authors: Shenmaier V.V.1
-
Affiliations:
- Sobolev Institute of Mathematics
- Issue: Vol 10, No 4 (2016)
- Pages: 560-566
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212555
- DOI: https://doi.org/10.1134/S199047891604013X
- ID: 212555
Cite item
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.
About the authors
V. V. Shenmaier
Sobolev Institute of Mathematics
Author for correspondence.
Email: shenmaier@mail.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090