Overview
In this project we have implemented of an example of Bichromatic data structures i.e, smallest enclosed circle problem. A large set of points which can take any of the two types of colours is given and as a result we would form a circle which covers maximum number of points of the same colour in the same plane.
Requirements
The Computational Geometry Algorithms Library (CGAL).
pip3 install cgal-bindings
Research Papers referred
- Aritra Banik, E.M. Arkin, M.J. Katz, J.S. Mitchell, P. Carmi, “Conflict-free covering”, CCCG 2015, Kingston.
- Steven Bitner, Yam Cheung, Ovidiu Daescu, “Minimum separating circle for bichromatic points in the plane”, University of Texas at Dallas.
- CGAL Bounding volumes library manual, “http://doc.cgal.org/latest/Bounding_volumes/index.html”
Possible applications using this concept
- Communication Jamming
- Minimizing Civilian casualities
- Data set seperation
Algorithm time complexity
O(m(n+m)log(n+m))
where, m = Size of red data points, and n = Size of blue data points
Additional Algorithms insights
- Farther Neighbour Voronoi Diagram
- Largest Seperating Circle