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- \(n\): Number of points, or size.
- id: Instance identification, between 0 and 29.
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) |
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>_<.isolThe 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
- [1] On the coarseness of bicolored point sets, S. Bereg, J.M. Diáz-Báñez, D. Lara, P. Pérez-Lantero, C. Seara, & J. Urrutia , In Computational Geometry 46 (pages 65–77), 2013.
- [2] Solving the Coarseness Problem by ILP using Column Generation , A. Sapucaia, P. J. de Rezende, & C. C. de Souza, submitted for publication (2021).
Address
Allan Sapucaia, Cid C. de Souza and Pedro J. de RezendeUniversidade 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: