# Releasing the CRaQAn (Coreference Resolution in Question-Answering): An
open-source dataset and dataset creation methodology using instruction-
following models

Rob Grzywinski
Pyxos, Inc. Joshua D’Arcy, MD11footnotemark: 1
Edge Analytics, Inc. Rob Naidoff
Pyxos, Inc. Ashish Shukla
Pyxos, Inc. Alex Browne
Edge Analytics, Inc. Ren Gibbons
Edge Analytics, Inc. Brinnae Bent, PhD
Edge Analytics, Inc These authors contributed equally to this work.

###### Abstract

Instruction-following language models demand robust methodologies for
information retrieval to augment instructions for question-answering
applications. A primary challenge is the resolution of coreferences in the
context of chunking strategies for long documents. The critical barrier to
experimentation of handling coreferences is a lack of open source datasets,
specifically in question-answering tasks that require coreference resolution.
In this work we present our Coreference Resolution in Question-Answering
(CRaQAn) dataset, an open-source dataset that caters to the nuanced
information retrieval requirements of coreference resolution in question-
answering tasks by providing over 250 question-answer pairs containing
coreferences. To develop this dataset, we developed a novel approach for
creating high-quality datasets using an instruction-following model (GPT-4)
and a Recursive Criticism and Improvement Loop.

##  1 Introduction

Information retrieval (IR) is a fundamental component in many applications of
instruction-following models providing ground truth text from a corpus of
documents. Long documents pose an issue for embedding-based information
retrieval, because state-of-the-art embedding models have a limited context
window length [1]. A common practice is to store embedded chunks of a long
document in a vector database, which then enables targeted information
retrieval [2]. Chunking refers to the process of dividing a long document into
smaller, more manageable pieces or chunks.

However, naive chunking strategies for long documents may inadvertently split
a coreference sequence, altering the semantic context of the individual chunks
[3]. Coreference sequences pertain to instances in a text where different
expressions link to the same entity, like a person or object. For instance,
consider the sentence "Mary planted a tree in her backyard because she loves
nature". In this case, "Mary" and "she" are coreferent. If a chunking strategy
splits this sentence into two chunks - "Mary planted a tree in her backyard"
and "because she loves nature" - the reference to "she" in the second chunk
becomes unclear without the context provided by the first chunk. Even more
challenging is the scenario where coreferences span several paragraphs or even
pages [4]. This greatly amplifies the complexity of maintaining semantic
integrity when chunking, as spatially distant coreferences could easily be
disrupted with common chunking strategies, leading to potential loss of
critical contextual information.

We posit that for every information retrieval task, there needs to be a
balance between preservation of long-range coreferences and chunk size, where
the latter might be limited by the embedding model architecture [5] or diluted
contextual meaning [1]. Our motivation for this body of work is to generate a
dataset necessitating coreference resolution across both contiguous and widely
separated sentences for accurate question-answering (QA). This dataset can be
used to test various chunking strategies for information retrieval in a QA
pipeline.

Manual creation of such a dataset would be labor-intensive, time-consuming,
and subject to significant human error through crowdsourcing. To alleviate
these concerns, we propose and demonstrate an approach to automated dataset
creation leveraging the advanced capabilities of GPT-4, a state-of-the-art
instruction-following model developed by OpenAI [6] and a Recursive Criticism
and Improvement loop (RCI) [7].

In this paper, we introduce the Coreference Resolution in Question-Answering
(CRaQAn) open-source dataset, alongside a scalable methodology for automated
dataset creation that leverages instruction-following models. These
contributions not only provide a tool for enhancing the robustness and
effectiveness of QA systems but also establish a new approach for accelerating
and refining dataset generation in the broader natural language processing
research community.

##  2 Related Work

###  2.1 Coreference Resolution and Question-Answering Datasets

There are many open-source datasets individually focused on coreference
resolution [8, 9, 10] or QA of passages [11, 12, 13]. However, to our
knowledge, there exists only one open-source dataset (Quoref, from Dasigi et
al., [14]) that contains question-answer pairs that require coreference
resolution within a single document to answer. However, Quoref’s reliance on
crowdsourcing has its limitations, including inconsistencies in the quality
and relevance of the coreference resolution required by the QA pairs [14].
Furthermore, there is no requirement for coreferences to exist across
sentences, meaning certain chunking strategies, such as by sentence, cannot be
assessed using the Quoref dataset. HotpotQA is another popular open-source
dataset for coreference resolution and question-answering. HotpotQA relies on
multiple-document hopping for its coreferences [15], which does not allow for
the assessment of single-document chunking strategies.

###  2.2 Automatic Question Generation

Automated dataset creation methodologies have been increasingly explored to
overcome the limitations of manual and crowdsourced data collection. Automatic
question generation (AQG) is one subset of this space that has grown in
popularity. A number of traditional approaches to AQG exist. Utilization of
language models, and specifically transformers, for QA generation is becoming
increasingly common [16, 17]. However, these methods rely on previously
labeled datasets and are not trained to provide complex question-answer pairs,
such as the ones desired in this study for coreferences [18, 19, 20]. Using
instruction-following models like large language models (LLMs) is a relatively
new strategy that researchers are beginning to explore for more complex AQG
tasks [21, 22].

###  2.3 Recursive Criticism and Improvement Loop

Kim et al. coined the term "RCI" for their prompting scheme approach in which
a model Recursively Criticizes and Improves its output [7]. We build on this
work by applying it to dataset creation and combining it with other techniques
such as memetic proxies [23], few-shot prompting [6], Chain-of-Thought [24],
and Show-Your-Work reasoning [25]. Our approach leverages the iterative
feedback process to refine and improve the quality of the generated data.

##  3 Methods

###  3.1 Automated Approach for Natural Language Dataset Generation with
Instruction-following Models and a Recursive Criticism and Improvement Loop

Our primary objective is to develop a framework for automated generation of
high-quality natural language datasets consisting of question-answer pairs
relating to a passage using an instruction-following model, GPT-4. To achieve
this, we establish a set of logical rules for the dataset and utilize a
GENERATOR to suggest candidate dataset entries. The GENERATOR is designed to
respond iteratively to feedback from a REVIEWER panel, ensuring a continuous
improvement in the quality of generated entries.

We developed a set of comprehensive guidelines used in both prompting and
instructions for human reviewers. Development of these guidelines was an
iterative process wherein feedback from human reviewers and domain experts was
incorporated into prompts to improve robustness of the automated GENERATOR and
REVIEWERS.

Figure 1: An overview of the GENERATOR and REVIEWERS process for automated
dataset generation. 1. The GENERATOR proposes a candidate to the REVIEWERS. 2.
The REVIEWERS can either pass the candidate on for Human Review, or offer
specific feedback to the GENERATOR, which will then continue to produce
candidates until 3. The REVIEWERS pass on for Human Review. The guidelines act
as a set of rules that the GENERATOR, REVIEWERS, and Human Reviewers all
follow.

####  3.1.1 Generator Prompt

The GENERATOR prompt is responsible for producing candidate dataset entries. A
well-crafted GENERATOR prompt enhances the efficiency and quality of automated
dataset generation. It needs a clear task definition, where GPT-4 is provided
with unambiguous, precise guidelines that enable the generation of relevant
text. This involves a succinct task description accompanied by a list of
instructions that leaves no room for misinterpretation. The GENERATOR prompt
should also utilize a memetic proxy, a concept backed by research suggesting
that the portrayal of the GENERATOR as an expert in the targeted domain can
enhance the quality of the responses [23]. It’s also beneficial to use few-
shot prompting, giving the model high-quality output examples to aid task
comprehension [6]. Finally, the prompt should be feedback-responsive,
adjusting to reviewer panel input for data refinement. A default temperature
parameter of 0.7 has been found effective for initial generation and feedback
response.

####  3.1.2 Reviewer Panel Prompts

The REVIEWERS are designed to ensure high-quality, contextually accurate data
entries. This process is based on Recursive Criticism and Improvement (RCI)
[7]. The REVIEWERS are an ensemble of prompts, each specialized in adhering to
logical guidelines initially set for the dataset. A REVIEWER should respond
with their rejection or acceptance of the candidate from the GENERATOR, as
well as their reasoning. Each REVIEWER can be considered an individual critic,
similar to the system proposed by Gou et al [26]. We developed the following
REVIEWER best practices:

##### Panel Formation

To create a robust feedback system, we recommend distributing the rules among
multiple REVIEWER personas, with each one specializing in a subset of rules.
The distribution of responsibilities does not need to be mutually exclusive.
Allowing overlap in the rules may increase the reliability of the feedback
system, because the same rule will be evaluated from different perspectives
among the REVIEWER personas. This persona system is also driven by the idea of
memetic proxy [23].

##### Reviewer Role

Once the GENERATOR produces a candidate QA pair, the candidate is forwarded to
the REVIEWERS. Each of the REVIEWERS evaluates the candidate based on its
assigned rules. If a REVIEWER identifies any rule breaches, it generates
feedback indicating the specific issues and suggestions for improvement. Since
we want the REVIEWERS to be rigid rule-followers, a lower temperature of 0.3
is appropriate.

##### Feedback Loop

The feedback from each REVIEWER is sent back to the GENERATOR for iterative
improvement. The GENERATOR uses insights from the feedback, aiming to resolve
the identified issues while maintaining the validity and context of the entry.
This revised entry is again forwarded to the reviewer panel, initiating
another round of feedback or acceptance. If the review panel does not reach a
consensus to accept after a maximum of five feedback loop iterations, no QA
pair is stored for that text, and the application proceeds to the next text.

##### Chain-of-Thought Reasoning

A REVIEWER is requested to provide its reasoning before deciding if a
candidate is passing. This utilizes Chain-of-Thought [24] and Show-Your-Work
reasoning [25].

The feedback prompts for the REVIEWERS were crafted ensuring they provided
clear, actionable suggestions for the GENERATOR. To achieve this, the prompts
were designed to indicate not only the issues but also possible solutions or
improvements. In summary, coordination between the GENERATOR and REVIEWERS
forms the backbone of our automated dataset generation method.

####  3.1.3 Human Quality Review

Human review remains an essential step in dataset generation. Human reviewers
serve as a final quality check, assessing candidate entries generated by the
model for final acceptance or rejection. This process is much faster than
manual generation as reviewers merely need to evaluate pre-generated entries.
Their feedback also helps refine the RCI process by highlighting the strengths
and weaknesses of the model’s iterations.

###  3.2 Application of Approach to Coreference Resolution Dataset Creation

We aim to generate a dataset, Coreference Resolution and Question Answering
(CRaQAn), that requires coreference resolution across sentences in a passage
for accurate QA to assess chunking strategies for information retrieval.
Recognizing the importance and complexity of coreference resolution, we
believe our method can significantly contribute to this field by creating a
high-quality dataset quickly and at scale. Complete documentation of prompts
for the sections below can be found in the Appendix.

Figure 2: Example of how a candidate for the CRaQAn dataset would be
generated. Optionally, the GENERATOR can be seeded with a ground truth text
corpus, which we demonstrate here. (1) The text corpus is split into
individual sentences for easier reference. (2) The sentences are sent to the
GENERATOR. (3) The GENERATOR creates the first question-answer coreference
candidate from these sentences and sends it to the REVIEWER panel. (4) The
REVIEWER panel identifies an issue with the candidate and sends feedback to
the GENERATOR. (5) The GENERATOR updates the candidate and sends back to the
REVIEWER panel. (6) The REVIEWER panel accepts this updated candidate and
passes it along for Human Review.

