RUS  ENG
Full version
JOURNALS // Avtomatika i Telemekhanika // Archive

Avtomat. i Telemekh., 2020 Issue 5, Pages 139–155 (Mi at15488)

Topical issue

Geometric algorithms for finding a point in the intersection of balls

I. N. Lushchakova

Belarusian State University of Informatics and Radioelectronics, Minsk, Belarus

Abstract: We consider a problem of finding a point in the intersection of $n$ balls in the Euclidean space $E^m$. For the case $m=2$ we suggest two algorithms of the complexity $O(n^2\log n)$ and $O(n^3)$ operations, respectively. For the general case we suggest an exact polynomial recursive algorithm which uses the orthogonal transformation of the space $E^m$.

Keywords: intersection of balls, approximation a convex set by ellipsoids, polynomial algorithm, delivery applications of drones, configuration of the swarm of drones.

Presented by the member of Editorial Board: A. A. Lazarev

Received: 18.07.2019
Revised: 15.09.2019
Accepted: 28.11.2019

DOI: 10.31857/S0005231020050098


 English version:
Automation and Remote Control, 2020, 81:5, 869–882

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024