Proximity problems in two and three dimensional Euclidean space .

摘要

In this dissertation we consider three problems in computational geometry. We begin with an overview of computational geometry and some background knowledge. We discuss several important data structures as well as briefly summarize the known results for finding the data structures discussed. Next, we give a solution for the farthest line segment problem. Given a set S of n points in R3 , we give an algorithm which will return the farthest line segment spanned by S from an input query point in O( n log n) time. This time is optimal in the algebraic decision tree model.;Then we address the minimum sum dipolar spanning tree (MSST) problem in R3 . This problem seeks to find two congruent balls centered at two points in the input set S such that the sum of the distance between their centers and the radius of the balls is minimized. These balls must cover the set S to be valid solutions. We give an O( n2 log2 n) time and O(n2) space algorithm which adds only a logarithmic factor to the two dimensional version. Our algorithm can also return a solution to the discrete 2-center problem without an addition to the asymptotic running time. This running time outperforms the speed of the best known algorithm for the continuous 2-center problem in R3 .;Finally, we give solutions to a new problem which we refer to as the bichromatic circular separation problem. Given two sets of points in R2 , one red and one blue, the problem is to find the minimum size circle such that all red points are in the interior of the circle and as few blue points as possible lie inside the same circle. We offer three solutions, two of which run in O(nm log m + n log n) time and use linear space. The third algorithm runs in O*(m 1.5) + O(m log n) time and uses O(n) + O(m1.5) space. The O*() notation ignores a polylogarithmic factor.;We conclude with a look at our ongoing work and some partial results that have been motivated by the work contained in this dissertation.