####  3.2.1 Guidelines for CRaQAn

We developed the following guidelines for our CRaQAn dataset: 1) Create an
aligned question and answer from the provided text focusing on pronominal,
nominal, and anaphoric coreferences across sentences. The complexity of the
coreference can range from basic to moderate. 2) Refrain from including
complex elements like cataphoric coreferences, appositive coreferences, and
zero anaphora. 3) Include in your response those sentence indices that are
necessary to understand the question and provide an accurate answer. 4)
Exclude from your response those sentence indices which are not essential in
understanding the question and the correct answer. 5) Respond appropriately to
the feedback from the REVIEWER. Please note, some guidelines have been edited
to improve readability.

####  3.2.2 Text Data Curation for CRaQAn

We curated our text corpus from Wikipedia articles on modern U.S. laws,
selected for their complexity and rich coreference relationships. We converted
100 selected articles to Markdown and split them by their sections. We then
selected the summary section at the top of the article as well as randomly
selected sections from the body of the article. The sections were split into
sentences using gpt-3.5-turbo, a cost-effective alternative to GPT-4 for this
relatively simple task. In our experience, gpt-3.5-turbo is a more reliable
sentence splitter than the Natural Language Toolkit (NLTK) in Python. The
resulting text corpus consisted of 578 sections from Wikipedia articles, split
into indexed sentences.

####  3.2.3 Approach for Generator and Reviewer Panel

Following our above described best practices and guidelines, we developed a
GENERATOR prompt and 4 REVIEWER prompts. The GENERATOR is written to accept
split text sections and create coreference–dependent question-answer pairs
from them. The REVIEWER prompts are each specialized in different aspects of
our dataset, with some overlap in the prompts themselves, including a: 1)
Content Cohesion Reviewer, 2) Information Accuracy Reviewer, 3) Linguistic
Quality Reviewer, and 4) Required Sentence Reviewer. Personas were chosen to
reflect the guidelines we developed for the coreference dataset curation. The
REVIEWER prompts respond to the GENERATOR question-answer pairs with feedback.

####  3.2.4 Methods for Human Review

Each question-answer sample in the dataset was reviewed by a minimum of two
human reviewers who were responsible for rejecting low quality QA pairs. The
human reviewers were given the same guidelines as the GENERATOR and REVIEWERS
to assess quality. Reviewing the CRaQAn dataset took our human reviewers
approximately 2 minutes on average to evaluate each QA pair.

##  4 CRaQAn Dataset

Table 1: CRaQAn Characteristics Characteristic | Total |  |
---|---|---|---
Number of Unique Wikipedia Articles | 70 |  |
Number of QA Pairs from a Summary Section | 57 |  |
Number of QA Pairs from a Random Section | 204 |  |
Number of QA Pairs that Require 2 Sentences to Answer | 229 |  |
Number of QA Pairs that Require 3 Sentences to Answer | 32 |  |
| 10% Quantile | 50% Quantile | 90% Quantile
Number of Sections per Article | 1 | 3.5 | 6
Number of Sentences per Section | 4 | 7 | 12
Number of Words per Section | 83 | 159 | 299
Number of Sentences between Coreferences | 1 | 1.5 | 4
Figure 3: Two examples from the CRaQAn Dataset. Top: Nominal coreference resolution from sentences 0 and 2 (“Energy Policy Act of 2005” and "the law") is required to answer the question. Bottom: Pronomial coreference resolution from sentences 0 and 2 ("Copyright Act of 1976" and "It") is required to answer the question. Table 2: CRaQAn Non-Passing Candidates Human Reviewer Reasoning | Count
---|---
Irrelevant Sentences Included | 47
Important Sentences Excluded | 43
Parsing or Formatting Errors | 36
Incomplete or Unclear Answer | 17
Question Ambiguity | 17
Coreference Errors | 11
Other | 9
Wrong Information | 7
Compound or Double Questions | 6

The initial release of CRaQAn contains 261 human reviewed question-answer
samples. Table 1 illustrates characteristics of the dataset. The yield from
our automated generation was approximately 60.2%, where at least 2 individual
reviewers accepted 348 out of 578 QA pairs. The most common reasons for
rejection were inclusion of irrelevant sentences (n = 47), exclusion of
required sentences (n = 43), and formatting errors (n = 36). Table 2
highlights all human reviewer versus CRaQAn candidate disagreements. 87 out of
348 of the accepted QA pairs were identified as duplicates of the same
Wikipedia section and were subsequently dropped, leaving 261 QA pairs in our
initial release.

##  5 Discussion

Our work presents a practical approach to automated dataset generation, an
area of growing interest in ML research. Leveraging GPT-4 and a Recursive
Criticism and Improvement (RCI) loop, we created CRaQAn, a distinctive dataset
that caters to the nuanced information retrieval requirements of coreference
resolution in QA tasks. Most existing datasets have either focused on QA or
coreference resolution individually. By integrating both, CRaQAn represents a
significant contribution in the field, providing a valuable resource for
researchers and practitioners in natural language processing aiming to tackle
complex information retrieval tasks. By making this dataset and code available
on Hugging Face, we hope to contribute to the ongoing research in this domain.

Our method led to the generation of a diverse set of coreference resolution
scenarios, many of which were complex and nuanced, stretching beyond our
initial expectations and guidelines. This highlights the potential richness of
automated dataset creation, where instruction-following language models like
GPT-4 can generate a plethora of unique and challenging real-world examples.

However, it’s important to recognize the limitations of our approach. The
requirement for human review, the necessity to craft effective prompts, and
the costs associated with generation are among the challenges that need to be
addressed. Without scaling this method, the initial CRaQAn release of 261 QA
pairs will be reasonably limited to testing and evaluation. Future work will
seek to refine and scale this process, striving for better efficiency and
cost-effectiveness in automated dataset generation.

Additionally, we recognize the inherent limitation that questions and answers
generated by GPT-4 are only reflective of the types of questions that GPT-4
comprehends. While beneficial for particular applications, it may not serve as
an unbiased benchmark for comparison across different LLMs or against human
performance. This is because GPT-4 may not encapsulate the range of questions
that other LLMs find challenging or the types of questions humans would
naturally ask. We highlight this point as essential for interpreting results
using the CRaQAn dataset and managing expectations of its utility.

The CRaQAn dataset could be enhanced in several ways in the future. One way is
by expanding the dataset from single Wikipedia sections to whole articles or
even full-length books. This would enable the dataset to tackle more intricate
coreference problems, making it more representative of real-world information
retrieval tasks. Another potential enhancement is to incorporate more
challenging types of coreference, such as zero anaphora or cataphora. This
would add to the complexity and usefulness of the dataset. Lastly, introducing
per-phrase coreference labeling to the dataset could be beneficial. This would
allow for more detailed tasks of granular resolution, thereby facilitating a
deeper understanding of the relationships within the text.

##  6 Dataset Availability

The CRaQAn dataset, along with the code used for its generation, is publicly
available on the Hugging Face platform to facilitate open research and
collaboration: https://huggingface.co/datasets/Edge-Pyxos/CRaQAn_v1. The
dataset is licensed under the Creative Commons Attribution 4.0 International
(CC BY 4.0) License, which allows for the free distribution, modification, and
use of the dataset, provided appropriate credit is given through citation of
this paper. Researchers interested in exploring coreference resolution in QA
tasks are encouraged to use this dataset, and we welcome any contributions to
its improvement and expansion.

## References

  * [1] Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang.  Lost in the middle: How language models use long contexts.  arXiv preprint arXiv:2307.03172, 2023.
  * [2] Pinecone Roie Schwaber-Cohen.  Chunking strategies for llm applications.  https://www.pinecone.io/learn/chunking-strategies/, 2023.  Accessed: 2023-09-25.
  * [3] Sheng Xu, Peifeng Li, and Qiaoming Zhu.  Improving event coreference resolution using document-level and topic-level information.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 6765–6775, 2022.
  * [4] Nghia T Le and Alan Ritter.  Are large language models robust zero-shot coreference resolvers?  arXiv preprint arXiv:2305.14489, 2023.
  * [5] Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei.  Text embeddings by weakly-supervised contrastive pre-training.  arXiv preprint arXiv:2212.03533, 2022.
  * [6] OpenAI.  Gpt-4 technical report, 2023.
  * [7] Geunwoo Kim, Pierre Baldi, and Stephen McAleer.  Language models can solve computer tasks.  arXiv preprint arXiv:2303.17491, 2023.
  * [8] RWEHM Marcus, Martha Palmer, RBSPL Ramshaw, and Nianwen Xue.  Ontonotes: A large training corpus for enhanced processing.  Joseph Olive, Caitlin Christianson, andJohn McCary, editors, Handbook of Natural LanguageProcessing and Machine Translation: DARPA GlobalAutonomous Language Exploitation, 2011.
  * [9] Hong Chen, Zhenhua Fan, Hao Lu, Alan L Yuille, and Shu Rong.  Preco: A large-scale dataset in preschool vocabulary for coreference resolution.  arXiv preprint arXiv:1810.09807, 2018.
  * [10] Kellie Webster, Marta Recasens, Vera Axelrod, and Jason Baldridge.  Mind the gap: A balanced corpus of gendered ambiguous pronouns.  Transactions of the Association for Computational Linguistics, 6:605–617, 2018.
  * [11] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, Kenton Lee, Kristina N. Toutanova, Llion Jones, Ming-Wei Chang, Andrew Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov.  Natural questions: a benchmark for question answering research.  Transactions of the Association of Computational Linguistics, 2019.
  * [12] Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang.  Squad: 100,000+ questions for machine comprehension of text.  arXiv preprint arXiv:1606.05250, 2016.
  * [13] Pranav Rajpurkar, Robin Jia, and Percy Liang.  Know what you don’t know: Unanswerable questions for squad.  arXiv preprint arXiv:1806.03822, 2018.
  * [14] Pradeep Dasigi, Nelson F Liu, Ana Marasović, Noah A Smith, and Matt Gardner.  Quoref: A reading comprehension dataset with questions requiring coreferential reasoning.  arXiv preprint arXiv:1908.05803, 2019.
  * [15] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning.  Hotpotqa: A dataset for diverse, explainable multi-hop question answering.  arXiv preprint arXiv:1809.09600, 2018.
  * [16] Nikahat Mulla and Prachi Gharpure.  Automatic question generation: a review of methodologies, datasets, evaluation metrics, and applications.  Progress in Artificial Intelligence, 12(1):1–32, 2023.
  * [17] Sabina Elkins, Ekaterina Kochmar, Iulian Serban, and Jackie CK Cheung.  How useful are educational questions generated by large language models?  In International Conference on Artificial Intelligence in Education, pages 536–542. Springer, 2023.
  * [18] Kettip Kriangchaivech and Artit Wangperawong.  Question generation by transformers.  arXiv preprint arXiv:1909.05017, 2019.
  * [19] Luis Enrico Lopez, Diane Kathryn Cruz, Jan Christian Blaise Cruz, and Charibeth Cheng.  Simplifying paragraph-level question generation via transformer language models.  In PRICAI 2021: Trends in Artificial Intelligence: 18th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2021, Hanoi, Vietnam, November 8–12, 2021, Proceedings, Part II 18, pages 323–334. Springer, 2021.
  * [20] Ying-Hong Chan and Yao-Chung Fan.  A recurrent bert-based model for question generation.  In Proceedings of the 2nd workshop on machine reading for question answering, pages 154–162, 2019.
  * [21] Veniamin Veselovsky, Manoel Horta Ribeiro, Akhil Arora, Martin Josifoski, Ashton Anderson, and Robert West.  Generating faithful synthetic data with large language models: A case study in computational social science.  arXiv preprint arXiv:2305.15041, 2023.
  * [22] Anthropic.  Prompt engineering for claude’s long context window.  https://www.anthropic.com/index/prompting-long-context, 2023.  Accessed 29-09-2023.
  * [23] Laria Reynolds and Kyle McDonell.  Prompt programming for large language models: Beyond the few-shot paradigm.  In Extended Abstracts of the 2021 CHI Conference on Human Factors in Computing Systems, pages 1–7, 2021.
  * [24] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  Advances in Neural Information Processing Systems, 35:24824–24837, 2022.
  * [25] Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al.  Show your work: Scratchpads for intermediate computation with language models.  arXiv preprint arXiv:2112.00114, 2021.
  * [26] Zhibin Gou, Zhihong Shao, Yeyun Gong, Yelong Shen, Yujiu Yang, Nan Duan, and Weizhu Chen.  Critic: Large language models can self-correct with tool-interactive critiquing.  arXiv preprint arXiv:2305.11738, 2023.

