Upravlenie Bol'shimi Sistemami
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



UBS:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


UBS, 2019, Issue 81, Pages 6–25 (Mi ubs1015)  

This article is cited in 1 scientific paper (total in 1 paper)

Systems Analysis

On multiple coverings and packings problems in a two-dimensional non-Euclidean space

A. L. Kazakova, A. A. Lemperta, Q. M. Leb

a Matrosov Institute for System Dynamics and Control Theory of SB RAS, Irkutsk
b Irkutsk National Research Technical University (Baikal School of BRICS), Irkutsk

Abstract: The article is devoted to the study of two significant problems of computational geometry. The first one is the multiple circle covering problem for a closed bounded set in a two-dimensional metric space, and the second one is the multiple circle packing problem. In the first case, the objective is to minimize the radius of the circles, in the second one is to maximize it. In both cases, the number of circles k is given. The considered metric is generally non-Euclidean. The source of such a statement is tasks from transport logistics, where the distance between objects is necessary to be replaced with a minimum time to travel between them. And optimum is not always achieved with straight line moving due to the terrain or urban features. We propose computational algorithms to solve these problems. They include the joint use of an optical-geometric approach based on the principles of Fermat and Huygens and the $K$-means method. The key step is to construct a generalized $k$-order Voronoi diagram. Each Voronoi cell with a fixed set of $n$ centroids includes points, which are closer to some $k$ centroids than to the remaining $n-k$. The cells can intersect each other. Computational experiments are carried out.

Keywords: multiple packing, equal circles, non-Euclidean metric, algorithm, Voronoi–Dirichlet diagram, Fermat and Huygens principles

Funding Agency Grant Number
Russian Foundation for Basic Research 18-07-00604


DOI: https://doi.org/10.25728/ubs.2019.81.1

Full text: PDF file (2179 kB)
References: PDF file   HTML file

UDC: 514.174.2
BBK: 22.19
Received: July 19, 2019
Published: September 30, 2019

Citation: A. L. Kazakov, A. A. Lempert, Q. M. Le, “On multiple coverings and packings problems in a two-dimensional non-Euclidean space”, UBS, 81 (2019), 6–25

Citation in format AMSBIB
\Bibitem{KazLemLe19}
\by A.~L.~Kazakov, A.~A.~Lempert, Q.~M.~Le
\paper On multiple coverings and packings problems in a two-dimensional non-Euclidean space
\jour UBS
\yr 2019
\vol 81
\pages 6--25
\mathnet{http://mi.mathnet.ru/ubs1015}
\crossref{https://doi.org/10.25728/ubs.2019.81.1}


Linking options:
  • http://mi.mathnet.ru/eng/ubs1015
  • http://mi.mathnet.ru/eng/ubs/v81/p6

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. L. Kazakov, A. A. Lempert, Ch. T. Ta, “O zadachakh upakovok neravnykh sharov v trekhmernom prostranstve”, UBS, 87 (2020), 47–66  mathnet  crossref
  • Upravlenie Bol'shimi Sistemami
    Number of views:
    This page:100
    Full text:32
    References:3

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022