# Designing A Sustainable Marine Debris Clean-up Framework without Human
Labels

Raymond Wang<EMAIL_ADDRESS>Davis Institute for AI, Colby
CollegeWatervilleMaineUSA ,  Nicholas R. Record<EMAIL_ADDRESS>Bigelow
Laboratory for Ocean SciencesEast BoothbayMaineUSA ,  D. Whitney King
<EMAIL_ADDRESS>Department of Chemistry, Colby CollegeWatervilleMaineUSA and
Tahiya Chowdhury<EMAIL_ADDRESS>Davis Institute for AI, Colby
CollegeWatervilleMaineUSA

(2018)

###### Abstract.

Marine debris poses a significant ecological threat to birds, fish, and other
animal life. Traditional methods for assessing debris accumulation involve
labor-intensive and costly manual surveys. This study introduces a framework
that utilizes aerial imagery captured by drones to conduct remote trash
surveys. Leveraging computer vision techniques, our approach detects,
classifies, and maps marine debris distributions. The framework uses Grounding
DINO, a transformer-based zero-shot object detector, and CLIP, a vision-
language model for zero-shot object classification, enabling the detection and
classification of debris objects based on material type without the need for
training labels. To mitigate over-counting due to different views of the same
object, Scale-Invariant Feature Transform (SIFT) is employed for duplicate
matching using local object features. Additionally, we have developed a user-
friendly web application that facilitates end-to-end analysis of drone images,
including object detection, classification, and visualization on a map to
support cleanup efforts. Our method achieves competitive performance in
detection (0.69 mean IoU) and classification (0.74 F1 score) across seven
debris object classes without labeled data, comparable to state-of-the-art
supervised methods. This framework has the potential to streamline automated
trash sampling surveys, fostering efficient and sustainable community-led
cleanup initiatives.

Remote sensing, object detection, sustainable computing, ecosystem
conservation.

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: ACM SIGCAS/SIGCHI Conference on Computing and
Sustainable Societies; July 08–11, 2024; New Delhi, India††price: 15.00††isbn:
978-1-4503-XXXX-X/18/06††ccs: Computing methodologies Computer vision††ccs:
Applied computing

##  1\. Introduction

The oceans, covering 71% of the earth’s surface, serve as a vast repository of
biodiversity and sustain marine life. This precious ecosystem is threatened as
various human-made materials, known as ‘marine debris’, enter the ocean.
Approximately 75 to 199 tonnes of plastic is currently found in our oceans,
resulting in severe environmental, social, economic, and health consequences,
according to a report by the United Nations Environment Programme (UNE, 2022).
The accumulation of these marine debris objects in a specific region is
exacerbated by ocean currents and weather patterns, often linking the marine
debris problem to climate change trends for particular oceanic regions
(Lincoln et al., 2022). Marine debris includes a spectrum of persistent solid
materials such as metals, plastics, rubber, fishing gear, and other discarded
items that are manufactured or processed, and abandoned in the marine
environment. Government, industry, and community stakeholders are developing
marine debris action plans tailored to the local community’s needs, which
involve monitoring, coordination, collection, and removal efforts. However,
implementing such initiatives can be expensive, both in terms of funding and
human efforts.

Figure 1. Beverage bottle, fishing gear and other marine debris along a beach
on Allen Island in Maine, USA where the data was collected.

An aerial image with beverage bottle, fishing gear, and other marine debris
found along a beach on Allen Island in Maine, USA where the data was
collected.

Figure 2. System diagram of the proposed framework.

System diagram of the proposed framework with four steps: trash detection,
classification, duplicate removal and map visualization.

To accelerate monitoring and clean-up efforts, previous research has developed
remote sensing and computer vision-based approaches to detect and classify
marine debris objects. Multi-spectral measurements available from image
sensors have been used to develop spectral indices to distinguish plastic and
other processed materials from natural materials such as vegetation and water
(Garaba et al., 2020; Knaeps et al., 2021; Tasseron et al., 2021; Freitas et
al., 2021). With recent advancements of deep learning in computer vision
tasks, prior research has used object segmentation and detection approaches
for automating marine debris monitoring from aerial imagery captured by
satellite and drones (Martin et al., 2021; Iordache et al., 2022; Pfeiffer et
al., 2022). However, identifying marine debris objects from an image taken
from the top view and classifying it based on appropriate material type still
remains challenging (Winans et al., 2023). Most debris objects are often
obscured by natural objects in the background (rocks, grass, bushes,
wetlands), making it difficult to distinguish debris objects from the
background land cover (see Figure 1). Additionally, marine debris objects can
be highly diverse in shape, size, color, and texture which is dependent on
economic, industry, and marine activities of the specific region. To resolve
this challenge, human interpretation is typically leveraged as a sustainable
approach to detect and identify debris items to monitor an area without making
a physical visit (Moy et al., 2018; Merlino et al., 2021).

Typical machine learning-based solutions rely on human-provided decisions
about the location and material type as ground truth to train algorithms to
identify similar items from images collected in the future. However, human
annotation is a time-consuming, tedious process that can take up to months,
hence is costly to scale across large geographic regions (Moy et al., 2018).
Additionally, while relying on an expert annotator familiar with the
geographical, environmental, and economic context is desirable, the
effectiveness of such solutions remains limited to a specific dataset or
geographic region. As a result, most solutions are designed around training
custom ML-based frameworks that involve data pre-processing, annotation, model
training, and validation procedures led by researchers and technical teams,
which are often challenging to adopt by local communities. There is a need to
design a sustainable, user-friendly framework for marine debris detection and
cleanup that combines state-of-the-art computer vision tools and local
stakeholders’ knowledge.

To address this gap, this paper introduces a framework that detects,
classifies, and maps the distribution of marine debris objects facilitating
longitudinal monitoring and expedited clean-up efforts. As an alternative to
cost-prohibitive ground-level sampling and time-consuming human inspection
methods, our approach leverages existing computer vision models trained on
large-scale image data to monitor marine debris accumulation over time.
Specifically, we used Grounding DINO, an object detection model to query
specific visual concepts related to custom marine debris objects in a coastal
region such as islands and beaches without manual annotation. To streamline
collection efforts, debris objects are categorized using an open-set image
classifier that can be prompted to classify images with natural language
debris categories. To improve the accessibility of the framework, we have
designed an interactive web application that enables users to add aerial
images, and analyze and map the spatial distribution of debris to co-ordinate
the clean-up initiatives effectively. We evaluate the framework using a novel
aerial image dataset captured via drone on a small coastal island, and we also
discuss future directions for local and global scale initiatives. We have made
the framework, web application, and dataset used in this study publicly
available111https://github.com/Tahiya31/Trash_Track.

##  2\. Method

In this paper, we present a framework for detecting marine debris objects from
drone images, classify them by object types, and visualize their location
distribution on a map. A system diagram of different components of the
framework is presented in Figure 2. We describe the four key components of the
framework in this section: object detection, classification, duplicate
removal, and map visualization.

###  2.1. Detection using Grounding DINO

####  2.1.1. Zero-shot object detection

Existing works on marine debris or waste detection formulate this problem as
object detection, which is a computer vision task to identify certain objects
in an image. The training procedure for such models often involves training
supervised detection models using a collection of annotated images labeled by
a human, called ‘training data’. Manual annotation is time-consuming and does
not scale well for diverse geographic regions as marine debris categories can
vary widely depending on social, economic, and geographic factors. Since our
objective is to develop an automated pipeline with minimal annotation efforts,
we relied on existing models trained on large-scale image datasets for object
detection tasks in a zero-shot learning setting. Zero-shot object detector is
trained on large image datasets with the intention that it can learn to
recognize objects unseen during the training. Traditional object detection
models require to be trained explicitly on examples of images containing
object categories that it will need to detect in the evaluation phase, in a
supervised learning setting. On the other hand, a zero-shot detector leverages
its knowledge block obtained from pre-training on large-scale training data
for open-set object detection without labels when encountered by novel
categories and conditions.

To detect marine debris objects present in the drone images, we selected
Grounding DINO, a zero-shot object detector (Liu et al., 2023). It is designed
for object detection in open set scenarios so that arbitrary objects can be
detected based on human-provided inputs such as a category or a label. We
select Grounding DINO for our purpose as it leverages cross-modal information
from vision and language for open set concept generalization. As a result,
Grounding DINO can generate object region proposals, indicating an object’s
location within an image, based on human-provided class labels, and detect
novel categories.

####  2.1.2. Parameters for Grounding DINO

Our objective is to detect the objects relevant to marine debris from the
images. Following the official implementation of Grounding DINO, we provided a
set of image and text pairs as inputs to the model. The text input is used as
a query command to detect all instances of that category in each image, which,
in this case, was ‘all trash’. Since our dataset consists of drone images
captured in coastal islands, the background landscape contained various
natural objects such as woodland, water, rocks, etc. Our preliminary analysis
showed that rocks were often categorized as trash due to lighting and angle,
hence increasing false positives. To resolve this, we employed a second query
for ‘all rocks’. Once the detected objects were retrieved, we filtered and
removed the instances of trash that overlapped with where rocks were detected
to lower the false positive rates resulting from the background landcover.

The Grounding DINO provides detected objects and their labels based on a user-
provided threshold. Each detected box is accompanied by a similarity score to
indicate its similarity to each of the text queries. The box threshold is used
to prune the objects detected in an image (maximum limit is 900 objects) that
fall below the threshold, which is analogous to a confidence score for an
object. Similarly, a text threshold can be set so that final labels for a
detected object are chosen based on the threshold. We experimented with
different threshold levels as we observed that different levels were effective
for different categories of debris objects. In our experimentation with the
dataset, we empirically found 0.3 and 0.15 for both text and box thresholds to
be effective as they provided detection performance comparable to human
detection. We ran the object detection queries with these two threshold levels
twice and combined the detection results to leverage their individual
effectiveness.

Figure 3. Examples of detections obtained from the raw query ”all trashes.”
Detections are highlighted using red bounding boxes to indicate the identified
areas within the dataset.

Two example for misclassification where detections obtained from the raw query
”all trashes” are shown. Detections are highlighted using red bounding boxes
to indicate the identified areas.

####  2.1.3. Improving Detection Performance

Note that we have used Grounding DINO’s pre-trained object concepts to detect
objects in the drone image. However, we observed two issues with this approach
that increased the number of false positives. First, the bounding boxes
returned by the detection block often overlap with each other, resulting in
over-prediction with the same piece of trash being detected multiple times. To
reduce the over-prediction rate, Objects with significant overlap (40% and
higher) between the boxes that bounded them, were filtered and removed.

The second issue involved classifying the entire image as an object. The drone
image, captured at a 44.7-meter average altitude and at 5472 x 3648 pixel
image resolution, could cover an area that contained many pieces of debris
objects that would appear small in the image. Bounding boxes larger than half
the size of the image were removed, to lower the mis-classification resulting
from the entire image being detected as a debris object. These modification
choices helped to customize the general-purpose zero-shot object detector to
our specific problem domain without having to train our own model while
minimizing issues related to redundancy and mis-classification. Figure 3 shows
two examples of mis-classification in the object detection step.

###  2.2. Classification using CLIP

####  2.2.1. Zero-shot classification