##  Appendix A GENERATOR PROMPT

As a PhD holder in Computational Linguistics and Natural Language Processing
(NLP) with a focus on Information Extraction, your task is to aid in the
creation of a dataset based on coreference resolution for question-answers.
This mainly concerns the development of clear and relevant question-answer
pairs from a given segmented_text, which may contain coreferential links
within sentences. The indices of segmented_text are the order of the sentences
in an original document.

Follow these rules:

1\. Create an aligned question and answer from the segmented_text focusing on
pronominal, nominal, and anaphoric coreferences across sentences. The
complexity of the coreference can range from basic to moderate.

2\. Refrain from including complex elements like cataphoric coreferences,
appositive coreferences, and zero anaphora.

3\. Include in the field "required_sentence_indices" those sentence indices
that are necessary to understand the question and provide an accurate answer.

4\. Exclude from the field "required_sentence_indices" those sentence indices
which are not essential in understanding the question and the correct answer.

5\. Respond appropriately to the feedback from the REVIEWER, usually by
creating a new question, answer, and required_sentence_indices. At times,
modifications on existing inputs may be enough.

6\. Ensure that the "required_sentence_indices" field includes either 2 or 3
sentences.

Your completed task should be in JSON format:

"question": <question>, "answer": <answer>, "required_sentence_indices":
<required_sentence_indices>

Example 1, which is a great response and follows all of the above rules:

