This dissertation has two topics. The rst one is about rotating a supporting hyperplane on the convex hull of a nite point set to arrive at one of its facets. We present three procedures for these rotations in multiple dimensions. The rst two procedures rotate a supporting hyperplane for the polytope starting at a lower dimensional face until the support set is a facet. These two procedures keep current points in the support set and accumulate new points after the rotations. The rst procedure uses only algebraic operations. The second procedure uses LP. In the third procedure we rotate a hyperplane on a facet of the polytope to a dierent adjacent facet. Similarly to the rst procedure, this procedure uses only algebraic operations. Some applications to these procedures include data envelopment analysis (DEA) and integer programming. The second topic is in the eld of containment problems for polyhedral sets. We present three procedures to nd a circumscribing simplex that contains a point set in any dimension. The rst two procedures are based on the supporting hyperplane rotation ideas from the rst topic. The third circumscribing simplex procedure uses polar cones and other geometrical properties to nd facets of a circumscribing simplex. One application of the second topic discussed in this dissertation is in hyperspectral unmixing.

We consider several combinatorial optimization problems in a geometric set- ting. The first problem we consider is the problem of clustering to minimize the sum of radii. Given a positive integer k and a set of points with interpoint distances that satisfy the definition of being a "metric", we define a ball centered at some input point and having some radius as the set of all input points that are at a distance smaller than the radius of the ball from its center. We want to cover all input points using at most k balls so that the sum of the radii of the balls chosen is minimized. We show that when the points lie in some Euclidean space and the distance measure is the standard Euclidean metric, we can find an exact solution in polynomial time under standard assumptions about the model of computation. The second problem we consider is the Network Spanner Topology Design problem. In this problem, given a set of nodes in the network, represented by points in some geometric setting - either a plane or a 1.5-D terrain, we want to compute a height assignment function h that assigns a height to a tower at every node such that the set of pairs of nodes that can form a direct link with each other under this height function forms a connected spanner. A pair of nodes can form a direct link if they are within a bounded distance B of each other and the heights of towers at the two nodes are sufficient to achieve Line-of-Sight connectivity - i.e. the straight line connecting the top of the towers lies above any obstacles. In the planar setting where the obstacles are modeled as having a certain maximum height and minimum clearance distance, we give a constant factor approximation algorithm. In the case where the points lie on a 1.5-D terrain we illustrate that it might be hard to use Computational Geometry to achieve efficient approximations. The final problem we consider is the Multiway Barrier Cut problem. Here, given a set of points in the plane and a set of unit disk sensors also in the plane such that any path in the plane between any pair of input points hits at least one of the given sensor disks we consider the problem of finding the minimum size subset of these disks that still achieves this separation. We give a constant factor approximation algorithm for this problem.

In this dissertation, we study several problems related to intervals and develop efficient algorithms for them. Interval problems have many applications in reality because many objects, values, and ranges are intervals in nature, such as time intervals, distances, line segments, probabilities, etc. Problems on intervals are gaining attention also because intervals are among the most basic geometric objects, and for the same reason, computational geometry techniques find useful for attacking these problems. Specifically, the problems we study in this dissertation includes the following: balanced splitting on weighted intervals, minimizing the movements of spreading points, dispersing points on intervals, multiple barrier coverage, and separating overlapped intervals on a line. We develop efficient algorithms for these problems and our results are either first known solutions or improve the previous work. In the problem of balanced splitting on weighted intervals, we are given a set of n intervals with non-negative weights on a line and an integer k ≥ 1. The goal is to find k points to partition the line into k + 1 segments, such that the maximum sum of the interval weights in these segments is minimized. We give an algorithm that solves the problem in O(n log n) time. Our second problem is on minimizing the movements of spreading points. In this problem, we are given a set of points on a line and we want to spread the points on the line so that the minimum pairwise distance of all points is no smaller than a given value δ. The objective is to minimize the maximum moving distance of all points. We solve the problem in O(n) time. We also solve the cycle version of the problem in linear time. For the third problem, we are given a set of n non-overlapping intervals on a line and we want to place a point on each interval so that the minimum pairwise distance of all points are maximized. We present an O(n) time algorithm for the problem. We also solve its cycle version in O(n) time. The fourth problem is on multiple barrier coverage, where we are given n sensors in the plane and m barriers (represented by intervals) on a line. The goal is to move the sensors onto the line to cover all the barriers such that the maximum moving distance of all sensors is minimized. Our algorithm for the problem runs in O(n2 log n log log n + nm log m) time. In a special case where the sensors are all initially on the line, our algorithm runs in O((n + m) log(n + m)) time. Finally, for the problem of separating overlapped intervals, we have a set of n intervals (possibly overlapped) on a line and we want to move them along the line so that no two intervals properly intersect. The objective is to minimize the maximum moving distance of all intervals. We propose an O(n log n) time algorithm for the problem. The algorithms and techniques developed in this dissertation are quite basic and fundamental, so they might be useful for solving other related problems on intervals as well.

We study the complexity of finding so called spanner paths between arbitrary nodes in Euclidean graphs. We study both general Euclidean graphs and a special type of graphs called Integer Graphs. The problem is proven NP-complete for general Euclidean graphs with non-constant stretches (e.g. (2n)^(3/2) where n denotes the number of nodes in the graph). An algorithm solving the problem in O(2^(0.822n)) is presented. Integer graphs are simpler and for these special cases a better algorithm is presented. By using a partial order of so called Images the algorithm solves the spanner path problem using O(2^(c(\log n)^2)) time, where c is a constant depending only on the stretch.

Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.

The results of this thesis concern folding of one-dimensional objects in two dimensions: planar linkages. More precisely, a planar linkage consists of a collection of rigid bars (line segments) connected at their endpoints. Foldings of such a linkage must preserve the connections at endpoints, preserve the bar lengths, and (in our context) prevent bars from crossing. The main result of this thesis is that a planar linkage forming a collection of polygonal arcs and cycles can be folded so that all outermost arcs (not enclosed by other cycles) become straight and all outermost cycles become convex. A complementary result of this thesis is that once a cycle becomes convex, it can be folded into any other convex cycle with the same counterclockwise sequence of bar lengths. Together, these results show that the configuration space of all possible foldings of a planar arc or cycle linkage is connected. These results fall into the broader context of folding and unfolding <I>k</I>-dimensional objects in <i>n</i>-dimensional space, <I>k</I> less than or equal to <I>n</I>. Another contribution of this thesis is a survey of research in this field. The survey revolves around three principal aspects that have received extensive study: linkages in arbitrary dimensions (folding one-dimensional objects in two or more dimensions, including protein folding), paper folding (normally, folding two-dimensional objects in three dimensions), and folding and unfolding polyhedra (two-dimensional objects embedded in three-dimensional space).

This thesis examines the (geometric) Steiner tree problem: Given a set of points P in the plane, find a shortest tree interconnecting all points in P, with the possibility of adding points outside P, called the Steiner points, as additional vertices of the tree. The Steiner tree problem has been studied in different metric spaces. In this thesis, we study the problem in Euclidean and rectilinear metrics. One of the most natural heuristics for the Steiner tree problem is to use a minimum spanning tree, which can be found in O(nlogn) time . The performance ratio of this heuristic is given by the Steiner ratio, which is defined as the minimum possible ratio between the lengths of a minimum Steiner tree and a minimum spanning tree. We survey the background literature on the Steiner ratio and study the generalization of the Steiner ratio to the case of obstacles. We introduce the concept of an anchored Steiner tree: an obstacle-avoiding Steiner tree in which the Steiner points are only allowed at obstacle corners. We define the obstacle-avoiding Steiner ratio as the ratio of the length of an obstacle-avoiding minimum Steiner tree to that of an anchored obstacle-avoiding minimum Steiner tree. We prove that, for the rectilinear metric, the obstacle-avoiding Steiner ratio is equal to the traditional (obstacle-free) Steiner ratio. We conjecture that this is also the case for the Euclidean metric and we prove this conjecture for three points and any number of obstacles.

The results of this thesis concern folding of one-dimensional objects in two dimensions: planar linkages. More precisely, a planar linkage consists of a collection of rigid bars (line segments) connected at their endpoints. Foldings of such a linkage must preserve the connections at endpoints, preserve the bar lengths, and (in our context) prevent bars from crossing. The main result of this thesis is that a planar linkage forming a collection of polygonal arcs and cycles can be folded so that all outermost arcs (not enclosed by other cycles) become straight and all outermost cycles become convex. A complementary result of this thesis is that once a cycle becomes convex, it can be folded into any other convex cycle with the same counterclockwise sequence of bar lengths. Together, these results show that the configuration space of all possible foldings of a planar arc or cycle linkage is connected. These results fall into the broader context of folding and unfolding <I>k</I>-dimensional objects in <i>n</i>-dimensional space, <I>k</I> less than or equal to <I>n</I>. Another contribution of this thesis is a survey of research in this field. The survey revolves around three principal aspects that have received extensive study: linkages in arbitrary dimensions (folding one-dimensional objects in two or more dimensions, including protein folding), paper folding (normally, folding two-dimensional objects in three dimensions), and folding and unfolding polyhedra (two-dimensional objects embedded in three-dimensional space).

This thesis examines the (geometric) Steiner tree problem: Given a set of points P in the plane, find a shortest tree interconnecting all points in P, with the possibility of adding points outside P, called the Steiner points, as additional vertices of the tree. The Steiner tree problem has been studied in different metric spaces. In this thesis, we study the problem in Euclidean and rectilinear metrics. One of the most natural heuristics for the Steiner tree problem is to use a minimum spanning tree, which can be found in O(nlogn) time . The performance ratio of this heuristic is given by the Steiner ratio, which is defined as the minimum possible ratio between the lengths of a minimum Steiner tree and a minimum spanning tree. We survey the background literature on the Steiner ratio and study the generalization of the Steiner ratio to the case of obstacles. We introduce the concept of an anchored Steiner tree: an obstacle-avoiding Steiner tree in which the Steiner points are only allowed at obstacle corners. We define the obstacle-avoiding Steiner ratio as the ratio of the length of an obstacle-avoiding minimum Steiner tree to that of an anchored obstacle-avoiding minimum Steiner tree. We prove that, for the rectilinear metric, the obstacle-avoiding Steiner ratio is equal to the traditional (obstacle-free) Steiner ratio. We conjecture that this is also the case for the Euclidean metric and we prove this conjecture for three points and any number of obstacles.

Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.