The second step in our pipeline is classifying the detected objects into
relevant object categories. To classify the detected marine debris objects, we
utilized CLIP (Radford et al., 2021), a zero-shot image classifier. CLIP uses
a vision-language transformer pre-trained on image-text pairs, enabling
general-purpose classification capability. As a result, given an image, the
model can provide the most relevant text snippet describing the content of the
image, without having to train a model. We selected CLIP due to its
adaptability to classify new classes that are unseen during training using
natural language instruction such as class names. For this step, input images
are created as image snippets cropped based on the bounding boxes in the
object detection step. CLIP takes image and text pairs as input where text
input is used as a list of possible class names for labeling the image. The
class label with the highest probability is chosen as the final label for the
object.

####  2.2.2. Labeling schema for classification

To come up with a labeling schema for the classes that are appropriate for our
specific problem domain, we relied on a manual marine debris audit conducted
on the site where the drone images of this study were collected. The manual
audit was performed by a group of researchers and volunteers as part of a
community effort to track the spatial and temporal distribution of marine
debris accumulation on coastal islands. We consulted their manual survey to
develop a set of category labels that we can use as a natural language query
for the CLIP model. Two of the authors further validated the choice of
category labels by manually inspecting a random sub-sample of the images to
merge, rename, and modify category names as necessary. We came up with 7 class
categories: wood, cage, fishing gear, nature, plastic, metal, and wheel (see
Table 1 for examples from each class category).

Table 1. Examples of debris objects for each class

Category Name | Example
---|---
Wood | Stray logs, boats
Cage | Lobster traps
Fishing Gear | Fishing nets, lobster buoys, ropes
Nature | Bushes, rocks, moss, branches
Plastic | Beverage bottles, caps, bags, cups
Metal | Aluminium, tin cans
Wheel | Tire, wheels

A table with example objects from the 7 debris object categories.

Note that our labeling schema is inspired by commonly found marine debris on
coastal islands. In particular, the economy of the areas where the data for
this study was collected is dependent on fishing activities and a large
quantity of the debris comes from fishing gear used by the fishing boats
operating in the area. Another consideration when designing the labeling
schema was to sort the detected materials for proper recycling, once
collected. We consulted with representatives from the local community group
volunteering in the marine debris removal process to understand how to design
our framework to easily integrate it into their existing workflow. In the case
of marine debris, some trash objects are heavier than others (each lobster
trap weighs between 45 to 60 pounds), which often needs multiple volunteers to
collect them. On the other hand, small plastic items (bottles, bags) can be
retrieved by an individual volunteer easily. As a result, volunteers need to
coordinate to ensure that they can allocate ample human resources to
adequately cover the spatial distribution of the debris. Knowing the material
type can help in this coordination as material type can be used as a good
proxy for the expected weight of the object. Based on this finding, we
designed the current labeling schema focusing on the material type to aid in
the decision-making process of allocating resources such as volunteers and
vehicles to both collect and transport the debris objects to recycling
facilities located on the mainland. Figure 4 shows example detection from each
of the seven classes.

###  2.3. Detecting duplicate objects

Our drone images are captured using a predetermined flight path at a sampling
rate of 30 frames per second. Due to the relatively high sampling rate, we
observed that a particular piece of debris object appeared in multiple
consecutive images resulting in duplicate items. To mitigate this issue, we
developed a duplicate removal approach to avoid over-counting debris object
instances.

Our approach is based on two steps: 1) extracting distinctive features from
the detected object, and 2) comparing different detected objects to identify
identical objects and remove them. Note that during the flight, the drone can
shift its orientation and thus the same piece of debris object can appear in
different angles across consecutive overlapping images. To extract features
from the detected objects, we utilized SIFT (Scale-Invariant Feature
Transform), a computer vision algorithm that detects and describes local
features in an image (Lowe, 2004). By identifying key points and descriptors
in an object, SIFT extracts distinct features from each of the cropped images
containing debris objects and checks whether they are different views of the
same object. We chose SIFT for detecting the duplicates, as the SIFT key
points are invariant to image scale, translation, rotation, and change in
illumination, which is suitable to differentiate the different views of the
same object in our problem setting.

Figure 4. Example debris object from each of seven classes.

A figure with example objects from the 7 debris object categories.

Figure 5. Detected clusters of marine debris distribution.

Detected clusters of marine debris distribution on the island.

One limitation of using SIFT is the algorithm’s complexity, which can be
prohibitive to use due to its slow speed and computational demand. To reduce
the computational cost, we made several design choices. First, we decided to
only compare an object to other candidate objects that are detected within a
5-meter radius distance of the query object. Second, to identify a match, SIFT
requires setting a minimum number of key points. The higher the number of
features considered, the more computationally expensive the process becomes.
We set the minimum number of matching features to 50 based on our empirical
experimentation. If the number of matching SIFT features exceeds 50, a pair of
detected objects is considered to be a different view of the same object. As
SIFT has a runtime complexity of $O(MN+I)$ for $M*N$ image and $I$ number of
descriptors, these two practical strategies reduced the computational
complexity of our proposed system.

###  2.4. Map visualization

####  2.4.1. Goal

Our objective is to aid in the coordination of volunteer-led marine debris
collection efforts through remote detection and mapping of debris using our
system. Based on our consultation experience with local stakeholders,
volunteer teams are on the island for a scheduled day (usually weekends) and
spend the daytime hours trying to cover as many sites as possible. Consecutive
years’ manual auditing reports can help identify the sites with high-density
debris objects. Otherwise, teams of volunteers have to manually survey the
island on foot, which can often take hours depending on the terrain
conditions, weather, and other factors. When volunteers reach the island,
knowing information such as where the hotspots are with marine debris located
in high density, whether the objects are light or heavy, etc. can help the
volunteer group to assign teams of people to those specific locations to
utilize their time and effort more effectively. For this purpose, we focused
on creating a map visualization of the drone survey that can be made available
to the volunteer team to streamline the removal process.

We used the metadata information from the drone image (longitude, latitude,
and altitude) to obtain the real-world point coordinates of the detected
objects To map the detected objects to their corresponding location, the
spatial resolution can be estimated with the dimension of the bounding box for
a detected object. To do this, we needed to calculate the Ground Sample
Distance (GSD) for each image location based on the corresponding altitude and
camera intrinsic parameters to capture the details.

####  2.4.2. Ground Sample Distance

In remote sensing from satellite or drone images, each square pixel represents
a square land or sea area on the earth’s surface. Ground Sampling Distance
(GSD) is a measure used in remote sensing to define the linear distance of a
single pixel in an image. It describes how much ground area is represented by
one pixel and is typically expressed in meters. The larger the GSD is, the
lower spatial resolution is gained. GSD allows us to estimate the real-world
distance from the image-view distance.

We leveraged the following relationship for GSD estimation,

(1) $\text{Ground Sample Distance}=\frac{{A\cdot S}}{{f\cdot I}}$

where,

  * •

$A$: Altitude of the sensor (Height between the camera and the ground) in
meters.

  * •

$S$: Sensor width (in meters).

  * •

$f$: Focal length of the camera lens (in millimeters).

  * •

$I$: Image width (in meters).

As the focal length of our drone is fixed, we use altitude, the object’s
image-view, and real-world dimension to estimate the GSD from equation 1.
Using GSD, we then translate the image-level center position of each object to
its real-world position and map them to corresponding geo-spatial coordinates.
An example of the map is presented in Figure 5, where three clusters of debris
objects can be seen.

One limitation we encountered in GSD calculation is camera angle and variable
GSD due to altitude change during drone flight. Due to the tree height and
ground elevation change, drone altitude during the flight dynamically changed
for safe navigation. On the other hand, lower altitude results in fine-grained
resolution, but result in more time and images required to survey a specific
area. These practical considerations are important design choices for
deploying the system in longitudinal automated surveys and its performance,
which we plan to explore in our future work.

##  3\. Evaluation

###  3.1. Site

To validate the performance of the proposed framework, we use a new drone
dataset of marine debris images. The dataset was primarily collected on Allen
Island, a coastal island located in North America of 2 km2 area. The island is
owned by Colby College and is primarily used for research and educational
purposes owing to the rich vegetation and multiple beach substrates, that are
ideal for studying different beach types. Visitors and volunteers can reach
the island primarily by boat, especially during summer. High fishing and
tourist activities in the water close to the island result in a large number
of marine debris objects accumulating along the shore in every fishing season,
making it ideal for the experimental evaluation of our framework.

###  3.2. Data Collection

Our dataset comprised of 1,000 images. The images were sampled from a single
drone flight surveying the island landscape on May 30, 2022. The aerial survey
was performed by a DJI Phantom 4 Pro (maximum image dimension 5472 by 3648).

While our framework is designed to perform without human labels as we do not
train or modify an existing detection model, we needed to curate a labeled
dataset with human-provided marine debris category labels for evaluation
purposes. The dataset was manually labeled by 6 undergraduate students as part
of a class project utilizing LabelBox (Lab, 2023), a web-based labeling tool
freely available for research purposes. 200 images were randomly selected as
an initial set that the annotators labeled individually. To minimize human
bias in the labeling process, an annotation guide (Tseng et al., 2020) was
developed through iterative discussion among the annotators to ensure
consistency in the labels across the annotators. Following the annotation
guide, the human annotators labeled the entire dataset using a labeling schema
with the final class categories.

Table 2. Detection and Classification Performance Evaluation Task | Metric | Score
---|---|---
Object Detection | Mean IOU | 0.69
Object Classification | F1 | 0.74

###  3.3. Results

We evaluate the detection and classification performance of our framework
using the annotator’s labels as ground truth. Since our framework involves two
modules: object detection and classification that are interdependent, we
evaluate the performance of each module separately. Note that, while
interdependent, performance in each module can be of value for clean-up
efforts, as a correctly detected debris objects that is categorized to a wrong
class can still help the volunteers.

For object detection, we use mean Intersection over Union (IOU), which
quantifies the overlap between the predicted bounding box and the ground truth
bounding box. The score ranges between 0 to 1 where a higher score indicates
better performance. For the classification step, we use the F1 score, which is
the harmonic mean of precision (fraction of correctly detected objects from
total detection) and recall (fraction of correctly detected objects from total
objects), ranging between 0 to 1 (best performance). The F1 score allows one
to measure the model’s performance by taking misclassifications into account,
which is particularly useful for evaluating the overall effectiveness of the
model when the number of instances from different classes is imbalanced.

Note that while prior works exist where marine debris objects are detected and
classified using computer vision models (Winans et al., 2023; Kikaki et al.,
2022; Marin et al., 2021), comparing our results directly with those systems
can result in spurious conclusions. First, most prior works trained or
finetuned a model using human labels in a supervised learning setting. Second,
different marine debris detection involves different numbers and types of
object categories depending on the economic activities of the data collection
site.

####  3.3.1. Detection performance

The evaluation results are presented in Table 2. The mean IoU score for marine
debris detection using Grounding DINO is 0.69. This is comparable to the
performance reported with existing drone-based deep learning-based litter
detection approaches (Kraft et al., 2021; Politikos et al., 2021). This is
promising considering we are using no human labels in detection and the
objects of interest are different from general waste categories. The detection
performance can be further improved as our database of correctly detected
marine debris objects grows to be large enough to train or finetune an
existing object detector using those labels as ground truth.

