Geometric Facility Location Optimization Thesis
Boaz Ben Moshe · 2005
This thesis is in Computational Geometry. Computational Geometry is a subfield of Computer Science that deals with problems of a geometric nature that arise in application domains such as Computer Graphics, Robotics, Geographic Information Systems (GIS), and Molecular Biology. More specifically, in this thesis we conduct research in Computational Geometry in the context of (Geometric) Facility Location problems, where the goal is to position sites over geometric models. Facility Location Optimization is a classical research area in Operations Research, in which problems dealing with the “best” location of different types of facilities in various settings and under various constraints are studied. With plenty of practical motivations, geometric instances of facility location problems have attracted researchers from the Computational Geometry community, especially in the last few years. Computational Geometry deals with the efficient processing of spatial data and with geometric optimization, and thus techniques, algorithms, and data structures from this field can be effectively utilized for solving these instances. In general, the input to a facility location problem includes a weighted set D of demand locations, a set F of feasible facility locations, and a distance function d that measures the cost of travel between a pair of locations. In geometric instances of facility location problems, the sets D and F are usually modeled as sets of points in some geometric space, e.g., R2, R3, or a (polyhedral) terrain, and distances are measured according to the Euclidean (L2) or Manhattan (L1) metric. Main problems and results. In Chapter 2, the problem of computing (approximately) the visible region from a point on a terrain is studied. A new algorithm is presented for this problem, this algorithm is then compared with other (known) algorithms. In Chapter 3, the problem of visibility preserving terrain simplification is introduced. An approximation algorithm (VPTS) is presented, this algorithm reduces the complexity of the terrain, while attempting to maintain the visibility properties of the original terrain. A comparison between VPTS and several other known terrain simplification methods is performed. In Chapter 4, the problem of guarding a 1.5D-terrain (an x-monotone chain of line-segments in the plane) using two watchtowers, such that the height of the higher of the two is minimized, is considered. A new improved algorithm is presented for this problem. In Chapter 5, we consider a more general version of the 1.5D-terrain guarding problem. In this version we need to place as few as possible guards on the terrain so that each point of the terrain is seen by at least one of the guards. A constant-factor approximation algorithm is presented for this problem. In Chapter 6, the problem of efficiently computing the visibility graph of a set of points within a 2D polygon is studied, this problem is closely related to polygon guarding problems. In Chapter 7, a facility location expert system is described, that was developed and implemented as part of our role in the LSRT MAGNET consortium. This system employs some of the algorithms above as well as some additional