Range assignment of base-stations maximizing coverage area without interference

DOI10.1016/J.TCS.2019.10.044MaRDI QIDQ2283033zbMATH OpenOpenAlexWikidataFDO

Authors Ankush Acharyya, Minati De, Subhas C. Nandy, Bodhayan Roy

Publication date 27 December 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.09346

zbMATH Keywords

approximation algorithmdiscrete packingNP-hardnessPTASquadratic programmingrange assignment in wireless communication

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Quadratic programming (90C20)

Abstract: We study the problem of assigning non-overlapping geometric objects centered at a given set of points such that the sum of area covered by them is maximized. If the points are placed on a straight-line and the objects are disks, then the problem is solvable in polynomial time. However, we show that the problem is NP-hard even for simplest objects like disks or squares in ${mathbbR}^2$. Eppstein [CCCG, pages 260--265, 2016] proposed a polynomial time algorithm for maximizing the sum of radii (or perimeter) of non-overlapping balls or disks when the points are arbitrarily placed on a plane. We show that Eppstein's algorithm for maximizing sum of perimeter of the disks in ${mathbbR}^2$ gives a $2$-approximation solution for the sum of area maximization problem. We propose a PTAS for our problem. These approximation results are extendible to higher dimensions. All these approximation results hold for the area maximization problem by regular convex polygons with even number of edges centered at the given points.

Recommendations

• scientific article; zbMATH DE number 2089212
• Polynomial time approximation schemes for base station coverage with minimum total radii
• VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION
• Distributed Computing – IWDC 2005
• An algorithm for maximising covered area

Cites work

• Approximation algorithms for quadratic programming
• Approximation schemes for covering and packing problems in image processing and VLSI
• Faster algorithms for some optimization problems on collinear points
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Maximizing the sum of radii of disjoint balls or disks
• Optimal binary space partitions in the plane
• Packing and covering with linear programming: a survey
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Quadratic programming with one negative eigenvalue is NP-hard
• The polynomial solvability of convex quadratic programming
• Towards a Genuinely Polynomial Algorithm for Linear Programming
• Über die dichteste Kugellagerung

Cited in

(5)

• scientific article; zbMATH DE number 2089212 (Why is no real title available?)
• An algorithm for maximising covered area
• Faster algorithms for some optimization problems on collinear points
• Dynamic Partitioning and Coverage Control With Asynchronous One-to-Base-Station Communication
• On a geometric graph-covering problem related to optimal safety-landing-site location

This page was built for publication: Range assignment of base-stations maximizing coverage area without interference

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2283033)