####  3.3.2. Classification performance

Our CLIP based marine debris classifier reported an accuracy of $0.775$ and
average F1 score of $0.74$6 across the 7 identified classes. Our F1 score is
close to previous works on marine debris detection (Winans et al., 2023; Tran
et al., 2022) using human labels, reporting similar (around 0.72 F1 score)
performance. This is promising as we are operating on multi-class
classification without any human labels.

One approach to improve the classification performance is dependent on
detection performance. Our objects of interest are of varying sizes and are
often found in clusters resulting in overlapping bounding boxes. Smaller items
such as bottles and caps were challenging to identify and label separately for
human annotators. This lowers the amount of overlap between ground truth and
detection, affecting the classification performance. (Winans et al., 2023)
found results suggesting that the performance of marine debris detection from
drone images improves with pixel-per-object ratio. We believe that systematic
exploration of image resolution and target debris size can be useful to
further improve performance.

##  4\. Web interface

Our objective is to provide the user easy access to the spatial distribution
information about the debris object so that it can aid in the removal process.
Towards that end, we developed a web application to allow stakeholders to
easily use the framework and explore the results. The front end of the
application is developed using React javascript library (Rea, 2023) that
serves as a Flask application. Our web interface is accessible as a public
Docker container, which is available at:
https://github.com/Tahiya31/Trash_Track.

###  4.1. User Interaction

The web interface is designed to offer an intuitive user experience targeting
non-technical stakeholders. Based on the findings of our need-finding session
with volunteers involved in removal and coordination, the application workflow
involves six functionality pages: Home, Data, Duplicate, Map, Plot, and Help.

Home page. On this page, users can upload a set of drone images. Once
uploaded, the user can run object detection and classification modules on each
image. Every detected debris object is cropped and displayed with the
predicted label. If incorrect, the user can manually correct the class label
from a drop-down menu containing the 7 predefined classes, allowing the user
to iteratively improve the model-provided annotation and create a labeled
dataset. Figure 6 shows the Home page where a drop-down menu is used to
correct the predicted label of a debris item.

Data. The Data page allows the user to upload, view, remove, and download the
current database containing the results in a tabular format. All user
interaction including label corrections made within the web application is
stored as a .csv file that the user can download for their analysis. The .csv
file contains bounding box coordinates, image metadata (latitude, longitude,
altitude), and class label information, which can be used for additional
analysis.

Duplicates. Users can upload a set of images here, and check whether there are
duplicate objects. If found, duplicate objects are removed from database.

Map. This page presents all detected debris items on a map, with detected
trash overlayed on it corresponding to their real-world position. Debris
object types are coded by specific colors to aid in the removal.

Plot. The Plot page generates charts and plots to quickly visualize the
distribution of different trash categories to understand the dominant category
on a particular site and aid in volunteer management and removal planning.

We also included a Help page with instructions and a demonstration with a
video walk-through illustrating the application’s different functionalities
described above.

Figure 6. A screen shot of the Home page of the web app. User can build an
annotated dataset for their custom geographic region by collaboratively
annotating using computer vision models available through our framework.

##  5\. Ethical Considerations and Limitations

The framework proposed in this work is designed using multiple machine
learning-based models to detect and classify objects. These models are trained
on large datasets for generalized performance that are primarily well-suited
for western geographic areas and thus may not be well-performant in other
geographic regions. Relying solely on automated tools for detecting objects in
critical settings can thus lead to potential societal and environmental
consequences due to misclassification.

Our drone images are collected on a remote island with very few inhabitants.
Drone images, taken in residential areas, can contain individually
identifiable information and can invade people’s privacy. Another limitation
is our framework is designed and evaluated on data collected from a single
geographic region. While we have tried to ensure that our framework is built
on general-purpose detection and classification models to be useful in a wide
variety of custom marine debris collection applications, we have not
empirically evaluated the approach for data collected in other sites, which we
plan to do in the future.

We utilized zero-shot object detectors and classifiers, which are inherently
large models trained on millions of training images and are computationally
expensive during inference time. Another source of computational expense in
this framework is the duplicate matching step with SIFT, which has a quadratic
time complexity in a worst-case scenario. Our current framework is supported
by Paperspace Gradient, a high-performance computing platform, useful for
prototyping with an hourly pay-as-you-go pricing model. In the future, we plan
to find more economic alternatives for hosting the web application and running
the model for real-world deployment.

##  6\. Discussion

While detecting and classifying waste objects with aerial imagery have been
explored in existing works, most approaches rely on publicly available large-
scale datasets. However, real-world marine debris cleanup efforts need user-
friendly frameworks that can be easily adaptable with minimal annotation
efforts by communities from different geographic landscapes and environmental
conditions. As our focus is to develop a solution that can be sustainably
adopted to existing clean-up efforts, we describe these considerations through
additional data collection and future directions to improve its impact.

###  6.1. Data Collection Considerations

We ran a pilot data collection effort to gather a second drone dataset of
marine debris images in January 2024. We picked several beaches along islands
in Bermuda for this pilot study. Bermuda beaches have a similar marine waste
pollution problem where beaches are covered with millions of small pieces of
plastic trash (Finighan, 2024). These trash pieces come from the Sargasso Sea,
which is bounded by multiple currents in the Atlantic that carry the trash
into the ocean and eventually accumulate on islands like the ones in Bermuda
due to the weather pattern.

We experienced that environmental factors can impact such drone data
collection tremendously. The attempt to gather data in Bermuda provided
valuable insights and underscored several challenges inherent to deploying
this type of technology in new geographic areas and environments.

First, the quality of images captured in a drone flight is subject to weather
conditions. Adverse weather conditions, including high winds and sudden rain,
disrupted the flight path of the drone and its ability to maintain a stable
altitude position that is necessary to capture high-resolution images. Second,
collecting drone images on public land and beaches was often restricted as
they were categorized as no-fly zones by local government and regulatory
bodies. Due to these complications and budgetary restrictions, it was not
possible to collect adequate data in Bermuda for evaluating our framework.
Based on the lessons learned from this experience, we plan to organize a data
collection plan in the future by working with local stakeholders to identify
suitable sites and weather conditions to appropriately cover different marine
debris hotspots with various types and number of object classes.

###  6.2. Future Works

We have presented preliminary works toward designing a framework for
sustainable marine debris removal through community-driven efforts. Currently,
our framework performs without human labels using a zero-shot object detector
(Grounding DINO) and object classifier (CLIP). While ML models are assessed by
their accuracy on the task against ground truth labels, the energy efficiency
and computational expense are also important factors for budgetary decisions
of community-led efforts. In the future, more experiments are needed to assess
the performance and efficiency of the framework using other detection and
classification models such as OWL (Minderer et al., 2024), that can help to
scale this framework to a wide range of marine debris objects in open-world
classification setting. We also want to evaluate the applicability of the
framework for different types of marine debris contexts and coastal ecosystems
to validate its robustness.

We initiated this project to explore building a community-driven solution for
the marine debris problem in small remote islands. The current approach of
frequently surveying the islands manually requires significant budget
allocation and volunteer time, which does not scale well. In the future, we
plan to release the framework as a mobile application that visitors and
volunteers of the island can download to access the trash locations for ease
of planning. We also plan to add functionality to the app where application
users can report the location of a debris item if it has not been located by
the system (e.g. occluded from drone view) already. This would also act as the
ground truth for assessing the detection and classification model’s
performance in future iterations. Debris items collected in this manner will
be sorted based on their recycling potential and can be transported to a
material recovery facility to maximize the value of recycled materials.

Realizing the positive impact of technological interventions often depends on
local stakeholders’ knowledge. For example, fishing gear that get washed up
are still considered the fishermen’s private property in many coastal regions,
making it required for volunteers to return the collected gears to their
owners after removal. Volunteers and fishermen work together to organize a
‘Gear Grab’ event to ensure gears are returned to their rightful owners and
remove other debris items for recycling. Additionally, storms and hurricanes
play a role in displacing the objects from their located position, often
moving them inward into the woods with the wind and waves. To bridge the gap
between technological innovation and on-ground efforts, we aim to collaborate
with volunteers and organizations locally involved in on-ground clean up
efforts. Such collaboration can provide practical insights and feedback on
such issues that can improve the user experience, usability, efficiency, and
overall performance of our framework in supporting clean-up initiatives. This
engagement will facilitate iterative improvements to the system, ensuring it
meets the practical needs of users and maximizes the sustainable conservation
of island ecosystems.

##  7\. Conclusion

In this work, we have introduced a framework for marine debris cleanup
initiatives led by the local government and volunteer community. Our framework
is designed to reduce the human efforts involved in the current manual survey
method and expedite the coordination of the debris collection and removal
process. This framework uses state-of-the-art object detection and
classification approaches to automate the monitoring process that stakeholders
can easily use and visualize through an interactive web application. We also
evaluate our approach using human-annotated drone images from a novel dataset
of marine debris on a coastal island. The proposed approach can be used
without human annotations for custom model training and can thus be used for a
wide range of geographic regions and environmental conditions. Our framework
is publicly available that we hope will enable sustainable community-driven
efforts for cleaning up our oceans and coast.

###### Acknowledgements.

We thank Dr. Amanda Stent from the Davis Institute for Artificial Intelligence
for her input in the annotation and initial framework design. We also thank
Tim Stonesifer for drone data collection, manual survey, and feedback on the
framework design. We acknowledge the students in Colby January Course JP297
for helping with the annotation of the dataset.

