Geometric Facility Location Optimization
Thesis submitted in fulfillmentof the requirements for the degree of
“DOCTOR OF PHILOSOPHY”
by: Boaz Ben-Moshe
advisor: Prof. Matthew J. Katz
April 13, 2005Beer-Sheva
Abstract
This thesis is in Computational Geometry. Computational Geometryis a subfield of Computer Science that deals with problems of ageometric nature that arise in application domains such asComputer Graphics, Robotics, Geographic Information Systems(GIS), and Molecular Biology.More specifically, in this thesis we conduct research inComputational Geometry in the context of (Geometric) FacilityLocation problems, where the goal is to position sites overgeometric models. Facility Location Optimization is a classical research area inOperations Research, in which problems dealing with the “best” location of different types of facilities in various settings andunder various constraints are studied. With plenty of practicalmotivations, geometric instances of facility location problems have attracted researchers from the Computational Geometrycommunity, especially in the last few years. ComputationalGeometry deals with the efficient processing of spatial data and with geometric optimization, and thus techniques, algorithms, anddata structures from this field can be effectively utilized forsolving these instances.
In general, the input to a facility location problem includes a weighted set D of demand locations, a set F of feasiblefacility locations, and a distance function (d) that measures thecost of travel between a pair of locations. In geometricinstances of facility location problems, the sets D and F areusually modeled as sets of points in some geometric space, e.g.,R2, R3, or a (polyhedral) terrain, and distancesare measured according to the Euclidean (L2) or Manhattan(L1) metric.
Main problems and results
In Chapter 2, the problem of computing (approximately) thevisible region from a point on a terrain is studied. A newalgorithm is presented for this problem, thisalgorithm 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 thecomplexity of the terrain, while attempting to maintain thevisibility properties of the original terrain. A comparisonbetween VPTS and several other known terrain simplificationmethods 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 isminimized, is considered. A new improved algorithm is presentedfor this problem.
In Chapter 5, we consider a more general version of the1.5D-terrain guarding problem. In this version we need to place asfew as possible guards on the terrain so that each point of theterrain is seen by at least one of the guards. A constant-factor approximation algorithm is presented for thisproblem.
In Chapter 6, the problem of efficiently computing the visibility graph of a set of points within a 2D polygon isstudied, this problem is closely related topolygon guarding problems.
In Chapter 7, a facility location expert system is described, thatwas developed and implemented as part of our role in the LSRTMAGNET consortium. This system employs some of the algorithmsabove as well as some additional heuristics, in order to allow auser to design and optimize the layout of large wireless networks.
Key words:computational geometry, facility location, optimization,approximation algorithms, visibility, visibility graphs,terrains, terrain simplification, guarding problems, wireless networks.