
On the Geometric Separability of Bichromatic Point Sets 
Author(s): 
Armaselu, Bogdan Andrei 

Daescu, Ovidiu 

201708 

Dissertation 
Keywords:  Voronoi polygons Point set theory Data structures (Computer science) 

Consider two sets of points in the two or threedimensional 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, axisaligned 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 nearquadratic 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 axisaligned case (that is, the target rectangle has to be axisaligned). We prove that the number of optimal solutions can be (n) in the worst case, present an algorithm to find one optimal solution that has nearlinear 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 axisaligned rectangles. Finally, we conclude by discussing the ongoing work and give possible future directions for geometric separability. 

PHD 

Doctoral 

http://hdl.handle.net/10735.1/5474 

text 

Computer Science 
Files  Size  Format  View 

ETD56087434.11.pdf  2.252Mb 
View/ 