## References

  * (1)
  * UNE (2022) 2022\.  _Our Planet is choking on plastic_.  Retrieved March 7, 2024 from https://www.unep.org/interactives/beat-plastic-pollution/
  * Lab (2023) 2023\.  _LabelBox_.  Retrieved March 5, 2024 from https://labelbox.com
  * Rea (2023) 2023\.  _React_.  Retrieved March 5, 2024 from https://react.dev
  * Finighan (2024) Gareth Finighan. 2024\.  _Ocean pollution crisis is ‘literally choking our local marine environments’ – KBB_.  Retrieved March 9, 2024 from https://www.royalgazette.com/environment/news/article/20230109/ocean-pollution-crisis-is-literally-choking-our-local-marine-environments-kbb/
  * Freitas et al. (2021) Sara Freitas, Hugo Silva, and Eduardo Silva. 2021.  Remote hyperspectral imaging acquisition and characterization for marine litter detection.  _Remote Sensing_ 13, 13 (2021), 2536.
  * Garaba et al. (2020) S. P. Garaba, T. Acuña Ruz, and C. B. Mattar. 2020.  Hyperspectral longwave infrared reflectance spectra of naturally dried algae, anthropogenic plastics, sands and shells.  _Earth System Science Data_ 12, 4 (2020), 2665–2678.  https://doi.org/10.5194/essd-12-2665-2020
  * Iordache et al. (2022) Marian-Daniel Iordache, Liesbeth De Keukelaere, Robrecht Moelans, Lisa Landuyt, Mehrdad Moshtaghi, Paolo Corradi, and Els Knaeps. 2022\.  Targeting plastics: machine learning applied to litter detection in aerial multispectral images.  _Remote Sensing_ 14, 22 (2022), 5820.
  * Kikaki et al. (2022) Katerina Kikaki, Ioannis Kakogeorgiou, Paraskevi Mikeli, Dionysios E Raitsos, and Konstantinos Karantzalos. 2022.  MARIDA: A benchmark for Marine Debris detection from Sentinel-2 remote sensing data.  _PloS one_ 17, 1 (2022), e0262247.
  * Knaeps et al. (2021) E. Knaeps, S. Sterckx, G. Strackx, J. Mijnendonckx, M. Moshtaghi, S. P. Garaba, and D. Meire. 2021.  Hyperspectral-reflectance dataset of dry, wet and submerged marine litter.  _Earth System Science Data_ 13, 2 (2021), 713–730.  https://doi.org/10.5194/essd-13-713-2021
  * Kraft et al. (2021) Marek Kraft, Mateusz Piechocki, Bartosz Ptak, and Krzysztof Walas. 2021.  Autonomous, Onboard Vision-Based Trash and Litter Detection in Low Altitude Aerial Images Collected by an Unmanned Aerial Vehicle.  _Remote Sensing_ 13, 5 (2021).  https://doi.org/10.3390/rs13050965
  * Lincoln et al. (2022) Susana Lincoln, Barnaby Andrews, Silvana N.R. Birchenough, Piyali Chowdhury, Georg H. Engelhard, Olivia Harrod, John K. Pinnegar, and Bryony L. Townhill. 2022.  Marine litter and climate change: Inextricably connected threats to the world’s oceans.  _Science of The Total Environment_ 837 (2022), 155709.  https://doi.org/10.1016/j.scitotenv.2022.155709
  * Liu et al. (2023) Shilong Liu, Zhaoyang Zeng, Tianhe Ren, Feng Li, Hao Zhang, Jie Yang, Chunyuan Li, Jianwei Yang, Hang Su, Jun Zhu, et al. 2023\.  Grounding dino: Marrying dino with grounded pre-training for open-set object detection.  _arXiv preprint arXiv:2303.05499_ (2023).
  * Lowe (2004) David G Lowe. 2004\.  Distinctive image features from scale-invariant keypoints.  _International journal of computer vision_ 60 (2004), 91–110.
  * Marin et al. (2021) Ivana Marin, Saša Mladenović, Sven Gotovac, and Goran Zaharija. 2021.  Deep-feature-based approach to marine debris classification.  _Applied Sciences_ 11, 12 (2021), 5644.
  * Martin et al. (2021) Cecilia Martin, Qiannan Zhang, Dongjun Zhai, Xiangliang Zhang, and Carlos M Duarte. 2021.  Enabling a large-scale assessment of litter along Saudi Arabian red sea shores by combining drones and machine learning.  _Environmental Pollution_ 277 (2021), 116730.
  * Merlino et al. (2021) Silvia Merlino, Marco Paterni, Marina Locritani, Umberto Andriolo, Gil Gonçalves, and Luciano Massetti. 2021.  Citizen science for marine litter detection and classification on unmanned aerial vehicle images.  _Water_ 13, 23 (2021), 3349.
  * Minderer et al. (2024) Matthias Minderer, Alexey Gritsenko, and Neil Houlsby. 2024\.  Scaling open-vocabulary object detection.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Moy et al. (2018) Kirsten Moy, Brian Neilson, Anne Chung, Amber Meadows, Miguel Castrence, Stephen Ambagis, and Kristine Davidson. 2018.  Mapping coastal marine debris using aerial imagery and spatial analysis.  _Marine pollution bulletin_ 132 (2018), 52–59.
  * Pfeiffer et al. (2022) Roland Pfeiffer, Gianluca Valentino, Sebastiano D’Amico, Luca Piroddi, Luciano Galone, Stefano Calleja, Reuben A Farrugia, and Emanuele Colica. 2022.  Use of UAVs and Deep Learning for Beach Litter Monitoring.  _Electronics_ 12, 1 (2022), 198.
  * Politikos et al. (2021) Dimitris V Politikos, Elias Fakiris, Athanasios Davvetas, Iraklis A Klampanos, and George Papatheodorou. 2021.  Automatic detection of seafloor marine litter using towed camera images and deep learning.  _Marine Pollution Bulletin_ 164 (2021), 111974.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021\.  Learning transferable visual models from natural language supervision. In _International conference on machine learning_. PMLR, 8748–8763.
  * Tasseron et al. (2021) Paolo Tasseron, Tim Van Emmerik, Joseph Peller, Louise Schreyers, and Lauren Biermann. 2021\.  Advancing floating macroplastic detection from space using experimental hyperspectral imagery.  _Remote Sensing_ 13, 12 (2021), 2335.
  * Tran et al. (2022) Thi Linh Chi Tran, Zhi-Cheng Huang, Kuo-Hsin Tseng, and Ping-Hsien Chou. 2022.  Detection of Bottle Marine Debris Using Unmanned Aerial Vehicles and Machine Learning Techniques.  _Drones_ 6, 12 (2022).  https://doi.org/10.3390/drones6120401
  * Tseng et al. (2020) Tina Tseng, Amanda Stent, and Domenic Maida. 2020.  Best practices for managing data annotation projects.  _arXiv preprint arXiv:2009.11654_ (2020).
  * Winans et al. (2023) W. Ross Winans, Qi Chen, Yi Qiang, and Erik C. Franklin. 2023\.  Large-area automatic detection of shoreline stranded marine debris using deep learning.  _International Journal of Applied Earth Observation and Geoinformation_ 124 (2023), 103515.  https://doi.org/10.1016/j.jag.2023.103515


11institutetext: Dept. of Mathematics and Computing, Indian Institute of
Technology (ISM) Dhanbad, India
11email<EMAIL_ADDRESS>
22institutetext: Dept. of Computer Science and Engineering, Indian Institute
of Information Technology Raichur, India
22email<EMAIL_ADDRESS>
33institutetext: The Czech Academy of Sciences, Institute of Computer Science,
Czech Republic
33email<EMAIL_ADDRESS>
44institutetext: Dept. of Information and Computing Sciences, Utrecht
University, the Netherlands
44email<EMAIL_ADDRESS>
55institutetext: Department of Theoretical Computer Science, Faculty of
Information Technology, Czech Technical University in Prague, Czech Republic
55email<EMAIL_ADDRESS>
# Minimum Color Spanning Circle
of Imprecise Points††thanks: A preliminary version of this paper appeared in
the Proceedings of the 27th International Conference on Computing and
Combinatorics (COCOON 2021).

Ankush Acharyya The work was partially done while affiliated with Institute of
Computer Science of the Czech Academy of Sciences, with institutional support
RVO:67985807.11 Ramesh K. Jallu22footnotemark: 2 22 Vahideh Keikha 33
Maarten Löffler 44 Maria Saumell 3355

###### Abstract

Let $\cal R$ be a set of $n$ colored imprecise points, where each point is
colored by one of $k$ colors. Each imprecise point is specified by a unit disk
in which the point lies. We study the problem of computing the smallest and
the largest possible minimum color spanning circle, among all possible choices
of points inside their corresponding disks. We present an $O(nk\log n)$ time
algorithm to compute a smallest minimum color spanning circle. Regarding the
largest minimum color spanning circle, we show that the problem is
$\mathsf{NP\text{-}Hard}$ and present a $\frac{1}{3}$-factor approximation
algorithm. We improve the approximation factor to $\frac{1}{2}$ for the case
where no two disks of distinct color intersect.

###### Keywords:

Color spanning circle Imprecise points Algorithms Computational complexity

##  1 Introduction

Recognition of color spanning objects of optimum size, in the classical
(precise) setting, is a well-studied problem in the literature [2, 3, 8, 16].
The motivation of color spanning problems stems from facility location
problems. Here facilities of type $i\in\\{1,2,\ldots,k\\}$ are modeled as
points with color code $i$, and the objective is to identify the location of a
desired geometric shape containing at least one facility of each type such
that the desired measure parameter (width, perimeter, area, etc.) is
optimized. Other applications of color spanning objects can be found in disk-
storage management systems [5] and central-transportation systems [30].

The simplest type of two-dimensional problem considered in this setup is the
minimum color spanning circle ($\mathsf{MCSC}$) problem, defined as follows.
Given a colored point set $P$ in the plane, such that each point in $P$ is
colored with one of $k$ possible colors, compute a circle of minimum radius
that contains at least one point of each color (see Fig. 1a). The
$\mathsf{MCSC}$ problem is well-understood: As observed by Abellanas et al.
[1], a minimum color spanning circle can be computed in $O(nk\log n)$ time
using results on the upper envelope of Voronoi surfaces obtained by
Huttenlocher et al. [16].

Figure 1: (a) $\mathsf{MCSC}$ for a precise colored point set. (b,c)
$\mathsf{S\text{-}MCSC}$ and $\mathsf{L\text{-}MCSC}$ for an imprecise colored
point set. The representative for each disk is marked as a point of the
corresponding color. In (c), we display two $\mathsf{L\text{-}MCSC}$ of the
same radius.

A limitation of these studies on color spanning objects is that, in many real-
life situations, the locations of the points are subject to errors and their
exact coordinates are unknown. This is an issue that might arise every time
that we try to apply a geometric algorithm to real-world data. For this
reason, in recent years there have been many studies aimed at describing how
imprecision in the input data might affect some of the most fundamental
geometric descriptors, such as the convex hull or the smallest bounding box.
In these studies, the input is an imprecise or uncertain point set: the
location of every point is not uniquely determined, but given by a set of
possible locations called its region [29, 33]. One of the fundamental
questions to be studied in this setting is to compute the extreme values of
the descriptors, that is, the smallest and biggest, e.g., convex hull of the
point set, for all possible locations of every point in its region. In this
paper, we consider this problem for the minimum color spanning circle.

###  1.1 Related work

Uncertainty in data is paramount in contemporary geometric computations. In
the literature, different variations have been considered where the regions
are modelled as simple geometric objects such as line segments, disks or
squares [29, 33]. Computing the smallest circle intersecting a set of disks or
convex regions of total complexity $n$ is called the intersection radius
problem, and can be solved in $O(n)$ time [17]. Robert and Toussaint [32]
studied the problem of computing the smallest width corridor intersecting a
set of convex regions (disks and line segments) and proposed two $O(n\log n)$
time algorithms, where $n$ is the number of convex regions. Löffler and van
Kreveld [29] considered the problem of computing the smallest and largest
possible axis-parallel bounding box and circle of a set of regions modelled as
circles or squares. Their proposed algorithms have running times ranging from
$O(n)$ to $O(n\log n)$. For a set of squares or line segments, computing a
placement of points in the regions that maximizes or minimizes the area or the
perimeter of the convex hull is studied by the same authors [28]. Some
variants are shown to be $\mathsf{NP\text{-}Hard}$, and the polynomial time
algorithms have running times ranging from $O(n\log n)$ to $O(n^{13})$. If the
input is a set of disks, a $(1+\varepsilon)$-approximation algorithm for this
problem is given also by van Kreveld and Löffler [26]. Other problems that
have been studied in the region-based model are computing a placement to
maximize or minimize the diameter on a set of squares or disks [21, 29], or
the area of the largest or smallest triangle on a set of line segments [22].

