Search

Cellular communications has experienced an explosive growth recently. In order to increase the capacity of a cellular network without new frequency spectrum allocation, it is a common practice to use base stations with a lower power transmitter. Cell splitting is one of such techniques, which increases the network capacity four-fold by dividing a cell into four smaller cells. Although the cell splitting technique can reuse the existing base stations, it requires that those existing base stations be uniformly distributed. In addition, the radius of each new cell is always half that of the original cell. In this paper, it is assumed that the radius of new cells can be of any smaller size, and that the existing base stations are not necessarily uniformly distributed. While new base stations can be placed at the cell centers based on the design of the new cellular network, existing base stations should be put as close to a cell center as possible in the new cellular network. The problem to be solved, referred to as the optimal cellular network deployment, can be formulated as follows: given a set of existing base stations and a planned cellular network that has a fixed cell size and network orientation but is movable, find a position to fix the movable cellular network such that the maximum distance between existing base stations and their corresponding cell centers is minimized. This paper shows that the optimal cellular network deployment problem can be solved in O(n3) time if n existing base stations will be reused.

In geometric covering problems, the aim is to cover a set of given points using a minimum number of shapes with prescribed properties. These problems extend in many ways such as covering in the presence of obstacles and partial covering. Since in most cases these problems are NP-hard, researchers have developed a large number of approximation algorithms to solve them. In this paper, with a more general view on these approaches, we propose an algorithmic framework that gives an approximation algorithm for the covering problem at hand, provided that its prerequisites are satisfied. As the result, we present a general class of geometric covering problems for which one can obtain polynomial-time approximation schemes (PTASs). This class of problems involves covering point sets with bounded shapes in a space with fixed dimension. For a problem to be in this class, it must be possible to find a polynomial number of maximal shapes and it must be possible to cover all the points in a small box with a small number of shapes. Using this framework, we present two new PTASs for the problems of covering with disks in the presence of polygonal obstacles and covering with sectors (pie-shaped wedges). The first problem has never been addressed before and for the second problem, only a logarithmic approximation algorithm was known in general and a 9-approximation algorithm for wide angles.

In this paper, we present techniques and algorithms for processing an offline sequence of update and query operations and for related problems. The update can be either all insertions or all deletions. The types of query include min-gap, max-gap, predecessor, and successor. Most problems we consider are solved optimally in linear time by our algorithms, which are based on new geometric modeling and interesting techniques. We also discuss some applications to which our algorithms and techniques can be applied to yield efficient solutions. These applications include an offline horizontal ray shooting problem and a shortest arc covering problem on a circle.