SEGMENTED_TEXT: ["index": 0, "sentence": "Albert Einstein was a theoretical
physicist who developed the theory of relativity.", "index": 1, "sentence":
"His work is also known for its influence on the philosophy of science.",
"index": 2, "sentence": "He won the 1921 Nobel Prize in Physics.", "index": 3,
"sentence": "Einstein, considered one of the most important figures in the
history of science, was awarded the prize for his services to theoretical
physics and especially for his discovery of the law of the photoelectric
effect."]

YOU: "question": "For what discovery did Albert Einstein win the Nobel Prize
in Physics?", "answer": "The law of the photoelectric effect.",
"required_sentence_indices": [0, 2, 3]

REVIEWER: Great job! Your response fills all of our criteria.

Example 2, which is a great response and follows all of the above rules:

SEGMENTED_TEXT: ["index": 0, "sentence": "Samantha is a talented painter.",
"index": 1, "sentence": "She has won numerous awards for her work.", "index":
2, "sentence": "The artist often uses bright colors in her pieces.", "index":
3, "sentence": "Despite her young age, she enjoys respect and admiration from
older artists."]

YOU: "question": "What does the artist Samantha often use in her pieces?",
"answer": "Bright colors.", "required_sentence_indices": [0, 2]

REVIEWER: Great job! Your response fills all of our criteria.

Example 3, which is a great response and follows all of the above rules:

SEGMENTED_TEXT: ["index": 0, "sentence": "Rainforests are places with enormous
diversity among species.", "index": 1, "sentence": "Amazon rainforest is the
world’s largest tropical rainforest.", "index": 2, "sentence": "It covers an
area of five and half a million square kilometers.", "index": 3, "sentence":
"The Amazon is home to an astounding number of plant species, some of which
are not found anywhere else in the world.", "index": 4, "sentence": "This
forest is also a habitat for many animal species."]

YOU: "question": "How large is the area that the Amazon rainforest covers?",
"answer": "Five and half a million square kilometers.",
"required_sentence_indices": [1, 2]

REVIEWER: Great job! Your response fills all of our criteria.

Example 4, which is an initially bad response made better by the REVIEWER:

SEGMENTED_TEXT: ["index": 0, "sentence": "The Affordable Care Act (ACA),
formally known as the Patient Protection and Affordable Care Act and
colloquially known as Obamacare, was signed into law by President Barack Obama
on March 23, 2010.", "index": 1, "sentence": "Together with the Health Care
and Education Reconciliation Act of 2010 amendment, it represents the U.S.
healthcare system’s most significant regulatory overhaul and expansion of
coverage since the enactment of Medicare and Medicaid in 1965.","index": 2,
"sentence": "The ACA’s major provisions came into force in 2014."]

YOU: "question": "When did the ACA’s major provisions come into force?",
"answer": "2014.", "required_sentence_indices": [0, 2]

REVIEWER: Your question does not require a coreference resolution between
sentences to answer and only requires sentence index 2 to answer. Please
revise your question.

YOU: "question": "When did the Affordable Care Act’s major provisions come
into force?", "answer": "2014.", "required_sentence_indices": [0, 2]

REVIEWER: Great job! Your response fills all of our criteria.

Now it’s your turn:

SEGMENTED_TEXT: *PLACEHOLDER*

YOU:

##  Appendix B REVIEWER PROMPT: Content Cohesion Reviewer

As a Context and Cohesion Reviewer, your chief task is to ensure that there is
total consistency and adherence to contextual information and solid cohesion
amongst all components. All entities must be able to not only stand alone but
also integrate seamlessly into the dataset, which includes the segmented text,
required_sentence_indices, and the question & answer pair.

Operational Directives:

1\. Verify that the question and answer pair depend ONLY on the information in
the sentences of the segmented text that are indicated by the
required_sentence_indices. 2\. If there are any pronouns or references in the
question, ensure they have clear antecedents in the sentences provided as
indicated by the required_sentence_indices. 3\. Verify that the question does
not introduce or imply any context that is not explicitly stated in the
sentences referred to by required_sentence_indices. 4\. Confirm that all
required_sentence_indices have been utilized in the usage of the question and
formation of the answer. 5\. To mark an instance as "quality", ensure that all
these directives are fulfilled. If any of these directives fall short, mark
the instance as "not quality".

Please respond in the following JSON format "reason": <reason_for_quality>,
"is_quality": <true/false>

Here is an excellent example where "is_quality" should be marked as false:

INPUT: "segmented_text": ["index": 0, "sentence": "Steve creates web
designs.", "index": 1, "sentence": "His clients say they are impressed.",
"index": 2, "sentence": "He works in the Silicon Valley."], "question": "Why
are Steve’s clients impressed?", "answer": "Because of his web designs.",
"required_sentence_indices": [1, 2]

YOU: "reason": "The question assumes information (’Steve creates web
designs.’) that is not provided in the sentences indicated by
required_sentence_indices([1, 2])", "is_quality": false

Here is an excellent example where "is_quality" should be marked as true:

INPUT: "segmented_text": ["index": 0, "sentence": "The ’Titanic’ sank on its
maiden voyage.", "index": 1, "sentence": "It hit an iceberg and began to
sink.", "index": 2, "sentence": "The ship went down on April 15, 1912."],
"question": "What happened on April 15, 1912?", "answer": "The ’Titanic’
sank.", "required_sentence_indices": [0, 2]

YOU: "reason": "All operational directives are followed.", "is_quality": true

Now it’s your turn:

INPUT: *PLACEHOLDER*

YOU:

##  Appendix C REVIEWER PROMPT: Information Accuracy Reviewer

As an Information Accuracy Reviewer, your chief task is to ensure the
precision and factual correctness of the information presented in the given
segmented text, question, and answer. You specialize in checking the accuracy
of the relevant information, particularly critical contextual details such as
dates, names, and places. Your tasks include verifying the listed sentences’
accuracy by analyzing the content in relation to the indices mentioned. By
doing so, you validate if the answer is both concise and correct in response
to the question. You should ensure that the details mentioned in the segmented
text, question, and answer align perfectly, without any discrepancies. It’s
your responsibility to check that the question and answer pair revolve around
the information present only in the sentences pointed out by the
required_sentence_indices.

Operational directives:

1\. Evaluate the segmented_text, question, and answer for factual accuracy.
2\. Assess if the answer is concise and correctly addresses the asked
question. 3\. Validate that there are no discrepancies in the critical details
such as dates, names, and places across the segmented_text, question, and
answer. 4\. Confirm that the question and answer pair utilize the information
from the sentences mentioned by required_sentence_indices and that no
additional details outside those sentences are present in the question or
answer. 5\. Ensure that the question does not assume any details or context
that are not present in the sentences indicated by the
required_sentence_indices. 6\. To mark an instance as "quality", ensure that
all these directives are fulfilled. If any of these directives fall short,
mark the instance as "not quality".

Please respond in the following JSON format "reason": <reason_for_quality>,
"is_quality": <true/false>

Here is an excellent example where "is_quality" should be marked as false:

INPUT: "segmented_text": ["index": 0, "sentence": "Steve Jobs co-founded Apple
Inc. with Steve Wozniak in 1976.", "index": 1, "sentence": "Jobs also became
the majority shareholder of Pixar in 1986."], "question": "Who were the co-
founders of Apple Inc. and what animation company did Jobs become a majority
shareholder of?", "answer": "Steve Jobs and Steve Wozniak co-founded Apple
Inc. Jobs became the majority shareholder of Walt Disney Animation Studios.",
"required_sentence_indices": [0, 1]

YOU: "reason": "The answer includes information that is not present in the
sentences indicated by required_sentence_indices. Jobs became the majority
shareholder of Pixar, not Walt Disney Animation Studios.", "is_quality": false

Here is an excellent example where "is_quality" should be marked as true:

INPUT: "segmented_text": ["index": 0, "sentence": "Thomas Edison was an
inventor who developed many devices.", "index": 1, "sentence": "Among his
greatest innovations was the practical electric light bulb."], "question":
"What is one of Thomas Edison’s greatest innovations?", "answer": "The
practical electric light bulb.", "required_sentence_indices": [0, 1]

YOU: "reason": "All operational directives are followed.", "is_quality": true

Now it’s your turn:

INPUT: *PLACEHOLDER*

YOU:

##  Appendix D REVIEWER PROMPT: Linguistic Quality Reviewer

As a Linguistic Quality Reviewer, your chief task is to ensure that the
linguistic aspects of the dataset example are of high-quality and meet all the
set guidelines. Your role is vital in guaranteeing the clarity,
grammaticality, and coherence of the segmented text, question, and answer.

You will focus on the structure and content of the question, ensuring that it
is phrased clearly and concisely, and doesn’t join multiple queries into one,
using conjunctions. You will review the answer to verify it’s unambiguous,
pertinent, and doesn’t entail any unnecessary details that could potentially
confuse the reader or student.

Correctness of grammar and syntax used, punctuation accuracy, appropriate
usage of language and vocabulary are all within your responsibility. In the
case of any detected linguistic errors or cases of confusing text, you will
need to report these issues, providing a valid reason.

Operational directives:

1\. Review the question for clearness and conciseness. The question should
pose a single issue; split queries joined by conjunctions should be flagged.
2\. Assess the accuracy of the answer. It must be terse and provide a
straightforward response to the question. 3\. Check for linguistic quality.
The language should be fluent and grammatically correct, with no instances of
ambiguity, slang, or jargon. Any language inconsistencies should be noted and
described. 4\. Evaluate the overall coherence between the segmented text with
required_sentence_indices, question, and answer. They should all be logically
and linguistically consistent. 5\. Review the question for clearness,
conciseness, and complete reliance on the context provided by the sentences as
indicated by the required_sentence_indices. 6\. To mark an instance as
"quality", ensure that all these directives are fulfilled. If any of these
directives fall short, mark the instance as "not quality".

Please respond in the following JSON format "reason": <reason_for_quality>,
"is_quality": <true/false>

Here is an excellent example where "is_quality" should be marked as true:

INPUT: "segmented_text": ["index": 0, "sentence": "Jane Austen’s Pride and
Prejudice was published in 1813.", "index": 1, "sentence": "The novel has
since become one of the most famous works in English literature"], "question":
"When was Jane Austen’s Pride and Prejudice published?", "answer": "1813.",
"required_sentence_indices": [0]

YOU: "reason": "All operational directives are followed.", "is_quality": true

Here is an excellent example where "is_quality" should be marked as false:

INPUT: "segmented_text": ["index": 0, "sentence": "In 1912, RMS Titanic sank
in the North Atlantic Ocean.", "index": 1, "sentence": "The exact number of
passengers is unknown, but estimates put it at over 2,200 people"],
"question": "When did the Titanic sink and how many people were on board?",
"answer": "1912 and over 2,200 people.", "required_sentence_indices": [0,1]

YOU: "reason": "The question combines two queries into one using a
conjunction.", "is_quality": false

Now it’s your turn:

INPUT: *PLACEHOLDER*

YOU:

##  Appendix E REVIEWER PROMPT: Required Sentence Reviewer

As a Required Sentence Reviewer, your task is to review question & answer
pairs that have been generated from a passage of text to ensure that the
required sentences are actually required. You must categorize the generated
questions & answers as either "quality" or "not quality" and explain your
reasoning.

Criteria for marking an instance as "quality":

1\. The question and answer depend ONLY on the information in the sentences of
the segmented text that are indicated by the required_sentence_indices. There
is no critical information in the passage which was not marked as required.
Importantly, sentences which are required for pronoun disambiguation and
coreference resolution must also be marked as required. 2\. ALL of the
sentences indicated by the required_sentence_indices are actually required for
answering the question. There are no irrelevant sentences included in
required_sentence_indices.

Here is an excellent example where "is_quality" should be true:

INPUT: "segmented_text": ["index": 0, "sentence": "The ’Titanic’ sank on its
maiden voyage.", "index": 1, "sentence": "It hit an iceberg and began to
sink.", "index": 2, "sentence": "The ship went down on April 15, 1912."],
"question": "What happened on April 15, 1912?", "answer": "The ’Titanic’
sank.", "required_sentence_indices": [0, 2]

YOU: "reason": "Sentence 2 mentions "The ship", but without the additional
context from sentence 0, we could not be certain which ship was being talked
about. With both sentence 0 and 2, we have all the information that we need to
answer the question and no critical information is missing. That means
criteria #1 has been met. In addition, no unnecessary sentences were marked as
required, so criteria #2 has been met as well.", "is_quality": true

Here is an excellent example where "is_quality" should be marked as false
because some of the criteria are not met:

INPUT: "segmented_text": ["index": 0, "sentence": "Steve creates web
designs.", "index": 1, "sentence": "His clients say they are impressed.",
"index": 2, "sentence": "He works in the Silicon Valley."], "question": "Why
are Steve’s clients impressed?", "answer": "Because of his web designs.",
"required_sentence_indices": [1, 2]

YOU: "reason": "The question asks about "Steve’s clients". Sentence 1 and 2
use pronouns but don’t mention "Steve" by name. Sentence 0 is required in
order to disambiguate the pronouns "He" and "His" in the later sentences.
Sentence 0 should have been marked as required but was not.", "is_quality":
false

Here is an excellent example where "is_quality" should be marked as false
because some of the criteria are not met:

INPUT: "segmented_text": ["index": 0, "sentence": "The Amazon rainforest, also
called Amazon jungle or Amazonia, is a moist broadleaf tropical rainforest in
the Amazon biome that covers most of the Amazon basin of South America.",
"index": 1, "sentence": "More than 56

YOU: "reason": "The question is about the dust that fertilizes the Amazon
rainforest. Sentence 1 contains all the information needed to answer the
question and it does not contain any references which need to be disambiguated
by preceding sentences. Sentence 0 was marked but is not actually required to
answer the question.", "is_quality": false

Now it’s your turn:

INPUT: *PLACEHOLDER*

YOU:


11institutetext:  Dept. of CSE, National Institute of Technology, Durgapur,
India 22institutetext: Dhirubhai Ambani Institute of Information and
Communication Technology, Gandhinagar, Gujarat, India
22email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Generalized Red-Blue Circular Annulus Cover Problem

Sukanya Maji corresponding author11 Supantha Pandit 22 Sanjib Sadhu 11

###### Abstract

We study the Generalized Red-Blue Annulus Cover problem for two sets of
points, red ($R$) and blue ($B$), where each point $p\in R\cup B$ is
associated with a positive penalty ${\cal P}$$(p)$. The red points have non-
covering penalties, and the blue points have covering penalties. The objective
is to compute a circular annulus ${\cal A}$ such that the value of the
function ${\cal P}$$({R}^{out})+$${\cal P}$$({B}^{in})$ is minimum, where
${R}^{out}\subseteq{R}$ is the set of red points not covered by ${\cal A}$ and
${B}^{in}\subseteq{B}$ is the set of blue points covered by ${\cal A}$. We
also study another version of this problem, where all the red points in $R$
and the minimum number of points in $B$ are covered by the circular annulus in
two dimensions. We design polynomial-time algorithms for all such circular
annulus problems.

###### Keywords:

Annulus cover Bichromatic point-set Circular annulus Voronoi Diagram

##  1 Introduction

An annulus is a closed region bounded by two geometric objects of the same
type, such as axis-parallel rectangles [13], circles [19], convex polygons
[6], and many more. The minimum width annulus problem is related to the
problem of finding a shape that fits in a given set of points in the plane
[1]. Further, the largest empty annulus of different shapes has many potential
applications [18, 8]. A point $p$ is said to be covered by an annulus ${\cal
A}$ if $p$ lies within the closed region bounded by ${\cal A}$.

In this paper, we study the Generalized Red-Blue Annulus Cover problem to
compute an annulus for a bichromatic point-set where each point has a positive
penalty. In this problem, we take a bichromatic point-set as a set of red
points and a set of blue points. A positive penalty, also called the non-
covering (resp. covering) penalty is associated with each red (resp. blue)
point, i.e., if a red point is not covered, then its penalty is counted,
whereas if a blue point is covered, then its penalty is counted. The objective
is to find an annulus $\cal A$ with minimum weight, where the weight of $\cal
A$ is the total penalty of the red points not covered plus the total penalty
of the blue points covered by $\cal A$. We define this problem formally as
follows. Generalized Red-Blue Annulus Cover (GRBAC) problem.  Given a set of
$m$ blue points ${B}=\\{p_{1},p_{2},\ldots,p_{m}\\}$ and a set of $n$ red
points ${R}=\\{q_{1},q_{2},\ldots,q_{n}\\}$, and a penalty function ${\cal
P}:{R}\cup{B}\rightarrow\mathbb{R}^{+}$. The objective is to find an circular
annulus $\cal A$ such that the quantity $\lambda=\sum_{q\in{R}^{out}}{\cal
P}(q)+\sum_{p\in{B}^{in}}{\cal P}(p)$ is minimum, where
${R}^{out}\subseteq{R}$ is the set of points not covered by $\cal A$ and
${B}^{in}\subseteq{B}$ is the set of points covered by $\cal A$.

If the penalty of each red point is $\infty$ and that of a blue point is a
unit, then the GRBAC problem reduces to a problem of computing an annulus that
covers all the red points while covering a minimum number of blue points. We
refer to this problem as the Red-Blue Annulus Cover (RBAC) problem.

Recently, Maji et al. [15] have studied the various types of Red-Blue
rectangular annulus cover problems. So, in this paper, we focus our study on
computing a circular shape annulus for both the RBAC and GRBAC problems. We
refer to the problem of computing a circular annulus in the RBAC problem
(resp. GRBAC problem) as the RBCAC problem (resp. GRBCAC problem). There exist
multiple annuli covering the same set of blue and red points that minimize
$\lambda$. Throughout this paper, we report the one among these annuli, whose
boundaries pass through some red points as an optimal solution.

Motivation: The oncologists remove the cancer cells while avoiding the healthy
cells as much as possible during the surgery or radiation therapy of the
cancer patients. We distinguish these two types of cells with two different
colors. The excision of the tumor leads us to various geometric optimization
problems, e.g., to determine the smallest circle enclosing the red points or
that separates the red points from the blue points. Instead of computing the
smallest enclosing circle, the computation of an annulus which covers all the
tumor cells and a minimum number of healthy cells, leads us to less wastage of
the healthy cells while performing surgery. This motivates us to formulate a
problem of covering the bichromatic point-set by an annulus that covers all
the given red points while minimizing the number of blue points covered by it.
Depending on the stage of the cancer cells and the importance of the healthy
cells, we can assign different weights called penalties to each cancer cell
and healthy cell so that the penalty incurred due to the elimination of
healthy cells and keeping the cancer cells within the body during the surgery,
is minimized. This motivates us to study the annulus cover problem by
assigning penalties to each point in $R\cup B$.

##  2 Related Works

The problem of computing the largest empty annulus [18, 8] is a well-studied
problem, where a set $S$ of $n$ points is partitioned into two subsets of
points - one lying completely outside the outer boundary and the other one
lying completely inside the inner boundary of the annulus, i.e., no point in
$S$ lies in the interior of the annulus. This problem is related to the
maximum facility location problem for $n$ points, where the facility is a
circumference. Díaz-Báñez et al. [12] computed the largest empty circular
annulus in $O(n^{3}\log n)$-time and $O(n)$-space. Bae et al. [5] studied the
maximum-width empty annulus problem, which computes square and rectangular
annulus in $O(n^{3}$) and $O(n^{2}\log n)$ time, respectively. Both of these
algorithms require $O(n)$ space. Also, Paul et al. [17] presented a
combinatorial technique using two balanced binary trees that computes the
maximum empty axis-parallel rectangular annulus that runs in $O(n\log n)$
time. Abellanas et al. [1] presented a linear time algorithm for the
rectangular annulus problem such that the annulus covers a given set of
points. They considered several variations of this problem. Gluchshenko et al.
[13] presented an $O(n\log n)$-time optimal algorithm for the planar
rectilinear square annulus. Also, it is known that a minimum width annulus in
arbitrary orientations can be computed in $O(n^{3}\log n)$ time for the square
annulus [4] and in $O(n^{2}\log n)$ time for the rectangular annulus [16].

Abidha and Ashok [3] studied the geometric separability problem for a
bichromatic point-set $P=R\cup B$ ($|P|=n$) of red ($R$) and blue ($B$)
points. It computes a separator as an object of a certain type that separates
$R$ and $B$. They computed different types of separators, e.g., (i) a non-
uniform and uniform rectangular annulus of fixed orientation in $O(n)$ and
$O(n\log n)$ time, (ii) a non-uniform rectangular annulus of arbitrary
orientation in $O(n^{2}\log n)$ time, (iii) a square annulus of fixed
orientation in $O(n\log n)$ time, (iv) an orthogonal convex polygon in
$O(n\log n)$ time. Maji et al. [15] presented several polynomial time
algorithms that compute various types of axis-parallel rectangular annulus
which cover all the red points and minimum number of blue points. Bitner et
al. [9] computed the largest separating circle and the minimum separating
circle for bichromatic point-set in $O(m(n+m)\log(n+m))$ time and $O(mn)$ \+
$O^{*}(m^{1.5})$ time, respectively, where the $O^{*}()$ notation ignores some
polylogarithmic factor.

The geometric version of a red-blue set cover problem is NP-Hard [10], where
for a given set of bichromatic (red and blue) points and a set of objects, a
subset of objects is chosen that cover all the blue points and the minimum
number of red points. Chan and Hu [11] designed PTAS for a weighted geometric
set cover problem where the objects are 2D unit squares. Madireddy et al. [14]
provided the APX-Hardness results of various special red-blue set cover
problems. Shanjani [20] also showed that the Red-Blue Geometric Set Cover is
APX-hard when the objects are axis-aligned rectangles. Abidha and Ashok [2]
studied the parameterized complexity of the generalized red-blue set cover
problem. Bereg et al. [7] studied the class cover problem for axis-parallel
rectangles and presented a $O(1)$-approximation algorithm.

Our Contributions: To the best of our knowledge, there exists no work on
circular annulus that is exactly similar to the problems studied in this
paper. Table 1 shows our contributions. We need to mention that, each solution
needs $O((m+n)\log(m+n))$ preprocessing time and $O(m+n)$ space.

Problems | Time Complexity
---|---
Red-Blue Circular Annulus | $O(m^{2}n(m+n))$
Generalized Red-Blue Circular Annulus | $O(n^{2}(m+n)^{3})$
Table 1: Results obtained for different circular annulus cover problems.

##  3 Preliminaries and Notations

For any point $p$, we denote its $x$ and $y$-coordinates by $x(p)$ and $y(p)$,
respectively. We compute a circular annulus in the RBAC and GRBAC problems,
i.e., we consider the $RBCAC$ (Red-blue circular annulus cover) and $GRBCAC$
(Generalized Red-blue circular annulus cover) problems. The width of a
circular annulus $\cal A$ is the difference between the radii of its outer and
inner circles, which we denote by ${\cal C}_{out}(\cal A)$ and ${\cal
C}_{in}(\cal A)$, respectively. The points on any circle’s boundary are said
to be the  defining points for that circle. A circular annulus has the
following property [8].

###### Property 1

[8] Four points are sufficient to define a circular annulus $\cal A$, where
either (i) three points lie on the boundary of its outer circle ${\cal
C}_{out}(\cal A)$ and one point lies on its inner circle ${\cal C}_{in}(\cal
A)$, (ii) three points lie on ${\cal C}_{in}(\cal A)$ and one point lies on
${\cal C}_{out}(\cal A)$, or (iii) two points lie on ${\cal C}_{in}(\cal A)$
and two points lie on ${\cal C}_{out}(\cal A)$.

We use $VD(R)$ and $FVD(R)$ to denote the Voronoi diagram and the farthest-
point Voronoi diagram of the point-set $R$, respectively. We state the
following properties of the $FVD(R)$ and $VD(R)$ [8, 18].

###### Property 2

[8] The centers of the circle passing through the three points in $R$ and
containing no (resp. all) other points in $R$ define the vertices of the
Voronoi diagram $VD(R)~{}($resp. farthest-point Voronoi diagram $FVD(R))$.

###### Property 3

[8] The locus of the center of the largest empty circles passing through only
a pair of points ($q_{i}$, $q_{j}$), where $q_{i},~{}q_{j}\in R$, defines an
edge of the $VD(R)$, whereas the edge in a $FVD(R)$ is defined similarly with
a difference that the circles cover all the points in $R$.

We use $VD_{i}$ and $VD_{i,j}$ to denote the Voronoi diagrams for the point-
set $R\cup\\{p_{i}\\}$ and $R\cup\\{p_{i},p_{j}\\}$ where $p_{i},p_{j}\in B$,
respectively. So, $VD_{i}=VD(R\cup\\{p_{i}\\})$ and
$VD_{i,j}=VD(R\cup\\{p_{i},p_{j}\\})$. Similarly, $FVD_{i}$ and $FVD_{i,j}$
are used to denote the farthest-point Voronoi diagrams for the point-set
$R\cup\\{p_{i}\\}$ and $R\cup\\{p_{i},p_{j}\\}$ where $p_{i},p_{j}\in B$,
respectively i.e., $FVD_{i}=FVD(R\cup\\{p_{i}\\})$ and
$FVD_{i,j}=FVD(R\cup\\{p_{i},p_{j}\\})$.

###### Property 4

[8, 18] Given a Voronoi diagram $VD(P)$ with $|P|=n$. We can insert a new
point $a$ (resp. two new points $a$ and $b$) and update the $VD(P)$ to obtain
$VD(P\cup\\{a\\})$ (resp. $VD(P\cup\\{a,b\\})$ ) in $O(n)$ time. Similarly, we
can update a given farthest-point Voronoi diagram $FVD(P)$ to obtain
$FVD(P\cup\\{a\\})$ and $FVD(P\cup\\{a,b\\})$.

Property 4 says that we can update $VD(R)$ (resp. $FVD(R)$) to obtain $VD_{i}$
and $VD_{i,j}$ (resp. $FVD_{i}$ and $FVD_{i,j}$) in linear time. We first
discuss the $RBCAC$ problem, followed by its generalized version, the $GRBCAC$
problem (where the penalties are assigned to each point).

##  4 Red-Blue Circular annulus cover ($RBCAC$) problem

A circular annulus ${\cal A}$ is said to be $feasible$ if it covers all the
red points in $R$. The objective of the $RBCAC$ problem is to compute a
$feasible$ annulus covering a minimum number of blue points in $B$. We observe
the following.

###### Observation 1

The colors of all the points lying on ${\cal C}_{out}(\cal A)$ $($resp. ${\cal
C}_{in}(\cal A))$ cannot be blue in an optimal solution.

Justification of the Observation 1: If the colors of all the points lying on
${\cal C}_{out}(\cal A)$ $($resp. ${\cal C}_{in}(\cal A))$ are blue then
keeping the center of ${\cal C}_{out}(\cal A)$ $($resp. ${\cal C}_{in}(\cal
A))$ fixed at the same position, we can decrease (resp. increase) the radius
of it to obtain another annulus with less number of blue points. Hence, at
least one of the point lying on ${\cal C}_{out}(\cal A)$ $($resp. ${\cal
C}_{in}(\cal A))$ must be red colored.

The distance of a point $p$ from a circle ${\cal C}$ is given by $|(|pc|-r)|$,
where $c$ and $r$ are the center and radius of $\cal C$, respectively.

###### Observation 2

If the centers of two intersecting circles ${\cal C}_{1}$ and ${\cal C}_{2}$
are separated by a distance $\epsilon$, then the distance of a point on ${\cal
C}_{2}$ from ${\cal C}_{1}$ is at most $2\epsilon$.

Justification of Observation 2: Let $c_{1}$ and $r$ (resp. $c_{2}$ and
${\mathscr{R}}$) be the center and radius of the circle ${\cal C}_{1}$ (resp.
${\cal C}_{2}$), respectively (see Fig. 1). Assume that $e$ is a point of
intersection of the circles ${\cal C}_{1}$ and ${\cal C}_{2}$. In $\triangle
c_{1}c_{2}e$, ${\mathscr{R}}\leq r+\epsilon$ (by triangle inequality). Hence,
$|gh|={\mathscr{R}}-|c_{2}g|={\mathscr{R}}-(r-\epsilon)\leq(r+\epsilon)-(r-\epsilon)=2\epsilon$.

Figure 1:  An instance of the Observation 2.

###### Definition 1

$\delta({\cal A})$: Compute the distances of all the points $a\in(R\cup B)$
from the ${\cal C}_{out}({\cal A})$ $($resp. ${\cal C}_{in}({\cal A}))$,
except the point ${a}$ that lies on ${\cal C}_{out}({\cal A})~{}($resp. ${\cal
C}_{in}({\cal A}))$. Among all such distances computed, the smallest one is
defined as $\delta({\cal A})$.

###### Definition 2

$ohp(a,VD(\\{a,b\\}))$: For any two points $a$ and $b$, we define $ohp(a,$
$VD(\\{a,b\\}))$ as the open half-plane of the partitioning line of the $a$
and $b$ in $VD(\\{a,b\\})$ that contains the point $a$.

###### Lemma 1

Let ${\cal C}_{out}(\cal A)~{}($resp. ${\cal C}_{in}(\cal A)))$ be defined by
three points. If one (resp. two) of these points, say $p_{i}$ (resp. $p_{i}$
and $p_{j}$), is (resp. are) blue, then we can shift the center of ${\cal A}$
and change its width to obtain an annulus, say ${\cal A}^{\prime}$, which
covers the same set of points that are covered by $\cal A$ except the blue
point(s) $p_{i}$ (resp. $p_{i}$ and $p_{j}$).

###### Proof

The following two cases need to be considered (see Observation 1).

(i)

One of the three defining points of a circle is blue:
Without loss of generality, we assume that ${\cal C}_{out}(\cal A)$ is defined
by three points, one of which, say $p_{i}$, is blue, and the other two, say
$q_{j}$ and $q_{k}$, are red (see Fig. 2(a)). In this case, ${\cal
C}_{in}(\cal A)$ is defined by a single point (see Property 1) of red color
(see Observation 1), and we take this point, say $q_{\ell}\in R$. We compute
$\delta(\cal A)$ for the annulus $\cal A$ (see Definition 1). We shift the
center of $\cal A$ towards the midpoint of $\overline{q_{j}q_{k}}$ by an
$\epsilon<\frac{{\delta}(\cal A)}{2}$, and create a new annulus ${\cal
A}^{\prime}$ centered at, say $c^{\prime}$, with $|c^{\prime}q_{j}|$ and
$|c^{\prime}q_{\ell}|$ as the radii of ${\cal C}_{out}({\cal A}^{\prime})$ and
${\cal C}_{in}({\cal A}^{\prime})$, respectively (see Fig. 2(b)). Since
$\epsilon<\frac{{\delta}(\cal A)}{2}$, $\cal A^{\prime}$ covers exactly the
same set of points that are covered by $\cal A$, except the blue point $p_{i}$
(see Observation 2). Hence, this proves our result if one of the three
defining points of ${\cal C}_{out}(\cal A)$ is a blue point.

Similarly, we can prove the result if ${\cal C}_{in}(\cal A)$ is defined by
three points: one blue point and two red points.

(ii)

Two of the three defining points of a circle are blue:
Without loss of generality, we assume that ${\cal C}_{out}(\cal A)$ is defined
by three points, one of which, say $q_{k}\in R$ is red, and the other two, say
$p_{i},~{}p_{j}\in B$, are blue (see Fig. 3(a)). The ${\cal C}_{in}(\cal A)$
must be defined by a single red point, say $q_{\ell}$ (see Property 1 and
Observation 1). We compute $\delta(\cal A)$ for the annulus $\cal A$ (see
Definition 1). We shift the center of $\cal A$ towards the red point $q_{k}$
along $\overline{cq_{k}}$ by a distance $\epsilon<\frac{{\delta}(\cal A)}{2}$
to create a new annulus ${\cal A}^{\prime}$ centered at, say $c^{\prime}$,
with $|c^{\prime}q_{k}|$ and $|c^{\prime}q_{\ell}|$ as the radii of ${\cal
C}_{out}({\cal A}^{\prime})$ and ${\cal C}_{in}({\cal A}^{\prime})$,
respectively (see Fig. 3(b)). Since $\epsilon<\frac{{\delta}(\cal A)}{2}$, the
annulus ${\cal A^{\prime}}$ covers all the points inside ${\cal A}$ except the
blue points $p_{i}$ and $p_{j}$ (see Observation 2). This proves the result.

Similarly, we can also show that the result is correct if ${\cal C}_{in}(\cal
A)$ is defined by three points: two blue points and one red point. ∎

Figure 2: Two red points ($q_{j}$, $q_{k}$) and one blue point ($p_{i}$)
define the ${\cal C}_{out}(\cal A)$. Figure 3: Two blue points ($p_{i}$,
$p_{j}$) and one red point ($q_{k}$) define the ${\cal C}_{out}(\cal A)$.

###### Lemma 2

If both ${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal A)$ are defined by
two points each, and one of these four defining points, say $p_{i}$ is blue,
then we can shift the center of $\cal A$ and change its width to obtain
another annulus, say $\cal A^{\prime}$, which covers the same set of points
that are covered by $\cal A$ except the blue point $p_{i}$.

###### Proof

It is similar to Case (ii) in the proof of Lemma 1. ∎

###### Lemma 3

If both ${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal A)$ are defined by
two points each, and one of the defining points of each circle, say $p_{i}$
(resp. $p_{j}$) on ${\cal C}_{out}(\cal A)~{}($resp. ${\cal C}_{in}(\cal A))$
is blue colored, then we can shift the center of $\cal A$ and change its width
to obtain another annulus, say $\cal A^{\prime}$, that contains only the
points that are covered by ${\cal A}$ except the blue point(s) $p_{i}$ and/or
$p_{j}$. In other words, we can generate an annulus $\cal A^{\prime}$
containing at least one blue point less than that of $\cal A$.

###### Proof

Let the red point that lies on ${\cal C}_{out}(\cal A)$ (resp. ${\cal
C}_{in}(\cal A)$) be $q_{i}$ (resp. $q_{j}$). The perpendicular bisector of
$\overline{p_{i}q_{i}}$ and $\overline{p_{j}q_{j}}$ intersect with each other
at the center $c$ of the annulus $\cal A$. We determine $\delta(\cal A)$ for
the annulus ${\cal A}$ (see Definition 1). There are three possible cases
depending on the positions of $q_{i}$ and $q_{j}$ with respect to the
perpendicular bisector of $\overline{p_{j}q_{j}}$, where the two points
$p_{j}$ and $q_{j}$ lies on the ${\cal C}_{in}(\cal A)$.

  * (i)

The two red points $q_{i}$ and $q_{j}$ lie on the two opposite sides of a
bisector $\overline{p_{j}q_{j}}$. We shift the center $c$ towards the red
point $q_{i}$ (see Fig. 4) by a distance $\epsilon<\frac{\delta(\cal A)}{2}$
and create another new annulus ${\cal A^{\prime}}$, centered at, say
$c^{\prime}$ with $|c^{\prime}q_{i}|$ and $|c^{\prime}q_{j}|$ as the radii of
the ${\cal C}_{out}(\cal A^{\prime})$ and ${\cal C}_{in}(\cal A^{\prime})$,
respectively. In this case, all the points in $\cal A$, except the blue points
$p_{i}$ and $p_{j}$, remain covered by $\cal A^{\prime}$.

  * (ii)

The two red points $q_{i}$ and $q_{j}$ lie on the same side of the bisector
$\overline{p_{j}q_{j}}$.
Depending on whether the same line or two different lines are the bisectors of
both the pairs ($p_{i}$, $q_{i}$) and ($p_{j}$, $q_{j}$), we have the
following two cases:

    * (a)

The perpendicular bisectors of the pairs ($p_{i}$, $q_{i}$) and ($p_{j}$,
$q_{j}$) are different lines (see Fig. 5).
We consider an arbitrary point, say $c^{\prime}$ at a distance
$\epsilon<\frac{\delta(\cal A)}{2}$ (see Definition 2) from $c$ inside the
region $ohp(p_{j},VD(\\{p_{j},q_{j}\\}))\cap ohp(q_{i},VD($
$\\{q_{i},p_{i}\\}))$ (see the shaded region in Fig. 5(a)), and create a new
annulus ${\cal A}^{\prime}$ centered at $c^{\prime}$ with $|c^{\prime}q_{i}|$
and $|c^{\prime}q_{j}|$ as the radii of ${\cal C}_{out}(\cal A^{\prime})$ and
${\cal C}_{in}(\cal A^{\prime})$, respectively. The annulus ${\cal
A}^{\prime}$ covers exactly the same set of points that are covered by ${\cal
A}$, except the blue points $p_{i}$ and $p_{j}$.

    * (b)

The perpendicular bisector of the pairs ($p_{i}$, $q_{i}$) and ($p_{j}$,
$q_{j}$) are represented by the same line (see Fig. 6).
We compute $\delta(\cal A)$ for ${\cal A}$ (see Definition 1). Then we choose
a point $c^{\prime}$ on $\overline{cq_{i}}$ at a distance
$\epsilon\leq\frac{\delta(\cal A)}{2}$ from $c$ and construct an annulus
${\cal A}^{\prime}$ centered at $c^{\prime}$ with $|c^{\prime}q_{i}|$ and
$|c^{\prime}q_{j}|$ as the radii of the ${\cal C}_{out}(\cal A^{\prime})$ and
${\cal C}_{in}(\cal A^{\prime})$, respectively (see Fig. 6). In this case, all
the blue points inside ${\cal A}$, except the blue point $p_{i}$, are covered
by ${\cal A}^{\prime}$. ∎

Figure 4: (a) Two red points $q_{i}$ and $q_{j}$ lie at the different sides of
the perpendicular bisector, (b) After shifting of the center, both the blue
points are removed from $\cal A^{\prime}$. Figure 5: (a) Two red points
$q_{i}$ and $q_{j}$ lie at the same sides of the perpendicular bisector, (b)
After shifting of the center, both the blue points are removed from $\cal
A^{\prime}$. Figure 6: (a) Perpendicular bisectors of $\overline{q_{i}p_{i}}$
and $\overline{q_{j}p_{j}}$ are the same, and the red points $q_{i}$ and
$q_{j}$ lie at the same sides of the perpendicular bisector, (b) After
shifting of the center, one blue point is removed from $\cal A^{\prime}$.

We describe our algorithm for the $RBCAC$ problem as follows.
Algorithm:
As a preprocessing task, we compute the Voronoi diagram $VD(R)$ and the
farthest-point Voronoi diagram $FVD(R)$ of the given set $R$ of red points. We
use two doubly connected edge lists ($DCEL$) to store $VD(R)$ and $FVD(R)$
separately, which need a linear space. Throughout our algorithm, we always
maintain an annulus ${\cal A}_{\min}$, which covers the minimum number of blue
points among the annuli generated so far.

We generate all the $feasible$ annuli in the following three cases, each one
satisfying one of the different conditions for an annulus to be defined (see
Property 1).

Case (A):

${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal A)$ are defined by three
points and one point lying on its boundary, respectively.
The following three sub-cases are possible depending on the color of the
defining points of ${\cal C}_{out}(\cal A)$.

Case (A.1):

All the points on the boundary of ${\cal C}_{out}(\cal A)$ are red.
Repeat the following tasks at each vertex, say $c$, of the $FVD(R)$ to compute
all the $feasible$ annuli $\cal A$ with ${\cal C}_{out}(\cal A)$ and ${\cal
C}_{in}(\cal A)$ passing through three red points and a single red point,
respectively.
We choose $c$ as the center of the ${\cal C}_{out}(\cal A)$, which passes
through the three red points and covers all the points in $R$ (see Property
2). Then we search $VD(R)$ to find out the Voronoi cell that contains the
center $c$, and we compute the closest red point, say $q_{i}$, from $c$ which
determines the radius of ${\cal C}_{in}(\cal A)$. Since $\cal A$ covers all
the red points in $R$, $A$ is a $feasible$ annulus. Next, we compute the
number of blue points lying inside $\cal A$. If the number of blue points
inside ${\cal A}$ is less than that of ${\cal A}_{\min}$, then we update the
${\cal A}_{\min}$ by taking $\cal A$ as the ${\cal A}_{\min}$.

Case (A.2):

${\cal C}_{out}(\cal A)$ has one blue point and two red points on its
boundary.
For each blue point $p_{i}\in B$, we execute the following tasks.
We update $FVD(R)$ to obtain $FVD_{i}$, i.e., $FVD(R\cup\\{p_{i}\\})$ in
linear time. We use $FR(i)$ to denote the region in $FVD_{i}$, which is
farthest from the blue point $p_{i}$. We choose each of the vertices of this
farthest region $FR(i)$ as a center $c$ of the ${\cal C}_{out}(\cal A)$ which
passes through $p_{i}$ along with two other red points and covers all the red
points in $R$. Next, we compute the ${\cal C}_{in}(\cal A)$ and the number of
blue points inside ${\cal A}$, in the same way as described in Case (A.1).
Then we compute another annulus ${\cal A^{\prime}}$ centered at $\epsilon$
distance away from that of $\cal A$, so that $\cal A^{\prime}$ covers exactly
the same set of points as covered by $\cal A$, except the blue point $p_{i}$
(see Lemma 1). So, for the annulus $\cal A$, we generate a corresponding
annulus $\cal A^{\prime}$ by eliminating the single blue point lying on ${\cal
C}_{out}(\cal A)$. We update the ${\cal A}_{\min}$, if $\cal A^{\prime}$
covers less number of blue points than ${\cal A}_{\min}$.

Case (A.3):

${\cal C}_{out}(\cal A)$ has two blue points and one red point on its
boundary.
In this case, for each pair of blue points ($p_{i}$, $p_{j}$), we execute the
following tasks.
We update $FVD(R)$ to obtain $FVD_{i,j}$, i.e., $FVD(R\cup\\{p_{i},p_{j}\\})$.
We consider only those vertices of $FVD_{i,j}$ as the center $c$ of ${\cal
C}_{out}(\cal A)$ which passes through two blue points $p_{i}$, $p_{j}$ and
one red point, say $q_{k}\in R$. Then, similar to Case (A.1), we compute the
${\cal C}_{in}(\cal A)$ and the number of blue points lying inside $\cal A$.
Next, in this case, we construct another annulus $\cal A^{\prime}$ centered at
an $\epsilon$ distance away from that of $\cal A$ (see Lemma 1)) to further
reduce the number of blue points covered. We update the ${\cal A}_{\min}$, if
$\cal A^{\prime}$ covers less number of blue points than ${\cal A}_{\min}$.

Case (B):

The ${\cal C}_{out}(\cal A)$ has one point on its boundary and ${\cal
C}_{in}(\cal A)$ has three points on its boundary.
Similar to Case (A), it has the following three sub-cases depending on the
color of the defining points of ${\cal C}_{in}(\cal A)$.

Case (B.1):

The ${\cal C}_{in}(\cal A)$ has three red points on its boundary.
Repeat the following tasks at each vertex, say $c$, of the $VD(R)$ to compute
all the $feasible$ annuli $\cal A$ with ${\cal C}_{in}(\cal A)$ and ${\cal
C}_{out}(\cal A)$ passing through three red points and a single red point,
respectively.
We choose $c$ as the center of the ${\cal C}_{in}(\cal A)$, which passes
through the three red points and does not contain any other points in $R$ (see
Property 2). Then we search in $FVD(R)$ to find out the Voronoi site (a red
point), say $q_{k}\in R$ so that the farthest region of $q_{k}$ in $FVD(R)$
contains the point $c$. The farthest red point from $c$ is $q_{k}$, which
determines the radius of ${\cal C}_{out}(\cal A)$. Since the annulus $\cal A$
covers all the red points in $R$, $\cal A$ is a $feasible$ annulus. We compute
the number of blue points lying inside $\cal A$, and if necessary, we update
${\cal A}_{\min}$.

Case (B.2):

The ${\cal C}_{in}(\cal A)$ has two red points and one blue point on its
boundary.
In this case, for each blue point $p_{i}\in B$, we execute the following
tasks.
We update $VD(R)$ to obtain $VD_{i}$, i.e., $VD(R\cup\\{p_{i}\\})$, and let
$VC(i)$ be the Voronoi cell of the site (blue point) $p_{i}$ in $VD_{i}$. We
choose each vertex of the boundary of $VC(i)$ as a center $c$ of ${\cal
C}_{in}(\cal A)$ which passes through $p_{i}$ and two other red points in $R$,
and does not contain any other red points in $R$. Next, we compute ${\cal
C}_{out}(\cal A)$ and the number of blue points inside $\cal A$ in the same
way as described in Case (B.1). Once we generate the annulus $\cal A$, we
compute another one, say ${\cal A}^{\prime}$ centered at an $\epsilon$
distance away from that of ${\cal A}$ so that $\cal A^{\prime}$ covers exactly
the same set of points that are covered by $\cal A$, except the blue point
$p_{i}$ (see Lemma 2). If $\cal A^{\prime}$ covers less number of blue points
than ${\cal A}_{\min}$, we update ${\cal A}_{\min}$.

Case (B.3):

The ${\cal C}_{in}(\cal A)$ has one red point and two blue points on its
boundary.
In this case, we do the following tasks for each pair of blue points ($p_{i}$,
$p_{j}$)$\in B\times B$.
We update $VD(R)$ to obtain $VD_{i,j}$, i.e., $VD(R\cup\\{p_{i},p_{j}\\})$. We
consider only those vertices of $VD_{i,j}$ as the center $c$ of ${\cal
C}_{in}(\cal A)$ which passes through two blue points $p_{i}$, $p_{j}$ and a
red point, say $q_{k}\in R$. Then, we use the $FVD(R)$ to find out the
farthest red point from $c$, and thus we obtain ${\cal C}_{out}(\cal A)$. In
this case, we also generate an annulus ${\cal A}^{\prime}$ whose center is at
an $\epsilon$ distance away from that of ${\cal A}$ (see Lemma 3). Then we
count the number of blue points inside $\cal A^{\prime}$ and update ${\cal
A}_{\min}$, if necessary.

Case (C):

The ${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal A)$ have two points on
their boundaries.
Depending on the color of the defining points of ${\cal C}_{in}(\cal A)$ and
${\cal C}_{out}(\cal A)$, we consider the following exhaustive four sub-cases.

Case (C.1):

The two points on the boundaries of both ${\cal C}_{in}(\cal A)$ and ${\cal
C}_{out}(\cal A)$ are red.
The center of the annulus $\cal A$ must lie on the edges of the $VD(R)$ and
$FVD(R)$ (see Property 3) so that ${\cal C}_{out}(\cal A)$ and ${\cal
C}_{in}(\cal A)$ pass through two points. This implies that the center of all
such annuli is the points of intersection of the edges of $VD(R)$ with that of
$FVD(R)$. At each such point of intersection, we compute ${\cal C}_{in}(\cal
A)$ and ${\cal C}_{out}(\cal A)$ which satisfy the Property 3 and thus $\cal
A$ is the $feasible$ annulus. We count the number of blue points inside $\cal
A$ and update ${\cal A}_{\min}$, if necessary.

Case (C.2):

The ${\cal C}_{out}(\cal A)$ has one red point and one blue point on its
boundary, whereas both the points on ${\cal C}_{in}(\cal A)$ are red.
In this case, for each blue point $p_{i}\in B$, we execute the following.
We update $FVD(R)$ to obtain $FVD_{i}$, i.e., $FVD(R\cup\\{p_{i}\\})$. We
choose the farthest region (denoted by $FR(i)$) of the blue point $p_{i}$ in
$FVD_{i}$ and find out the points of intersection of the boundary of $FR(i)$
with the edges of $VD(R)$. We choose each such point of intersections as the
center $c$ of ${\cal C}_{out}(\cal A)$, which passes through $p_{i}$ and a red
point in $R$. We use the $VD(R)$ to obtain an empty circle $\cal C$ centered
at $c$ passing through two red points in $R$, and we take ${\cal C}$ as the
${\cal C}_{in}(\cal A)$. Then we construct an annulus ${\cal A}^{\prime}$
whose center is $\epsilon$ distance away from that of $\cal A$ (see Lemma 2)
so that $\cal A^{\prime}$ contains exactly the same set of points that are
covered by $\cal A$, except the blue point $p_{i}$. Then we count the number
of blue points inside $\cal A^{\prime}$, and if it is less than ${\cal
A}_{\min}$, we update the ${\cal A}_{\min}$.

Case (C.3):

The ${\cal C}_{in}(\cal A)$ has one red point and one blue point on its
boundary, whereas both the points on ${\cal C}_{out}(\cal A)$ are red.
In this case, we execute the following for each blue point $p_{i}\in B$.
We update $VD(R)$ to obtain $VD_{i}$, i.e., $VD(R\cup\\{p_{i}\\})$. In
$VD_{i}$, we choose the Voronoi cell $VC(i)$ of the blue point $p_{i}$, whose
boundary consists of at most $(n-1)$ edges. Next, we find out the point of
intersection of the boundary of $VC(i)$ with the edges of $FVD(R)$. We choose
each such point of intersections as the center $c$ of ${\cal C}_{in}(\cal A)$
that passes through $p_{i}$ and a red point, say $q_{j}\in R$. We use the
$FVD(R)$ to obtain a circle ${\cal C}_{out}(\cal A)$ centered at $c$, which
covers all the red points in $R$ and passes through two red points in $R$.
Then we construct an annulus ${\cal A}^{\prime}$ whose center is $\epsilon$
distance away from that of $\cal A$ (see Lemma 2) so that the $\cal
A^{\prime}$ contains exactly the same set of points that are covered by $\cal
A$, except the blue point $p_{i}$. Then, we count the number of blue points
inside $\cal A^{\prime}$ and update ${\cal A}_{\min}$, if necessary.

Case (C.4):

Both the ${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal A)$ have one red
point and one blue point on their boundaries.
In this case, for each pair of blue points ($p_{i}$, $p_{j}$)$\in B\times B$,
we do the following.
Compute the $VD_{i}$, i.e., $VD(R\cup\\{p_{i}\\})$ and the $FVD_{j}$, i.e.,
$FVD(R\cup\\{p_{j}\\})$. Choose the Voronoi cell $VC(i)$ of the blue point
$p_{i}$ in the $VD_{i}$ that has at most $(n-1)$ edges along the boundary of
$VC(i)$. Also consider the $FR(j)$, the farthest region of the blue point
$p_{j}$ in $FVD_{j}$. Then we find the points of intersections between the
boundaries of the cells $VC(i)$ and $FR(j)$. which are at most $2(n-1)$ in
number. We choose these points of intersections as the center of the annulus.
The ${\cal C}_{out}(\cal A)$ (resp. ${\cal C}_{in}(\cal A)$) passes through
$p_{j}$ (resp. $p_{i}$) and a red point, say $q_{j}\in R$ (resp. $q_{i}\in
R$). Then we construct another annulus ${\cal A}^{\prime}$ centered at
$\epsilon$ distance away from that of $\cal A$ (see Lemma 3), so that the
$\cal A^{\prime}$ contains exactly the same set of points covered by $\cal A$,
except the blue point $p_{j}$. We count the number of blue points inside $\cal
A^{\prime}$, and if it is less than ${\cal A}_{\min}$, then we update the
later one.

Finally we report the annulus ${\cal A}_{\min}$.

Remarks: Note that as a special case, one of the circles (outer or inner) may
be defined by two diametrically opposite points, and the other one is defined
by a single point. There are two possibilities as follows:

(i)

${\cal C}_{out}(\cal A)$ is defined by two diametric points:
To generate an annulus $\cal A$ with ${\cal C}_{out}(\cal A)$, we first
compute the diameter (i.e., the farthest pair) of the point-set $R$ from the
$FVD(R)$ and check whether all the points in $R$ can be covered by a circle
centered at the midpoint of such a farthest pair. If so, then we take that
circle as ${\cal C}_{out}(\cal A)$ and compute the corresponding ${\cal
C}_{in}(\cal A)$ in a similar way as described above in the algorithm.
Similarly, we can also construct the annulus $\cal A$ with its ${\cal
C}_{in}(\cal A)$ being defined by a single red point and a single blue point
$p_{i}$ using the $FVD_{i}$, as described above in our algorithm.

(ii)

${\cal C}_{in}(\cal A)$ is defined by two diametric points:
We consider the two sites (red points), say $q_{i},q_{j}\in R$ of the two
adjacent Voronoi cells in the $VD(R)$, and choose the point $c$ on the edge
which is equidistant from this pair. We take the $c$ as a center of $\cal A$
and then find out the farthest red point from $c$ using $FVD(R)$, and follow
the procedure in the algorithm to generate $\cal A$. Similarly, we handle the
case if one of the defining points of ${\cal C}_{in}(\cal A)$ is red.

Proof of correctness: The correctness of the algorithm is based on the
following claim.

###### Claim 1

Our algorithm generates all the $feasible$ annuli.

###### Proof

Our algorithm always generates all possible annuli $\cal A$ following the
Property 1 so that it covers all the red points in $R$. When one or two of the
defining points of $\cal A$ are blue, we generate its corresponding annulus
$\cal A^{\prime}$ in such a way that $\cal A^{\prime}$ discards such blue-
colored defining points without eliminating any red ones. Hence, our algorithm
generates all possible annuli which are $feasible$. ∎

Since our algorithm chooses the $feasible$ annulus (${\cal A}_{\min}$) that
covers the minimum number of points, it provides the optimal result.

###### Theorem 1

The algorithm for the $RBCAC$ problem computes the optimal result in
$O(m^{2}n(m+n))$ time and linear space.

###### Proof

We have given the algorithm and proved the correctness above. Now we discuss
the time complexity of the algorithm, which is determined by the following
tasks:

  * (i)

The preprocessing task, i.e., the computation of $VD(R)$ and $FVD(R)$ needs
$O(n\log n)$ time.

  * (ii)

We update one of the $VD(R)$ and $FVD(R)$ to obtain the Voronoi diagram or
farthest-point Voronoi diagram for the point-set $R\cup\\{p_{i}\\}$,
$R\cup\\{p_{i},p_{j}\\}$ in $O(n)$ time.

  * (iii)

In the $VD(R)$ (resp. $FVD(R)$), we search for the Voronoi cell (resp.
farthest region) in which the center $c$ of ${\cal C}_{out}(\cal A)$ (resp.
${\cal C}_{in}(\cal A)$) lies on, and it needs $O(\log n)$ time. Then we
compute the corresponding ${\cal C}_{in}(\cal A)$ (resp. ${\cal C}_{out}(\cal
A)$) in constant time.

  * (iv)

The computation of the $\delta(\cal A)$ needs to determine the distances of
all the red and blue points from ${\cal C}_{out}{(\cal A)}$ and ${\cal
C}_{out}{(\cal A)}$. Hence, it requires $O(m+n)$ time. In other words, the
computation of $\epsilon$ takes $O(m+n)$ time.

  * (v)

Counting the number of blue points lying inside $\cal A$ or $\cal A^{\prime}$
needs $O(m)$ time.

The algorithm needs $O(n\log n)$ preprocessing time. Now, the number of
vertices in $FVD(R)$ as well as $VD(R)$ are $O(n)$. Case (A.1), needs
$O(n(m+\log n))$ time to choose ${\cal A}_{\min}$. In Case (A.2), $FVD(R)$ is
updated $m$ times to compute $FVD_{i}$ for each $m$ different blue points
$p_{i}\in B$. This case needs $O(mn(m+n+\log n))$ time, i.e., $O(mn(m+n))$. In
Case (A.3), we compute $m\choose 2$ number of $FVD_{i,j}$ by updating
$FVD(R)$. Hence, Case (A.3) requires $O(m^{2}n(m+n))$ time.
Similarly, Case (B.1) needs $O(n(m+\log n))$ time. Cases (B.2) and (B.3) need
the same time as that of Case (A.2) and Case (A.3), respectively.
Case (C.1) needs $O(n^{2}(m+n))$ time to compute the annulus with the minimum
number of blue points inside it since there are $O(n^{2})$ number of possible
points of intersections of the edges of $VD(R)$ with that of $FVD(R)$. Each of
Case (C.2) and Case (C.3) needs $O(n^{2}m)$ time to compute the annulus with
the minimum number of blue points inside it. In Case (C.4), the number of
centers of all possible annuli $\cal A$ whose outer (resp. inner) circle is
defined by $p_{i}$ (resp. $p_{j}$), is at most $2n$ which is determined by the
points of intersection of boundaries of $VC(i)$ and $FR(j)$. Hence, it needs
$O(nm)$ time to count the number of blue points inside all possible annuli
whose ${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal A)$ are defined by the
blue points $p_{i}$ and $p_{j}$. There are $m\choose 2$ pairs of blue points;
hence, it needs $O(m^{2}n(m+n))$ time to compute the optimal annulus. Hence,
the overall time complexity of the algorithm is $O(m^{2}n(m+n))$.
We can reuse the same storage space to store each case’s different $FVD_{i}$
(resp. $VD_{i}$). It is also true for $FVD_{i,j}$ (resp. $VD_{i,j}$). Hence,
it needs linear space. ∎

##  5 Generalized Red-Blue Circular Annulus Cover ($GRBCAC$) problem

The given bichromatic points in ${\mathbb{R}}^{2}$ are associated with
different penalties. We compute an annulus $\cal A$ that has Property 1, and
we generate them with all possible color combinations of their defining points
as stated in each of the different cases in the algorithm for the $RBCAC$
problem (discussed in Section 4). However, note that to have a minimum
penalty, not all the red points need to lie inside $\cal A$. For this reason,
we need to generate all possible annuli exhaustively, except the case where
all the defining points of ${\cal C}_{out}(\cal A)$ or ${\cal C}_{in}(\cal A)$
are blue (see Observation 1). This method for this problem gives the following
result.

###### Lemma 4

If one of the two circles ${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal
A)$, is defined by three points, then we can compute the one with a minimum
penalty in $O(n(m+n)^{3}\log(m+n))$ time.

###### Proof

If ${\cal C}_{out}(\cal A)$ is defined by three points, then we can compute
all possible such outer circles in $O(n(m+n)^{2})$ ways since at least one of
the defining points of the ${\cal C}_{out}(\cal A)$ must be red. For each
center $c$ of ${\cal C}_{out}(\cal A)$, we sort all the points in $R\cup B$
with respect to their distances from $c$ in $O((m+n)\log(m+n))$ time, and then
compute ${\cal C}_{in}(\cal A)$ so that the annulus $\cal A$ has the minimum
penalty. Computation of such ${\cal C}_{in}(\cal A)$ needs $O(m+n)$ time.
Hence, we need $O(n(m+n)^{3}\log(m+n))$ time.

Similarly, if ${\cal C}_{in}(\cal A)$ is defined by three points, we need the
same amount of time to generate the annulus with the minimum penalty. Hence
the result follows. ∎

###### Lemma 5

If both the circles ${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal A)$, are
defined by two points, then we can compute the one with a minimum penalty in
$O(n^{2}(m+n)^{3})$ time.

###### Proof

Each of the two circles ${\cal C}_{out}(\cal A)$ and ${\cal C}_{in}(\cal A)$
have at least one red point that defines it, so we have $O(n^{2}(m+n)^{2})$
possible positions of the center of the annulus ${\cal A}$. For each such
annulus $\cal A$, we compute the points ($\in$ $R\cup B$) lying inside $\cal
A$ and its penalty in $O(m+n)$ time. Hence, our result is proved. ∎

We obtain the following result by combining Lemma 4 and Lemma 5.

###### Theorem 2

The optimal solution to the $GRBCAC$ problem can be computed in
$O(n^{2}(m+n)^{3})$ time and linear space.

##  6 Concluding Remarks

We have studied circular annulus cover problems for a given bichromatic point-
set in two dimensions. Each red point in the bichromatic point-set has a non-
covering penalty, whereas the blue point has a covering penalty. We design
polynomial-time algorithms for each variation. Improving the running time of
the generalized annulus cover problems as well as designing the algorithms for
these problems in the higher dimensions remains challenging as a future work.

## References

  * [1] Abellanas, M., Hurtado, F., Icking, C., Ma, L., Palop, B., Ramos, P.A.: Best fitting rectangles.  In: The European Workshop on Computational Geometry (2003)
  * [2] Abidha, V., Ashok, P.: Red blue set cover problem on axis-parallel hyperplanes and other objects.  arXiv preprint arXiv:2209.06661 (2022)
  * [3] Abidha, V.P., Ashok, P.: Geometric separability using orthogonal objects.  Information Processing Letters 176, 106245 (2022)
  * [4] Bae, S.W.: Computing a minimum-width square annulus in arbitrary orientation.  Theoretical Computer Science 718, 2–13 (2018)
  * [5] Bae, S.W., Baral, A., Mahapatra, P.R.S.: Maximum-width empty square and rectangular annulus.  Computational Geomerty 96, 101747 (2021)
  * [6] Barequet, G., Goryachev, A.: Offset polygon and annulus placement problems.  Computational Geometry 47(3), 407–434 (2014)
  * [7] Bereg, S., Cabello, S., Díaz-Báñez, J.M., Pérez-Lantero, P., Seara, C., Ventura, I.: The class cover problem with boxes.  Computational Geometry 45(7), 294–304 (2012)
  * [8] de Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational geometry: Algorithms and Applications.  Springer (2008)
  * [9] Bitner, S., Cheung, Y., Daescu, O.: Minimum separating circle for bichromatic points in the plane.  In: 2010 International Symposium on Voronoi Diagrams in Science and Engineering, pp. 50–55. IEEE (2010)
  * [10] Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.: On the red-blue set cover problem.  Tech. rep., Sandia National Lab.(SNL-NM), Albuquerque, NM (United States); Sandia (1999)
  * [11] Chan, T.M., Hu, N.: Geometric red–blue set cover for unit squares and related problems.  Computational Geometry 48(5), 380–385 (2015).  Special Issue on the 25th Canadian Conference on Computational Geometry (CCCG)
  * [12] Díaz-Báñez, J.M., Hurtado, F., Meijer, H., Rappaport, D., Sellarès, J.A.: The largest empty annulus problem.  International Journal of Computational Geometry & Applications 13(4), 317–325 (2003)
  * [13] Gluchshenko, O., Hamacher, H.W., Tamir, A.: An optimal $O(n\log n)$ algorithm for finding an enclosing planar rectilinear annulus of minimum width.  Operations Research Letters 37(3), 168–170 (2009)
  * [14] Madireddy, R.R., Nandy, S.C., Pandit, S.: On the geometric red-blue set cover problem.  In: International Workshop on Algorithms and Computation, pp. 129–141. Springer (2021)
  * [15] Maji, S., Pandit, S., Sadhu, S.: Red-blue rectangular annulus cover problem.  In: Frontiers of Algorithmics - 17th International Joint Conference, IJTCS-FAW 2023 Macau, China, August 14-18, 2023, Proceedings, vol. 13933, pp. 195–211. Springer (2023)
  * [16] Mukherjee, J., Mahapatra, P.R.S., Karmakar, A., Das, S.: Minimum-width rectangular annulus.  Theoretical Computer Science 508, 74–80 (2013)
  * [17] Paul, R., Sarkar, A., Biswas, A.: Finding the maximum empty axis-parallel rectangular annulus.  In: International Workshop on Combinatorial Image Analysis, pp. 139–146 (2020)
  * [18] Preparata, F.P., Shamos, M.I.: Computational Geometry - An Introduction.  Texts and Monographs in Computer Science. Springer (1985).  DOI 10.1007/978-1-4612-1098-6
  * [19] Roy, U., Zhang, X.: Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error.  Computer-Aided Design 24(3), 161–168 (1992)
  * [20] Shanjani, S.H.: Hardness of approximation for red-blue covering.  In: Canadian Conference on Computational Geometry, pp. 39–48 (2020)