We note that other model formulations have also been proposed for dealing with
inaccuracies in geometric problems. These are epsilon geometry [33],
probabilistic models [6, 34], the aggregated uncertainty model [20], and the
domain based models [11].

Regarding other color spanning objects in the precise setting, efficient
algorithms are known for computing smallest color spanning squares [1], strips
and rectangles [8], 2-intervals [18], equilateral triangles of fixed
orientation [15], and axis-parallel squares [23]. Acharyya et al. [2] propose
efficient algorithms to compute the narrowest color spanning annulus for
circles, axis-parallel squares, rectangles, and equilateral triangles of fixed
orientation. The minimum diameter color spanning set problem has also been
studied [13, 19, 35]. Its general version is known to be
$\mathsf{NP\text{-}Hard}$ in the $L_{p}$ metric, for $1<p<\infty$, while in
the $L_{1}$ and $L_{\infty}$ metrics the problem can be solved in polynomial
time [13].

Colored variations of other geometric problems have also been studied in the
context of imprecise points [7, 9, 31]. Given a set of colored clusters, the
problem of computing the minimum-weight color spanning tree (generalized MST
problem) is $\mathsf{APX\text{-}Hard}$ [9]. Even when each cluster contains
exactly two points the problem remains $\mathsf{NP\text{-}Hard}$ [14]. The
problem admits a $2\delta$-approximation, where $\delta$ is the maximum size
of the cluster for any imprecise vertex of the MST [31]. In the generalized
TSP problem (GTSP), the imprecision is defined by neighborhoods (which are
either continuous or discrete) and the goal is to find the shortest tour that
visits all neighborhoods. It is known that GTSP with neighborhoods defined by
subsets of cardinality two is inapproximable [9].

Finally, we would like to notice that the problem of computing the largest
minimum color spanning circle (see the formal description below) is closely
related to the dispersion problem in unit disks, where for a given set of $n$
unit disks the goal is to select $n$ points, one from each disk, such that the
minimum pairwise distance among the selected points is maximized. This problem
was introduced by Fiala et al. [12], and the authors proved that it is
$\mathsf{NP\text{-}Hard}$. It is also known that the problem is APX-hard [10].
Constant factor approximation algorithms for this problem are given by Cabello
[4], and by Dumitrescu and Jiang [10].

###  1.2 Problem definition and results

In this work, we are given a set ${\cal R}=\\{R_{1},R_{2},\ldots,R_{n}\\}$ of
$n$ unit disks of diameter $1$ in the plane, where each disk is colored with
one of $k$ possible colors. A colored point set $P$ is a realization of $\cal
R$ if there exists a color-preserving bijection between $P$ and $\cal R$ such
that each point in $P$ is contained in the corresponding disk in $\cal R$.
Each realization of $\cal R$ gives a $\mathsf{MCSC}$ of certain radius. We are
interested in finding realizations of $\cal R$ such that the corresponding
$\mathsf{MCSC}$ has the smallest ($\mathsf{S\text{-}MCSC}$) and largest
($\mathsf{L\text{-}MCSC}$) possible radius (see Fig. 1b and c).

We present the following results:

  * •

The $\mathsf{S\text{-}MCSC}$ problem can be solved in $O(nk\log n)$ time.

  * •

The $\mathsf{L\text{-}MCSC}$ problem is $\mathsf{NP\text{-}Hard}$.

  * •

A $\frac{1}{3}$-factor approximation to the $\mathsf{L\text{-}MCSC}$ problem
can be computed in $O(nk\log n)$ time. When no two distinct color disks
intersect, the approximation factor becomes $\frac{1}{2}$.

To the best of our knowledge there is no prior result on the minimum color
spanning circle problem for imprecise point sets.

##  2 The smallest $\mathsf{MCSC}$ ($\mathsf{S\text{-}MCSC}$) problem

Given a set $\cal R$ of $n$ imprecise points modeled as unit disks, we present
an algorithm that finds a $\mathsf{S\text{-}MCSC}$, denoted by $C_{opt}$, and
the realization of $\cal R$ achieving it. Notice that the
$\mathsf{S\text{-}MCSC}$ problem is equivalent to finding a smallest circle
that intersects all color regions.

Let ${\cal C}=\\{c_{1},\ldots,c_{n}\\}$ be the set of center points of the
disks in $\cal R$. Let $C_{c}$ be a $\mathsf{MCSC}$ of the colored set $\cal
C$, and let $r_{c}$ be its radius. Finally, let $r_{opt}$ be the radius of
$C_{opt}$. The following relation holds:

###### Lemma 1

If $r_{c}>\frac{1}{2}$, then $r_{opt}=r_{c}-\frac{1}{2}$.

###### Proof

Consider a circle $C_{c}^{\prime}$ concentric with $C_{c}$ with radius
$r^{\prime}_{c}=r_{c}-\frac{1}{2}$ (see Fig. 2). For every disk $R_{i}$ such
that $c_{i}$ is contained in $C_{c}$, we have that $C^{\prime}_{c}$ contains
$c_{i}$ or the intersection between the boundary of $R_{i}$ and the segment
connecting $c_{i}$ with the center of $C_{c}$. Thus, $C^{\prime}_{c}$ contains
at least one point of each color and $r_{opt}\leq r^{\prime}_{c}$.

Figure 2: Illustration of Lemma 1. The dotted circle $C_{c}$ is the
$\mathsf{MCSC}$ of the disk centers and the circle $C^{\prime}_{c}$ is
obtained by decreasing $C_{c}$’s radius by $\frac{1}{2}$.

If $r_{opt}<r^{\prime}_{c}$, we would get a feasible solution for the
$\mathsf{MCSC}$ problem of $\cal C$ by increasing the radius of $C_{opt}$ by
$\frac{1}{2}$. Since such a solution would have radius
$r_{opt}+\frac{1}{2}<r^{\prime}_{c}+\frac{1}{2}=r_{c}$, we would get a
contradiction with the fact that $r_{c}$ is the radius of any $\mathsf{MCSC}$
of $\cal C$. ∎

Using Lemma 1, we compute $C_{opt}$ as described in Algorithm 1:

Algorithm 1 Algorithm for the $\mathsf{S\text{-}MCSC}$ problem 1:A set ${\cal
R}$ of $n$ unit disks 2:A $\mathsf{S\text{-}MCSC}$ of $\cal R$ with radius
$r_{opt}$ 3:compute $C_{c}$;  4:if $r_{c}>1/2$ then 5: $C_{opt}$ is a circle
concentric with $C_{c}$, $r_{opt}\leftarrow r_{c}-\frac{1}{2}$;  6:else 7:
$C_{opt}$ is a circle concentric with $C_{c}$, $r_{opt}\leftarrow 0$;
$\triangleright$ $C_{opt}$ is a point  8:return $C_{opt}$

It only remains to prove that Algorithm 1 is correct and efficient:

###### Theorem 2.1

A smallest minimum color spanning circle of $\cal R$ can be computed in
$O(nk\log n)$ time.

###### Proof

In Algorithm 1, we first compute a $\mathsf{MCSC}$ $C_{c}$ of $\cal C$ in
$O(nk\log n)$ time using the technique proposed by Huttenlocher et al. [16].
If $r_{c}>\frac{1}{2}$, we shrink the radius of $C_{c}$ by $\frac{1}{2}$ and
return this circle as a solution to the $\mathsf{S\text{-}MCSC}$ problem. The
optimality of the solution follows from Lemma 1. If $r_{c}\leq\frac{1}{2}$, we
have the following property: If $c_{i}$ is contained in $C_{c}$, then the
center of $C_{c}$ in contained in $R_{i}$. Hence, the center of $C_{c}$ lies
in the intersection of $k$ distinct colored disks. In consequence, a circle of
radius zero concentric with $C_{c}$ is a solution to the
$\mathsf{S\text{-}MCSC}$ problem. ∎

##  3 The largest $\mathsf{MCSC}$ ($\mathsf{L\text{-}MCSC}$) problem

In this section, we consider the $\mathsf{L\text{-}MCSC}$ problem, where for
the given set $\cal R$ the goal is to find a realization such that any
$\mathsf{MCSC}$ is as large as possible. We show that the problem is
$\mathsf{NP\text{-}Hard}$, already for $k=2$, using a reduction from planar
$\mathsf{3\text{-}SAT}$ [27]. Our reduction is inspired by those described by
Fiala et al. [12], and by Knauer et al. [24].

Given a planar $\mathsf{3\text{-}SAT}$ instance, we construct a set of colored
unit disks with the following property: There exists a realization such that
any $\mathsf{MCSC}$ has diameter $\delta$ if and only if the
$\mathsf{3\text{-}SAT}$ instance is satisfiable, where $\delta=\frac{9}{8}$.
We use disks of colors red and blue. Thus, a point set having any
$\mathsf{MCSC}$ of diameter at least $\delta$ is equivalent to saying that
there is no red-blue pair of points at distance less than $\delta$. We denote
the family of realizations with this property by $\mathcal{P}^{\delta}$. With
some abuse of notation, sometimes we also use the terminology
$\mathcal{P}^{\delta}$ to characterize realizations of (only) a subset of the
disks.

We next describe our construction.

Figure 3: (a) A stack of disks; (b) the distance from the left endpoint of the
red disk to its farthest point in the top blue disk is $\frac{9}{8}$; (c,d)
the two placements of points with red-blue distances equal to $\delta$.

A _stack of disks_ is a set of three vertically aligned unit disks of
alternating colors such that the center of the middle disk is at distance
$\frac{3}{8}$ from the centers of the two other disks. See Fig. 3a for an
example of a blue-red-blue stack of disks.

###### Lemma 2

There exist two realizations in $\mathcal{P}^{\delta}$ of a stack of disks.

###### Proof

Let us denote by $R_{i}$ and $R_{j}$ the upper and middle disk of the stack,
and let $c_{i}$ and $c_{j}$ denote their centers. Additionally, let the
leftmost and rightmost points of $R_{j}$ be denoted by $p_{j}$ and
$p^{\prime}_{j}$ (see Fig. 3b). Notice that, among all points which are on the
upper half of $R_{j}$ or on its horizontal diameter, $p_{j}$ and
$p^{\prime}_{j}$ are the furthest to $c_{i}$.

Let $q_{i},q_{j}$ be two points such that $q_{i}$ lies in $R_{i}$ and $q_{j}$
lies in $R_{j}$. Without loss of generality, we assume that $q_{j}$ lies on
the upper half of $R_{j}$ or on its horizontal diameter (otherwise, we repeat
the same arguments taking the lower disk of the stack instead of the upper
one). Then we have

$\displaystyle d(q_{j},q_{i})$ $\displaystyle\leq
d(q_{j},c_{i})+d(c_{i},q_{i})\leq d(p_{j},c_{i})+\frac{1}{2}$
$\displaystyle=\sqrt{(d(p_{j},c_{j}))^{2}+(d(c_{i},c_{j}))^{2}}+\frac{1}{2}$
$\displaystyle=\frac{5}{8}+\frac{1}{2}=\frac{9}{8}.$

Notice that equality is only attained if $q_{j},c_{i}$ and $q_{i}$ are
aligned, and $q_{j}$ is equal to $p_{j}$ or $p^{\prime}_{j}$. Thus, there
exist only two realizations in $\mathcal{P}^{\delta}$, shown in Fig. 3c and d.
∎

###  3.1 Variable Gadget

Figure 4: A variable gadget with zoomed in view for the top-left corner. The
dashed circles are centered at $p_{k}^{\prime},p_{k},p_{i}^{\prime},p_{i}$ and
have radius $\delta$.

Our variable gadget (see Fig. 4) is an alternating chain of red and blue
disks, whose centers lie on a hexagon, together with some stacks of disks. The
distance between the centers of two consecutive red and blue disks along the
same edge of the hexagon is $\delta$. Each edge of the hexagon contains two
stacks of disks placed near the endpoints, and every pair of consecutive edges
is joined by a blue disk. In the following description, we say that $p_{i}$
and $p^{\prime}_{i}$ are the _leftmost_ and _rightmost_ points of disk $R_{i}$
if they are its leftmost and rightmost points after the hexagon has rotated so
that the edge containing the center of $R_{i}$ is horizontal and the center of
the hexagon is below the edge.

At the top-left corner of the variable gadgets, the disks are placed as
follows (the other corners are constructed similarly). Let $R_{i}$ be the last
disk in clockwise order along the top-left edge of the hexagon, and let
$R_{j}$ and $R_{k}$ be the first and second disks along the top edge (see Fig.
4). The point $p_{j}$ lies at the top left corner of the hexagon, and the
centers of $R_{j}$ and $R_{k}$ are at distance $\delta$. Regarding $R_{i}$, it
is placed in such a way that the lower blue disk of its stack contains a point
$z$ which is at distance $\delta$ from both $p_{k}$ and $p_{i}$ (see Fig. 4).
Notice that, if a realization in $\mathcal{P}^{\delta}$ chooses
$p^{\prime}_{i}$, the choice for $R_{j}$ is not unique; however, none of the
points in $R_{j}$ at distance at least $\delta$ from $p^{\prime}_{i}$ is at
distance at least $\delta$ from $p_{k}$. Therefore, the choice of
$p^{\prime}_{i}$ forces the choice of $p^{\prime}_{k}$, and clearly the choice
of $p_{k}$ forces the choice of $p_{i}$.

For a realization in $\mathcal{P}^{\delta}$ of a variable gadget, the
following holds: By Lemma 2, the stack containing $R_{k}$ is constrained to
choose either $p_{k}$ or $p^{\prime}_{k}$. Let us assume that it chooses
$p^{\prime}_{k}$. This choice propagates to the right through the chain of
disks in the top edge. The red disk of the stack on the right of the edge also
chooses its rightmost point, and this forces the red disk of the first stack
of the top right edge to choose its rightmost point too. Therefore, the choice
of $p^{\prime}_{k}$ propagates through the whole hexagon. If $R_{k}$ chooses
$p_{k}$, the same phenomenon occurs. We conclude:

###### Lemma 3

For any realization in $\mathcal{P}^{\delta}$ of a variable gadget, either all
the unit disks centered at the edges of the hexagon, except for the ones
intersecting corners of the hexagon, choose their rightmost point, or they all
choose their leftmost point.

###  3.2 Clause gadget

Figure 5: (a-c) A clause gadget with distinct truth assignments. In the
placement in (a), the red-blue pairs are at distance smaller than $\delta$,
while in (b) and (c) they are at distance greater than $\delta$.

Clause gadgets are illustrated in Fig. 5a-c. We consider an equilateral
triangle of side length $\frac{7}{2}$ and center $g$, and we place one red
disk at every corner of the triangle in such a way that the center of the disk
is aligned with $g$ and its nearest corner of the triangle. Then we place a
blue disk centered at $g$. Each red disk of a clause gadget is associated to
one of the literals occurring in the clause, and is connected to the
corresponding variable gadget via a connection gadget. Intuitively, to decide
if there exists any realization in $\mathcal{P}^{\delta}$, each red disk
$R_{\tau}$ of the clause gadget has essentially two relevant placements,
called $t_{R_{\tau}}$ and $f_{R_{\tau}}$ (see Fig. 5a). As we will see, when
the associated literal is set to _true_ , we can choose the placement
$t_{R_{\tau}}$, and when it is set to _false_ , we are forced to choose
$f_{R_{\tau}}$. It is easy to see that any realization in
$\mathcal{P}^{\delta}$ of the clause gadget does not choose $f_{R_{\tau}}$ for
at least one of the disks $R_{\tau}$ (see Fig. 5b and c).

###  3.3 Connection gadget

Figure 6: Connection gadget for a positive variable in a clause; the variable
has truth value $T$.

A variable gadget is connected to each of its corresponding clause gadgets
with the help of a _connection_ gadget. A connection gadget consists of an
alternating chain of red and blue disks together with some stacks of disks
(see Fig. 6).

The chain in a connection gadget is formed by straight line portions of groups
of disks equal to those along the edges of hexagons associated to variable
gadgets. These straight line portions are connected at bends of $120^{\circ}$.
The placement of disks at each bend is similar to the placements at the
corners of a variable gadget; in particular, stacks of disks are used around
the bends.

Figure 7: Point placements corresponding to (a) positive and (b) negative
variable in a clause, at the intersection of a connection gadget and a
variable gadget.  In both figures, the left subfigures correspond to the truth
value $T$ for the variable, and the right subfigures to the truth value $F$.

The precise connection of the variable gadget to the clause gadget by a
connection gadget depends on whether the variable in the clause is positive or
negative. For a positive variable, the connection is established through a
pair of a red disk $R_{i}$ and a blue disk $R_{j}$ which appear consecutively
along an edge of the hexagon, and such that none of them intersects a corner
of the hexagon, and $R_{i}$ comes before $R_{j}$ in clockwise order (see Fig.
7a). Let $R_{k}$ be the first red disk of the connection gadget. The top-most
point of $R_{k}$ is at distance $\delta$ from $p_{j}$, and its bottom-most
point is at distance $\delta$ from $p^{\prime}_{j}$. For a negative variable,
the connection is established through a pair of blue-red disks in the variable
gadget. The placement of the first red disk of the connection gadget is
analogous to the one in the red-blue configuration (see Fig. 7b).

To ensure the desired propagation of the placement of points in the disks,
stacks of disks are used next to the first disk $R_{k}$, and next to the red
disk of the clause gadget associated to the literal (see Fig. 6).

The truth value $T$ of a variable is associated with the choice of the
rightmost points of the disks in the variable gadget. If the variable appears
positive at a clause, this allows (for a realization in
$\mathcal{P}^{\delta}$) the choice of the bottom-most point of $R_{k}$, and
this propagates through the connection gadget and eventually allows the choice
of the associated point $t_{R_{\tau}}$ in the clause gadget (see Fig. 6). If
the truth value is $F$, $p_{j}$ is selected, which (for a realization in
$\mathcal{P}^{\delta}$) forces the choice of a point in a close vicinity of
the top-most point of $R_{k}$. Since there is a stack next to $R_{k}$, the
blue disk in the stack chooses the top-most point, and this eventually forces
the choice of $f_{R_{\tau}}$. The analysis of the other cases are similar.

###  3.4 Final construction

In the following lemma, we put all pieces of the construction together, and we
prove that it has polynomial size.

###### Lemma 4

Using the gadgets described above, we can construct in polynomial time a
polynomial-size instance of the $\mathsf{L\text{-}MCSC}$ problem associated to
the given planar $\mathsf{3\text{-}SAT}$ formula.

###### Proof

The dependency graph of the $\mathsf{3\text{-}SAT}$ formula can be embedded so
that all variables lie on a horizontal line, all clauses are on either side of
them, and each edge connecting a clause to a variable is an orthogonal edge
with at most one bend (see Fig. 8 for an example) [25]. We take an embedding
with these properties which, additionally, is aligned with a grid of
resolution 20 (i.e., the distance between any pair of consecutive horizontal
or vertical segments is at least 20). In the following lines, we explain how
to modify this embedding to produce an instance of the
$\mathsf{L\text{-}MCSC}$ problem. Our construction is illustrated in Fig. 9.

Figure 8: (a) Planar embedding of ${\cal F}=(x_{1}\lor
x_{2}\lor\bar{x}_{4})\land(x_{1}\lor\bar{x}_{2}\lor
x_{3})\land(x_{2}\lor\bar{x}_{3}\lor\bar{x}_{4})$. (b) A vertical portion of a
connection gadget with increased gaps among three central disks, which have
been replaced by stacks.

First, we replace the variables of the embedding by gadgets as described
above. The size of a variable gadget is chosen so that the upper and lower
side of the hexagon are long enough to fit all edges leading to clauses. Since
any two such edges are at distance at least 20 and we place them at distance
at least 20 from the extremes of the edges of the hexagon, the side of the
hexagon is no longer than $20(m+1)$, where $m$ is the number of clauses in the
formula. During this step, we might again need to horizontally “stretch” the
initial embedding so that variable gadgets end up at distance at least 20 from
each other.

Next, we replace the clauses of the embedding by clause gadgets. We explain in
detail the case where the clause is above the variables; the other case is
solved symmetrically (in particular, clause gadgets lying below the variables
will be rotated by $180^{\circ}$). Initially, the clause is incident to three
edges, which we call the “left”, “middle” and “right” edges. Each of them is
assigned to one of the red disks of the clause gadgets, i.e., the connection
between the variable gadget and the connection gadget will be done through
that disk. In particular, the left edge is assigned to the left-most red disk
of the gadget, the middle edge is assigned to the right-most red disk of the
gadget, and the right edge is assigned to the top red disk of the gadget (see
Fig. 9).

Finally, we replace every edge connecting a clause to a variable gadget by a
connection gadget in the following way: The position of the first disk of the
connection gadget (that is, the nearest to the clause gadget) is given by the
previous assignment of edges to red disks of the clause. The position of the
last disk (i.e., the disk of the connection gadget which intersects the
variable gadget) is as near as possible to the original location of the edge,
while respecting the requirements for each type of connection (which depend on
whether the variable appears positive or negative in the clause; refer to Fig.
7). Since the left and middle edges become connection gadgets with one bend of
$120^{\circ}$ (see Fig. 9), the precise shape of these gadgets (including the
position of the bend) is determined by their first and last disks. Notice also
that, since the middle edge (which is vertical) is replaced by a chain of
shape “  ”, it might be necessary to move the clause gadget slightly towards
the left. Regarding the right edge, it is replaced by a chain of shape “  ”
starting from the top red disk of the clause variable. In this case, there is
some freedom to choose the positions of the bends, and we place them so that
the final connection gadget is close enough to the original replaced edge.

After replacing orthogonal edges by connection gadgets with bends of
$120^{\circ}$, some pairs of connection gadgets might have ended up too near
(or even cross) and might interfere with each other. This can again be solved
by stretching the embedding to separate them.

We finally point out that the straight portions of our connection gadgets are
made of chains of unit disks at a certain fixed distance, and thus they can
only have certain prescribed lengths of $\frac{9k}{8}+1$ for some integer $k$,
which we call _integer_ lengths (e.g., for vertical portions of a connection
gadget, the distance between the bottom-most and top-most points of the chain
can only take values of the form $\frac{9k}{8}+1$, for some integer $k$).
Therefore, it might happen that the positions of a clause and variable gadget
force the placement of a chain which does not have integer length. In this
case, we proceed as follows: Suppose that we need a vertical chain such that
the positions and colors of the first and last disk are prescribed, and either
the distance $l$ between the bottom-most and top-most points of the chain does
not correspond to an integer length, or it does but it has the wrong parity
(e.g., when we try to build the chain, the bottom-most disk turns up blue, but
we would need it to be red). We take the longest chain of integer length
having length smaller than $l$ and having the desired combination of colors of
the first and last disk. If this chain has length $\frac{9k}{8}+1$, for some
integer $k$, then we have that $l<\frac{9(k+2)}{8}+1$. Thus, the difference in
lengths is at most $\frac{9}{4}$. To solve this discrepancy, we select two to
four consecutive disks from the middle of the chain and increase the gap
between them from $\frac{1}{8}$ to some appropriate value smaller than or
equal to $\frac{7}{8}$ (the remaining gaps between consecutive disks of the
chain remain of $\frac{1}{8}$). By replacing these two to four disks by
stacks, we ensure the required propagation among them despite the increased
gaps. See Fig. 8b for an example. Since we might increase up to three gaps by
up to $\frac{3}{4}$, we can achieve the difference in lengths of at most
$\frac{9}{4}$.

Since the final construction has a polynomial number of disks and all the
steps in the construction can be performed in polynomial time, the lemma
follows. ∎

Figure 9: Instance of the $\mathsf{L\text{-}MCSC}$ problem associated to the
formula $\cal F$ in Fig. 8a. For the sake of readability, the figure has been
rotated, the proportions among the sizes of the different objects have been
altered a little, and the hexagons associated to the variables are not drawn
regular. The placement of points corresponds to the satisfying assignment
$x_{1}=F$, $x_{2}=T$, $x_{3}=T$, and $x_{4}=F$.

Given a planar $\mathsf{3\text{-}SAT}$ formula $\cal F$, let us denote by
${\cal R}^{\cal F}$ an associated instance of the $\mathsf{L\text{-}MCSC}$
problem constructed following the steps in the proof of Lemma 4. We prove that
${\cal R}^{\cal F}$ has the desired property:

###### Lemma 5

The planar $\mathsf{3\text{-}SAT}$ formula $\cal F$ has a satisfying
assignment if and only if there exists a realization of ${\cal R}^{\cal F}$ in
$\mathcal{P}^{\delta}$.

###### Proof

Suppose that $\cal F$ has $n$ variables $x_{1},x_{2},\ldots,x_{n}$ and $m$
clauses $C_{1},C_{2},\ldots,C_{m}$.

Let us first assume that $\cal F$ is satisfiable. Thus, every clause contains
a literal whose truth value is $T$. We describe a realization of ${\cal
R}^{\cal F}$ in $\mathcal{P}^{\delta}$.

Let $C_{j}$ be a clause and let $\ell_{i}$ be a literal making the clause
true. Then we pick $t_{R_{i}}$ from the associated disk $R_{i}$ in the clause.
This choice propagates through the connection gadget and eventually forces one
of the realizations for the variable gadget described in Lemma 3: the one
choosing the rightmost points of the disks, if $\ell_{i}$’s truth value is $T$
and it appears in the clause positively; or the one choosing the leftmost
points of the disks, if $\ell_{i}$’s truth value is $F$ and it appears in the
clause negatively. Notice that a variable might make true several clauses, but
the obtained realizations of the variable gadget are consistent with each
other.

Let us consider a variable whose realization has been fixed in the paragraph
above. If its truth value is $T$ and it appears in a clause negatively, or if
its truth value is $F$ and it appears in a clause positively, the placement
described above forces the realizations of the corresponding connection gadget
and associated disk in the clause gadget.

For the variables whose realization has not been fixed yet (if any), we pick,
say, the realization choosing the leftmost points of the disks. For their
connection gadgets to the clauses, we pick the realization choosing the top-
most (respectively, bottom-most) points of the disks, if the clause is above
(respectively, below) the variable. The described realizations belong to
$\mathcal{P}^{\delta}$.

After following the steps above, for each clause gadget at least one of the
three red disks has its representative at the position $t_{R_{\tau}}$. In
consequence, it is possible to find a realization of the blue disk such that
the realization of the clause gadget is in $\mathcal{P}^{\delta}$.

Notice that we have described realizations for all gadgets in the
construction. Clearly, the global realization is in $\mathcal{P}^{\delta}$.

We next prove the second implication. Suppose that there exists a realization
$R$ of ${\cal R}^{\cal F}$ in $\mathcal{P}^{\delta}$. Let $C_{j}$ be a clause.
Since the realization of the clause is in $\mathcal{P}^{\delta}$, at least one
of the red disks $R_{i}$ of the clause does not have the representative at the
position $f_{R_{i}}$. If the corresponding literal appears positive in the
clause, we set the associated variable to $T$. Otherwise, we set it to $F$. In
this way, we ensure that every clause is true, but we need to argue that we
did not assign $T$ and $F$ simultaneously to the same variable due to two
distinct clauses.

Since in the connection gadget there is a stack of disks next to $R_{i}$, the
fact that $R_{i}$ does not have the representative at the position $f_{R_{i}}$
forces the choice of the representative of the blue disk in the stack. The
choice propagates to the connection gadget and eventually to the variable
gadget: If the literal associated to $R_{i}$ appears positive in $C_{j}$, the
variable has been set to $T$ and the realization in the variable gadget is the
one choosing the rightmost points of the disks. If the literal appears
negative, the variable has been set to $F$ and the realization in the variable
gadget chooses the leftmost points of the disks. Since in $R$ the realization
of the variable gadget is either the rightmost or the leftmost, the variable
has either been set to $T$ or to $F$. ∎

Lemmas 4 and 5 imply the following:

###### Theorem 3.1

The problem of finding a largest minimum color spanning circle of $\cal R$ is
$\mathsf{NP\text{-}Hard}$.

###### Remark 1

Given a yes-instance, we can verify in $O(nk\log n)$ time whether the given
realization is correct and the radius of its $\mathsf{MCSC}$ is at least
$\delta$. Therefore, the decision version of the problem is
$\mathsf{NP\text{-}Complete}$.

##  4 Approximation algorithms

Given that the $\mathsf{L\text{-}MCSC}$ problem is $\mathsf{NP\text{-}Hard}$,
in this section we turn our attention to approximation algorithms.

Let $\tilde{r}_{opt}$ denote the radius of a largest possible minimum color
spanning circle of ${\cal R}$. We first prove bounds on $\tilde{r}_{opt}$.

Figure 10: The tilted grid in the proof of Lemma 6. We choose $p_{i}$ as the
red corner of $Q$ contained in $R_{i}$.

###### Lemma 6

$\tilde{r}_{opt}\geq 1/4$.

###### Proof

First, we show that it is enough to prove the result for the case where $k=2$:
Suppose that $k>2$. We select two of the $k$ colors, say red and blue, and the
set $\cal R^{\prime}\subseteq\cal R$ of red and blue disks. Suppose that the
radius of any $\mathsf{L\text{-}MCSC}$ of $\cal R^{\prime}$ is greater than or
equal to $1/4$. Then there exists a realization of $\cal R^{\prime}$ whose
$\mathsf{MCSC}$ has radius greater than or equal to $1/4$. We complete this
realization of $\cal R^{\prime}$ to a realization of $\cal R$ by choosing any
point in each disk of the remaining $k-2$ colors. Since any $\mathsf{MCSC}$ of
this realization contains at least one red and one blue point, its radius is
greater than or equal to $1/4$.

Therefore, we only show that the bound holds when $k=2$ by providing a
realization $P$ whose $\mathsf{MCSC}$ achieves the bound. Consider a regular
square grid rotated by $\pi/4$ such that the side of every cell of the grid
has length $1/2$. We color the corners of the cells in red or blue in such a
way that all corners lying in some vertical line are colored red, all corners
lying in the next vertical line are colored blue, and so on (see Fig. 10). Now
let $R_{i}\in\cal R$ have red color, and let $Q$ be the cell of the grid
containing the center of $R_{i}$ (if the center of $R_{i}$ lies on an edge or
vertex of the grid, we assign it to any of the adjacent cells). Notice that at
least one of the two red corners of $Q$ lies inside $R_{i}$. We choose such a
corner as $p_{i}\in P$. Similarly, for every $R_{j}\in\cal R$ of blue color,
$P$ contains one of the blue corners of a cell containing the center of
$R_{j}$. We obtain that $P$ is a subset of the grid corners. Since the
distance between any pair of red and blue corners is at least $1/2$, the
radius of any $\mathsf{MCSC}$ is at least $1/4$. ∎

Next, we establish a relation between $\tilde{r}_{opt}$ and $r_{c}$. We recall
that $r_{c}$ is the radius of a $\mathsf{MCSC}$ (denoted $C_{c}$) of the
colored set $\cal C$ containing the center points of the disks in $\cal R$.

###### Lemma 7

$\tilde{r}_{opt}\leq r_{c}+\frac{1}{2}$.

###### Proof

Without loss of generality we can assume that $C_{c}$ contains the centers of
the disks in ${\cal R^{\prime}}=\\{R_{1},R_{2},\ldots,R_{k}\\}$. A circle of
radius $r_{c}+\frac{1}{2}$, concentric with $C_{c}$, contains the $k$ disks in
${\cal R^{\prime}}$. Therefore, for any placement of points inside disks of
${\cal R^{\prime}}$, we can always get a color spanning circle with radius at
most $r_{c}+\frac{1}{2}$. Thus, $\tilde{r}_{opt}\leq r_{c}+\frac{1}{2}$. ∎

We use the bounds above to design a simple approximation algorithm, presented
in Algorithm 2. Let $P^{g}$ denote the realization of $\cal R$ described in
the proof of Lemma 6.

Algorithm 2 $\frac{1}{3}$-factor approximation algorithm for the
$\mathsf{L\text{-}MCSC}$ problem 1:A set ${\cal R}$ of $n$ unit disks 2:A
$\mathsf{MCSC}$ of a realization of $\cal R$ with radius at least
$\tilde{r}_{opt}/3$ 3:compute $C_{c}$;  4:if $r_{c}\geq 1/4$ then 5: return
$C_{c}$;  6:else 7: return a $\mathsf{MCSC}$ of $P^{g}$;

It only remains to prove that Algorithm 2 indeed gives a $\frac{1}{3}$-factor
approximation:

###### Theorem 4.1

A $\frac{1}{3}$-factor approximation for the $\mathsf{L\text{-}MCSC}$ problem
can be computed in $O(nk\log n)$ time. If no two distinct colored unit disks
of $\cal R$ intersect, the approximation factor becomes $\frac{1}{2}$.

###### Proof

If $r_{c}\geq 1/4$, then, by Lemma 7, $\tilde{r}_{opt}\leq 3r_{c}$ and $C_{c}$
gives a $\frac{1}{3}$-approximation for the problem. If $r_{c}<1/4$, then, by
Lemma 7, $\tilde{r}_{opt}<3/4$. By Lemma 6, any $\mathsf{MCSC}$ of $P^{g}$ has
radius at least $1/4$, so such a circle gives a $\frac{1}{3}$-approximation
for the problem.

