On the Geometric Separability of Bichromatic Point Sets

dc.contributor.VIAF172508805 (Daescu, O)
dc.contributor.advisorDaescu, Ovidiu
dc.creatorArmaselu, Bogdan Andrei
dc.date.accessioned2017-08-29T16:11:49Z
dc.date.available2017-08-29T16:11:49Z
dc.date.created2017-08
dc.date.issued2017-08
dc.date.submittedAugust 2017
dc.date.updated2017-08-29T16:11:49Z
dc.description.abstractConsider 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 (n) 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.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/10735.1/5474
dc.language.isoen
dc.subjectVoronoi polygons
dc.subjectPoint set theory
dc.subjectData structures (Computer science)
dc.titleOn the Geometric Separability of Bichromatic Point Sets
dc.typeDissertation
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.grantorUniversity of Texas at Dallas
thesis.degree.levelDoctoral
thesis.degree.namePHD

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ETD-5608-7434.11.pdf
Size:
2.25 MB
Format:
Adobe Portable Document Format
Description:

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
5.84 KB
Format:
Plain Text
Description: