March 3, 2026Open Access

Partitioning Colored Points into Monochromatic Islands is NP-Complete

Key Points

Partitioning colored points into monochromatic subsets is NP-complete, showing high computational difficulty.
The study defines monochromatic subsets as those containing only one color, which complicates partitioning.
Using theoretical modeling, the problem's NP-completeness was established through relevant mathematical proofs.
Understanding this complexity may guide future research in computational geometry and algorithm design.

Abstract

We are given a set S of colored points and a positive integer κ. A subset of S is monochromatic if it contains points of only one color. We prove that it is NP-complete to decide whether S can be partitioned into at most κ monochromatic subsets whose convex hulls are pairwise-disjoint.

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Discussion

Cite this study

Broek et al. (Wed,) studied this question.

www.synapsesocial.com/papers/69a75fccc6e9836116a2bc98

Authors

Steven W.; id_orcid 0009-0005-6677-3916 van den Broek

Marc van Kreveld

Soeren; id_orcid 0000-0001-5161-3841 Terziadis

Actions

References and Citations

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Partitioning Colored Points into Monochromatic Islands is NP-Complete

Key Points

Abstract

Citation Network

Connected Papers

Discussion

Cite this study

Authors

Actions

References and Citations

Citation Network

Connected Papers

Discussion