Computing $P^{g}$ takes $O(n)$ time, and computing a $\mathsf{MCSC}$ of
$P^{g}$ or the set of disk centers can be done in $O(nk\log n)$ time.

Finally, if no two distinct colored disks intersect, $r_{c}\geq\frac{1}{2}$.
This, combined with Lemma 7, gives $r_{c}\geq\frac{\tilde{r}_{opt}}{2}$. ∎

Since Lemma 6 is one of the key ingredients of our approximation algorithm, we
conclude this section by showing that it is the best possible.

Figure 11:  Construction in the proof of Remark 2. For the sake of clarity,
the red disks centered at the grid points are not displayed.

###### Remark 2

Given any $\varepsilon>0$, there exists a set ${\cal R}$ of unit disks for
which $\tilde{r}_{opt}<1/4+\varepsilon$.

###### Proof

We start with a blue disk $R_{1}$. We overlay a square grid of red points over
the area covered by $R_{1}$ enlarged a little around the boundary (see Fig.
11). The length of the sides of the grid cells is set to
$2\sqrt{2}\varepsilon$. Then, for every red point of the grid, we place a red
disk centered at that point. Finally, we place the remaining blue disks far
away from the construction.

Let $p_{1}$ be the representative for $R_{1}$ in a realization $P$ giving a
minimum color spanning circle of radius $\tilde{r}_{opt}$. Since $p_{1}$ lies
inside some cell of the grid, there exists some red grid point $q$ such that
$d(p_{1},q)\leq 2\varepsilon$. Let $R_{j}$ be the red disk centered at $q$,
and $p_{j}$ be its representative in the realization $P$. Then,
$d(p_{1},p_{j})\leq d(p_{1},q)+d(q,p_{j})\leq 2\varepsilon+1/2$. Since
$p_{1},p_{j}$ is a blue-red pair at distance at most $1/2+2\varepsilon$, the
radius of any minimum color spanning circle is at most $1/4+\varepsilon$. ∎

##  5 Open problems

Naturally, the main open problems are related to the $\mathsf{L\text{-}MCSC}$
problem and the existence of better approximation algorithms for it. So far we
have not succeeded in finding a PTAS for this problem, and we suspect that the
problem might be $\mathsf{APX\text{-}Hard}$. If this is the case, it would
also be interesting to improve the approximation factor of our approximation
algorithm.

#### Acknowledgements

The authors would like to thank Irina Kostitsyna for key discussions on the
hardness reduction and Hans Raj Tiwary for the proof of Lemma 6. A.A., R.J.,
V.K., and M. S. were supported by the Czech Science Foundation, grant number
GJ19-06792Y, and by institutional support RVO: 67985807. M.L. was partially
supported by the Netherlands Organization for Scientific Research (NWO) under
project no. 614.001.504. This project has received funding from the European
Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreement No 734922.

## References

  * [1] Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: Smallest color-spanning objects. In: auf der Heide, F.M. (ed.) Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings. Lecture Notes in Computer Science, vol. 2161, pp. 278–289. Springer (2001), https://doi.org/10.1007/3-540-44676-1_23
  * [2] Acharyya, A., Nandy, S.C., Roy, S.: Minimum width color spanning annulus. Theor. Comput. Sci. 725, 16–30 (2018), https://doi.org/10.1016/j.tcs.2017.11.031
  * [3] de Berg, M., Gudmundsson, J., Katz, M.J., Levcopoulos, C., Overmars, M.H., van der Stappen, A.F.: TSP with neighborhoods of varying size. J. Algorithms 57(1), 22–36 (2005), https://doi.org/10.1016/j.jalgor.2005.01.010
  * [4] Cabello, S.: Approximation algorithms for spreading points. J. Algorithms 62(2), 49–73 (2007), https://doi.org/10.1016/j.jalgor.2004.06.009
  * [5] Consuegra, M.E., Narasimhan, G.: Geometric avatar problems. In: Seth, A., Vishnoi, N.K. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India. LIPIcs, vol. 24, pp. 389–400. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013), https://doi.org/10.4230/LIPIcs.FSTTCS.2013.389
  * [6] Cormode, G., McGregor, A.: Approximation algorithms for clustering uncertain data. In: Lenzerini, M., Lembo, D. (eds.) Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, June 9-11, 2008, Vancouver, BC, Canada. pp. 191–200. ACM (2008), https://doi.org/10.1145/1376916.1376944
  * [7] Daescu, O., Ju, W., Luo, J.: NP-Completeness of spreading colored points. In: Wu, W., Daescu, O. (eds.) Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I. Lecture Notes in Computer Science, vol. 6508, pp. 41–50. Springer (2010), https://doi.org/10.1007/978-3-642-17458-2_5
  * [8] Das, S., Goswami, P.P., Nandy, S.C.: Smallest color-spanning object revisited. Int. J. Comput. Geom. Appl. 19(5), 457–478 (2009), https://doi.org/10.1142/S0218195909003076
  * [9] Dror, M., Orlin, J.B.: Combinatorial optimization with explicit delineation of the ground set by a collection of subsets. SIAM J. Discret. Math. 21(4), 1019–1034 (2008), https://doi.org/10.1137/050636589
  * [10] Dumitrescu, A., Jiang, M.: Dispersion in disks. Theory Comput. Syst. 51(2), 125–142 (2012), https://doi.org/10.1007/s00224-011-9331-x
  * [11] Edalat, A., Lieutier, A., Kashefi, E.: The convex hull in a new model of computation. In: Proceedings of the 13th Canadian Conference on Computational Geometry, CCCG, Waterloo, Canada, August 13-15, 2001. pp. 93–96 (2001)
  * [12] Fiala, J., Kratochvíl, J., Proskurowski, A.: Systems of distant representatives. Discret. Appl. Math. 145(2), 306–316 (2005), https://doi.org/10.1016/j.dam.2004.02.018
  * [13] Fleischer, R., Xu, X.: Computing minimum diameter color-spanning sets is hard. Inf. Process. Lett. 111(21-22), 1054–1056 (2011), https://doi.org/10.1016/j.ipl.2011.07.015
  * [14] Fraser, R.: Algorithms for geometric covering and piercing problems. Ph.D. thesis, University of Waterloo (2013)
  * [15] Hasheminejad, J., Khanteimouri, P., Mohades, A.: Computing the smallest color spanning equilateral triangle. In: Proceedings of 31st European Workshop on Computational Geometry, EuroCG, Ljubljana, Slovenia, March 15-18, 2015. pp. 32–35 (2015)
  * [16] Huttenlocher, D.P., Kedem, K., Sharir, M.: The upper envelope of Voronoi surfaces and its applications. Discret. Comput. Geom. 9, 267–291 (1993), https://doi.org/10.1007/BF02189323
  * [17] Jadhav, S., Mukhopadhyay, A., Bhattacharya, B.K.: An optimal algorithm for the intersection radius of a set of convex polygons. J. Algorithms 20(2), 244–267 (1996), https://doi.org/10.1006/jagm.1996.0013
  * [18] Jiang, M., Wang, H.: Shortest color-spanning intervals. Theor. Comput. Sci. 609, 561–568 (2016), https://doi.org/10.1016/j.tcs.2015.01.039
  * [19] Ju, W., Fan, C., Luo, J., Zhu, B., Daescu, O.: On some geometric problems of color-spanning sets. J. Comb. Optim. 26(2), 266–283 (2013), https://doi.org/10.1007/s10878-012-9458-y
  * [20] Keikha, V., Aghamolaei, S., Mohades, A., Ghodsi, M.: Clustering geometrically-modeled points in the aggregated uncertainty model. Fundam. Informaticae 184(3), 205–231 (2021), https://doi.org/10.3233/FI-2021-2097
  * [21] Keikha, V., Löffler, M., Mohades, A.: A fully polynomial time approximation scheme for the smallest diameter of imprecise points. Theor. Comput. Sci. 814, 259–270 (2020), https://doi.org/10.1016/j.tcs.2020.02.006
  * [22] Keikha, V., Löffler, M., Mohades, A.: Largest and smallest area triangles on imprecise points. Comput. Geom. 95, 101742 (2021), https://doi.org/10.1016/j.comgeo.2020.101742
  * [23] Khanteimouri, P., Mohades, A., Abam, M.A., Kazemi, M.R.: Computing the smallest color-spanning axis-parallel square. In: Cai, L., Cheng, S., Lam, T.W. (eds.) Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. Lecture Notes in Computer Science, vol. 8283, pp. 634–643. Springer (2013), https://doi.org/10.1007/978-3-642-45030-3_59
  * [24] Knauer, C., Löffler, M., Scherfenberg, M., Wolle, T.: The directed Hausdorff distance between imprecise point sets. Theor. Comput. Sci. 412(32), 4173–4186 (2011), https://doi.org/10.1016/j.tcs.2011.01.039
  * [25] Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discret. Math. 5(3), 422–427 (1992), https://doi.org/10.1137/0405033
  * [26] van Kreveld, M., Löffler, M.: Approximating largest convex hulls for imprecise points. J. Discrete Algorithms 6(4), 583–594 (2008), https://doi.org/10.1016/j.jda.2008.04.002
  * [27] Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982), https://doi.org/10.1137/0211025
  * [28] Löffler, M., van Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56(2), 235–269 (2010), https://doi.org/10.1007/s00453-008-9174-2
  * [29] Löffler, M., van Kreveld, M.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. 43(4), 419–433 (2010), https://doi.org/10.1016/j.comgeo.2009.03.007
  * [30] Manzini, R., Gamberini, R.: Design, management and control of logistic distribution systems. Int. J. Adv. Robot. Syst. pp. 263–290 (2008)
  * [31] Pop, P.C.: The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances. Eur. J. Oper. Res. 283(1), 1–15 (2020), https://doi.org/10.1016/j.ejor.2019.05.017
  * [32] Robert, J.M., Toussaint, G.: Computational geometry and facility location. In: Proceedings of International Conference on Operations Research and Management Science. pp. 11–15 (1990)
  * [33] Salesin, D., Stolfi, J., Guibas, L.J.: Epsilon geometry: Building robust algorithms from imprecise computations. In: Mehlhorn, K. (ed.) Proceedings of the Fifth Annual Symposium on Computational Geometry, Saarbrücken, Germany, June 5-7, 1989. pp. 208–217. ACM (1989), https://doi.org/10.1145/73833.73857
  * [34] Suri, S., Verbeek, K., Yildiz, H.: On the most likely convex hull of uncertain points. In: Bodlaender, H.L., Italiano, G.F. (eds.) Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013\. Proceedings. Lecture Notes in Computer Science, vol. 8125, pp. 791–802. Springer (2013), https://doi.org/10.1007/978-3-642-40450-4_67
  * [35] Zhang, D., Chee, Y.M., Mondal, A., Tung, A.K.H., Kitsuregawa, M.: Keyword search in spatial databases: Towards searching by document. In: Ioannidis, Y.E., Lee, D.L., Ng, R.T. (eds.) Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29-April 2, 2009, Shanghai, China. pp. 688–699. IEEE Computer Society (2009), https://doi.org/10.1109/ICDE.2009.77