| Consider two sets of points in the two- or three-dimensional space, namely, a set R of n "red" points and a set B of m "blue" points. A separator of the point sets R and B is a geometric locus enclosing all red points, that contains the fewest possible blue points. In this dissertation, we study the separability of these two point sets using various separators, such as circles, axis-aligned rectangles, or arbitrarily oriented rectangles. If there are an infinity of separators, we consider optimum criteria such as minimizing the radius (for circles) and maximizing the area (for rectangles). We first give an overview of computational geometry and the work related to geometric separability. Then, we study the circular separation problem and present three dynamic data structures that allow insertions and deletions of blue points, as well as reporting an optimal circle after such an insertion or deletion. The first is a unified data structure that supports both insertions and deletions and has nearlinear query and update time. The other two data structure have logarithmic query time and near-quadratic update time. One of them allows only insertions and the other supports only deletions of blue points. These are the first algorithms for the dynamic circular separation problem. After that, we introduce the rectangular separation problem and focus on the axis-aligned case (that is, the target rectangle has to be axis-aligned). We prove that the number of optimal solutions can be O(m) in the worst case, present an algorithm to find one optimal solution that has near-linear running time, and then prove a matching lower bound for finding one optimal solution. We also introduce a number of extensions of the rectangular separation problem. Specifically, we consider the case when a fixed number of blue points are allowed inside the separating rectangle and the case where the blue points are replaced by axis-aligned rectangles. Finally, we conclude by discussing the on-going work and give possible future directions for geometric separability. |
