Coarseness of Point Sets - Benchmark Instances, by Allan Sapucaia, C. C. de Souza and P. J. de Rezende

Citing this page:

    Use the BibTeX entry:

    @Misc{coar-instances-page,
     author = {Allan Sapucaia and Cid C. de Souza and Pedro J. de Rezende},
     title = {Coarseness of Point Sets - Benchmark Instances},
     year = {2021},
     url = {www.ic.unicamp.br/~cid/Problem-instances/Coarseness}
    }

Problem description

Given a bipartite planar point set \(P= R\,\cup\, B\), with \(R\,\cap\, B = \emptyset\), we call \(R\) (red points) and \(B\) (blue points) classes of points and say that \(P\) is a bicolored set. A subset \(Q \subseteq P\) is an island if there is a convex region \(C\) such that \(Q = C\cap P\). The set of all islands of \(P\) is denoted by \(\mathcal{I}(P)\). We associate a discrepancy with each island \(Q \in \mathcal{I}(P)\), given by \(\nabla_Q = |\,|R\cap Q|-|B \cap Q|\,|\)

Moreover, the discrepancy of a partition \(\Pi=\{Q_1, Q_2, \ldots Q_k\} \subseteq \mathcal{I}(P)\) of \(P\) into \(k\) pairwise disjoint islands, denoted by \(\nabla_\Pi\), is given by \(\nabla_\Pi = \min_{Q \in \Pi} \nabla_Q\). The coarseness of \(P\), denoted by \(\mathcal{C}(P)\), is the maximum discrepancy among all possible partitions of \(P\) into pairwise disjoint islands. The figures below illustrate the concepts of discrepancy and coarseness.

Suboptimal Partition

Optimal Partition

Problem Statement. Given a bicolored planar point set, the Coarseness Problem consists in determining its coarseness.

The problem was first introduced in [1] and its time complexity remais unknown, but conjectured to be NP-hard.

Input Instances

The name of each instance is in the following pattern:

     r<\(n\)>-<\(id\)>.inst

File Format: Instances
Each instance consists of a list of points, with the following format:

     <\(n\)>
     <\(x\ y\)>
     <\(c\)>

The value \(n\) is the number of points. The next \(n\) lines have two rational numbers \(x\) and \(y\) corresponding to the horizontal and vertical coordinates of each point. The remaining \(n\) lines have a binary indicating the color of each point.

Instances instances.tar.bz2 (79.5K)

Results

The results are in csv files, each one corresponding to a solving method. Each row of each file corresponds do an instance. The columns in the file indicate the properties being measured and the specific configuration of the solver. More information about these results can be found in [2].
full results-full.csv (6.5K)
full-relax results-full-relax.csv (15.9K)
cg results-cg.csv (14.4K)

These solutions were obtained with an implementation in C++14, compiled with GCC compiler version 7.2.0, using -O3 as optimization level. As an ILP solver we employed SCIP 7.0.2, using IBM's ILOG CPLEX version 12.10.0 as LP solver.
Geometric structures and procedures were implemented using CGAL 5.2, using exact rational numbers represented by Gmpq. We conducted the experiments on a computer with an Intel® Xeon® CPU E5-2420 processor at 1.90 GHz and 32GB of RAM.

Solution Files

For each instance, there is a corresponding solution file. The name of the file is in the following pattern:

     <inst_name>_<configuration>_<.isol

The content of each solution file is in the format:

     <\(m d\)>
     <\(ch\) \(int\) \(ch_i\) | \(int_j\) \(v\)>

Where \(m\) indicates the number of islands and (\d\) the discrepancy of the solution, followed by \(m\) lines describring the islands. For each island \(ch\) indicates the number of vertices in its convex hull and \(int\) the number of interior points. Next, the \(ch\) points are listed in counter-clockwise order followed by the \(int\) interior points in any order. The lines end with the value of the variable in the solution.

full solutions-full.tar.bz2 (32K)
full-relax solutions-full-relax.tar.bz2 (338.7K)
cg solutions-cg.tar.bz2 (17.5K)

Acknowledgments

This research was supported in part by grants from: Brazilian National Council for Scientific and Technological Development (CNPq) #313329/2020-6, #309627/2017-6, #304727/2014-8; São Paulo Research Foundation (FAPESP) #2020/09691-0, #2018/ 26434-0, #2018/14883-5, #2014/12236-1.

References

Address

Allan Sapucaia, Cid C. de Souza and Pedro J. de Rezende
Universidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: