Advertisement
Published in:
2015 | OriginalPaper | Chapter
Dynamic Minimum Bichromatic Separating Circle
Authors : Bogdan Armaselu, Ovidiu Daescu
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In the Minimum Bichromatic Separating Circle problem, we are given a set of n red points R and a set of m blue points B, and we want to find the smallest circle C that contains all red points and the smallest possible number of blue points. In this paper we study the Dynamic Minimum Bichromatic Separating Circle and present data structures that allow to perform efficient dynamic operations on the input points, specifically for adding and removing blue points. We first present a unified data structure that allows both additions and deletions. Then, we present data structures that allow to report an optimal circle in logarithmic time when only insertions are allowed, at the expense of an increase in update time. Our results are the first known for the Dynamic Minimum Bichromatic Separating Circle problem.